Algorithm for drawing directed acyclic graphs

• US 8,237,716 B2
• Filed: 09/08/2008
• Issued: 08/07/2012
• 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
• Primary Examiner(s): HARRISON, CHANTE E
• Application Number:
  US12/206,691
• Publication Number:
  US 20100060643A1
• Time in Patent Office: 1,429 Days
• Field of Search: 345/440, 345/419, 715/243, 715/853
• 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 comprising at least one computer processor, information representing a directed acyclic graph;

providing the information to the at least one computer processor of the computing system;

generating a layout of the directed acyclic graph utilizing the computing system, 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 utilizing the computing system;

straightening the edges of the layout of the directed acyclic graph utilizing the computing system, the straightening increasing a number of vertical edges in the directed acyclic graph;

compacting the one or more subgraphs along x-coordinate axis to generate a compacted directed acyclic graph layout associated with a compacted directed acyclic graph utilizing the computing system; 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 directed acyclic graph utilizing the computing system, wherein assigning new y-coordinates comprises;

computing, for each level of a plurality of levels of the layout of the directed acyclic graph, a weight function that is the ratio of a square of incoming edges to the each level and a number of nodes at the each level; and

adjusting vertical separation between adjacent levels of the plurality of levels in proportion with computed weight functions associated with the adjacent levels.

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 directed acyclic graph further comprises:

sorting, using the layout, child nodes of each node of a plurality of child nodes in an increasing order of order weight.

4. The method in accordance with claim 3, wherein calculation of order weight for each child node comprises:

identifying nodes that are at a higher level than each child node of the plurality of child nodes and that have an edge to a descendant node of the child node; and

computing a median of x-coordinates of the identified nodes, the computed median being the order weight of the child node.

5. The method in accordance with claim 1, wherein the straightening of the edges 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 layout of the directed acyclic graph.

6. The method of claim 5, wherein:

the layout of the directed acyclic graph is used to determine a child-order of a plurality of child-orders that is associated with each corresponding node of a plurality of nodes in the layout; and

the reducing of the number of edge crossings is performed by changing the determined child-order of at least one node of the plurality of nodes,

the changing being performed such that the at least one node is placed, subsequent to the changing, at a location closer to other one or more nodes with which the at least one node shares descendents in the layout.

7. The method of claim 6, wherein:

the number of reduced edge crossings is maintained during the edge straightening; and

the changed child-order is maintained during the edge straightening.

8. The method in accordance with claim 1, wherein the compacting of the one or more subgraphs further comprises:

partitioning the directed acyclic graph into a plurality of vertical chains; and

compacting the plurality of vertical chains closer without causing node overlaps between pairs of adjacent vertical chains, the compacting comprising moving at least one vertical chain towards other one or more vertical chains of the plurality of vertical chains such that edges associated with the at least one vertical chain are maintained as vertical edges during the moving and such that a number of nodes in each level of the directed acyclic graph is maintained during the moving.

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

10. A computer program product comprising a machine-readable medium storing instructions that, when executed by at least one programmable processor, cause the at least one programmable processor to perform operations 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, the reducing comprising moving at least one node of the two or more nodes to a location closer to other one or more nodes with which the at least one node shares descendent nodes in the layout;

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 directed acyclic graph 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, wherein assigning new y-coordinates comprises;

computing, for each level of a plurality of levels of the layout of the directed acyclic graph, a weight function that is the ratio of a square of incoming edges to the each level and a number of nodes at the each level; and

adjusting vertical separation between adjacent levels of the plurality of levels in proportion with computed weight functions associated with the adjacent levels.

11. The computer program product in accordance with claim 10, 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.

12. The computer program product in accordance with claim 10, 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.

13. The computer program product in accordance with claim 12, 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.

14. The computer program product in accordance with claim 10, 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 layout of the directed acyclic graph.

15. The computer program product in accordance with claim 10, 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.

16. The computer program product in accordance with claim 10, further comprising outputting new x- and y-coordinates of the new layout of the directed acyclic graph.

17. A system comprising:

at least one programmable processor; and

a machine-readable medium storing instructions that, when executed by the at least one processor, cause the at least one programmable processor to perform operations 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-coordinate;

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, the straightening increasing a number of vertical edges in the directed acyclic graph;

compacting along x-coordinate axis to generate a compacted directed acyclic graph layout; and

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

computing, for each level of a plurality of levels of the layout of the directed acyclic graph, a weight function that is the ratio of a square of incoming edges to the each level and a number of nodes at the each level; and

adjusting vertical separation between adjacent levels of the plurality of levels in proportion with computed weight functions associated with the adjacent levels.

18. The system in accordance with claim 17, wherein the at least one programmable processor performs further operations comprising:

outputting new x- and y-coordinates of the new layout of directed acyclic graph.