Algorithm For Drawing Directed Acyclic Graphs

• US 20100060643A1
• Filed: 09/08/2008
• Published: 03/11/2010
• Est. Priority Date: 09/08/2008
• Status: Active Grant

• Current Assignee: Fair Isaac Corporation
• Original Assignee: Fair Isaac Corporation
• Inventors: Kolipaka, Kashyap Babu Rao, Doshi, Navin, Chhaparwal, Gaurav
• Granted Patent: US 8,237,716 B2
• Time in Patent Office: Days
• US Class Current: 345/440
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs

Abstract

A system and method for drawing directed acyclic graphs is disclosed. In particular, an algorithm, as implemented in a method and system, to aesthetically layout directed acyclic graphs is presented. The algorithm includes methods to reduce the number of edge crossings and increase the number of straight edges in such drawings. The algorithm keeps short and straight edges wherever possible and gives preference to vertical edges. It also provides an edge-crossing reduction heuristic to refine the layout obtained after standard median heuristic layout, and further provides a method to focus on important paths in the graph through layout.

Claims

1. A computer-implemented method for drawing directed acyclic graphs, the method comprising:

receiving, in a computing system, information representing a directed acyclic graph, a computer processor of the computing system configured for;

generating a layout of the directed acyclic graph, the layout comprised of one or more subgraphs, each subgraph comprising two or more nodes and edges that connect pairs of nodes, the nodes and edges being defined in x- and y-coordinates;

reducing the number of edge crossings in the layout of the directed acyclic graph;

straightening the edges of the layout of the directed acyclic graph;

compacting one or more subgraphs along x-coordinate axis to generate a compacted DAG layout; and

assigning new y-coordinates to the nodes of the one or more subgraphs such that the nodes do not overlap in the y-coordinate to generate a new layout of directed acyclic graph.

2. The method in accordance with claim 1, wherein generating the layout of the directed acyclic graph further comprises:

creating a tree copy of the directed acyclic graph;

determining the width of each subgraph in the tree copy; and

generating a layout of the tree copy and using it to layout the input directed acyclic graph such that no overlaps occur in the x-coordinate.

3. The method in accordance with claim 1, wherein reducing the number of edge crossings in the layout of the directed acyclic graph further comprises sorting children nodes of every node in the increasing order of an “

order weight”

.

4. The method in accordance with claim 3 where “

order weight”

calculation for each child node N further comprises;

identifying nodes that are at a higher level than N and have an edge to a descendant node of N;

computing “

order weight of N”

as the median of x-coordinate of these identified nodes

5. The method in accordance with claim 1, wherein straightening the edges of the layout of the directed acyclic graph further comprises maximizing a number of vertical median edges that start or end at nodes at each level in the DAG layout.

6. The method in accordance with claim 1, wherein compacting one or more subgraphs along x axis further comprises:

partitioning the graph into two or more vertical chains; and

compacting the two or more vertical chains closer without causing any node overlaps between pairs of adjacent vertical chains.

7. The method in accordance with claim 1, wherein assigning new y-coordinates to the nodes of the one or more subgraphs further comprises, for each level of the DAG layout, computing a weight function that is the ratio of a square of incoming edges to the each level divided by the number of nodes at each level.

8. The method in accordance with claim 1, further comprising outputting new x- and y-coordinates of the new layout of the directed acyclic graph.

21. The method in accordance with claim 19, further comprising laying out the interesting node clusters and non-interesting node clusters in the assigned slots (vertical span) using the directed acyclic graph layout outlined earlier in claim 1 and 9.

9. A method, executable by a computer processor, for drawing directed acyclic graphs, the method comprising:

generating a layout of the directed acyclic graph, the layout comprised of one or more subgraphs, each subgraph comprising two or more nodes and edges that connect pairs of nodes, the nodes and edges being defined in x- and y-coordinates;

reducing the number of edge crossings in the layout of the directed acyclic graph;

straightening the edges of the layout of the directed acyclic graph;

