Browse Prior Art Database

Method for Visualizing Looping Graphs by Proper Ordering in a 1-Dimensional List View

IP.com Disclosure Number: IPCOM000177586D
Original Publication Date: 2008-Dec-18
Included in the Prior Art Database: 2008-Dec-18
Document File: 3 page(s) / 26K

Publishing Venue

IBM

Abstract

When presented with an arbitrary graph, determining an ordering of nodes is nontrivial. Some kind an ordering is needed when presenting the nodes in a GUI outline view for instance. A directed flow (control) graph has a better way of being visualized by an ordering proceeding from the start node of the graph. When a graph is stored, the nodes are typically written in an unordered fashion within the file and need to be put back into some kind of understandable sequence. We need some kind of sorting rule to find out how to properly present the graph to the user when showing the nodes in an outline.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 60% of the total text.

Page 1 of 3

Method for Visualizing Looping Graphs by Proper Ordering in a 1-Dimensional List View

Problem:

When presented with an arbitrary graph, determining an ordering of nodes is nontrivial. Some kind an ordering is needed when presenting the nodes in a GUI outline view for instance. A directed flow (control) graph has a better way of being visualized by an ordering proceeding from the start node of the graph. When a graph is stored, the nodes are typically written in an unordered fashion within the file and need to be put back into some kind of understandable sequence. A sorting rule is needed to find out how to properly present the graph to the user when showing the nodes in an outline. Graphs obtained in this model are a subset of all possible complex graphs in that they have simple first order looping structures.

Implementation :

To sort the list, a sort comparator is needed capable of comparing two nodes to determine which one should precede the other. Any standard sort method can use the comparator.

Solution :

Order the nodes based on comparing the cardinality of the reachable set of nodes from a

particular node. A node is reachable from another node if it exists along a walk of the directed

graph. Every node is at least reachable from itself. From node n, the cardinality of the reachable set, |R(n)| is just the count of how many nodes any particular node can get to. For instance :

A B C D E F

_

|R(n)| 6 5 4 3 2 1

The sort comparator for this simple case just makes one node precede another according to which has the higher reachable set cardinality to achieve the flat list :

A

    
B
C
D
E
F
In the case of a looping flow, the cardinality of the reachable set for a nodes within a loop are all the same :

1

Page 2 of 3

6 5 1

4 4 4

In this case there must be a way to determine loop entry and follow the directed graph from the entry point. Here a new rule can be imposed for the comparator when a sort collision is seen : Order the node with the...