compacting the nodes of the one or more subgraphs along x-coordinate axis to generate a compacted DAG layout; and

assigning new y-coordinates to the nodes of the one or more subgraphs such that the nodes do not overlap in the y-coordinate to generate a new layout for directed acyclic graph.

10. The method in accordance with claim 9, wherein generating the layout of the directed acyclic graph further comprises:

creating a tree copy of the directed acyclic graph;

determining the width of each subgraph in the tree copy; and

generating a layout of the tree copy and using it to layout the input directed acyclic graph such that no overlaps occur in the x-coordinate.

11. The method in accordance with claim 9, wherein reducing the number of edge crossings in the layout of the directed acyclic graph further comprises sorting children nodes of every node in the increasing order of an order weight.

12. The method in accordance with claim 11 wherein the order weight calculation for each child node N further comprises:

identifying nodes that are at a higher level than N and have an edge to a descendant node of N; and

computing an order weight of N as the median of x-coordinate of these identified nodes.

13. The method in accordance with claim 9, wherein straightening the edges of the layout of the directed acyclic graph further comprises maximizing a number of vertical median edges that start or end at nodes at each level in the DAG layout.

14. The method in accordance with claim 9, wherein compacting one or more subgraphs along x-coordinate axis further comprises:

partitioning the graph into two or more vertical chains; and

compacting the two or more vertical chains closer without causing any node overlaps between pairs of adjacent vertical chains.

15. The method in accordance with claim 9, wherein assigning new y-coordinates to the nodes of the one or more subgraphs further comprises, for each level of the DAG layout, computing a weight function that is the ratio of a square of incoming edges to the each level divided by the number of nodes at the each level.

16. The method in accordance with claim 9, further comprising outputting new x- and y-coordinates of the new layout of the directed acyclic graph.

17. A computer-implemented method for drawing directed acyclic graphs, the method comprising:

receiving information representing a directed acyclic graph;

generating a layout of the directed acyclic graph, the layout comprising two or more nodes and edges that connect pairs of nodes, the nodes and edges being defined in x- and y-coordinates;

reducing the number of edge crossings in the layout of the directed acyclic graph;

straightening the edges of the layout of the directed acyclic graph;

compacting along x-coordinate axis to generate a compacted DAG layout; and

assigning new y-coordinates to the nodes of the compacted DAG layout such that the nodes do not overlap in the y-coordinate, to generate a new layout for directed acyclic graph.

18. The method in accordance with claim 17, further comprising outputting new x- and y-coordinates of the new layout of directed acyclic graph.

19. A method, executable by a computer processor, for focusing on interesting paths in the directed acyclic graphs through layout, the method comprising:

dividing interesting paths into one or more path-clusters;

dividing the nodes of the interesting paths into node clusters;

determining an order in which to lay out the node clusters.

20. The method in accordance with claim 19, further comprising:

dividing non-interesting nodes into non-interesting node clusters; and

assigning the non-interesting nodes into a slot in the one or more paths based on an associated cluster order.

22. The method in accordance with claim 19, wherein dividing interesting paths into one or more path-clusters further comprises:

creating path similarity graph using a similarity measure as number of common nodes

considering only those edges in the path similarity graphs that are above a threshold

identifying connected components in the path similarity graph

23. The method in accordance with claim 19, wherein dividing the nodes of the interesting paths into node clusters further comprises:

assigning nodes that are part of single interesting path to the path cluster of that path.

assigning nodes that are part of multiple paths to the path-cluster of the maximum number of paths.

24. The method in accordance with claim 19, wherein determining an order in which to lay out the interesting node clusters further comprises:

computing rank order each node cluster as a weighted average of the common edges with other node clusters.

sorting the node cluster in the increasing order of their rank

dividing this sorted list of clusters into sub-lists of a fixed size

finding the order of cluster in each sub-list that results in the minimum number of edge-crossings

appending the reordered sub-lists to obtain a final order of node-clusters.