Layered Graph Layouts with a Given Aspect Ratio

• US 20080291203A1
• Filed: 05/21/2007
• Published: 11/27/2008
• Est. Priority Date: 05/21/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Robertson, George G., Lee, Bongshin, Nachmanson, Lev Boris
• Granted Patent: US 7,932,907 B2
• Time in Patent Office: Days
• US Class Current: 345/440
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs
• CPC Class Codes: G09G 2340/0407 Resolution change, inclusive of the use of different resolutions for different screen areas
• CPC Class Codes: G09G 2340/0442 Handling or displaying different aspect ratios, or changing the aspect ratio
• CPC Class Codes: G09G 2340/0464 Positioning

Abstract

A graph layout technique that creates a layered graph layout with a given aspect ratio. The present layered graph layout technique better utilizes the available space and, at the same time, creates an aesthetically pleasing drawing of a directed graph. In one embodiment it determines the layout of the new graph based on a modified Sugiyama technique combined with a modified Coffman-Graham scheduling algorithm. Given a directed graph and a desired aspect ratio, it uses a binary search and the Coffman-Graham scheduling algorithm to find a layout of the graph that has an aspect ratio that matches the given aspect ratio of the available space.

Claims

1. A computer-implemented process for laying out a layered graph, comprising using a computer to perform the process actions of:

inputting a directed graph and a desired aspect ratio;

creating a directed acyclic graph from the input directed graph;

determining a layout of a new graph by using a modified Coffman-Graham scheduling process that limits the widths of nodes in a layer of the directed acyclic graph to find an interim layout of the directed acyclic graph with an aspect ratio that matches the desired aspect ratio; and

performing a layout of the new graph with the interim layout of the directed acyclic graph when an interim layout is found such that its aspect ratio matches the desired aspect ratio.

2. The computer implemented process of claim 1 further comprising stretching the new graph in the horizontal and vertical directions to obtain an aspect ratio that exactly matches the desired aspect ratio.

3. The computer-implemented process of claim 2 wherein the height and width of the new graph are adjusted by adjusting the horizontal and vertical distances between the nodes.

4. The computer-implemented process of claim 1 further comprising computing splines connecting nodes in the new graph.

5. The computer-implemented process of claim 1 wherein determining a layout of a new graph further comprises balancing the nodes of the layout of the new graph in the horizontal direction.

6. The computer-implemented process of claim 1 further comprising shortening the lengths of the edges in the new graph.

7. The computer-implemented process of claim 1 wherein the input graph is defined by a separation function, a weight function, nodes and node boundary curves.

8. The computer-implemented process of claim 4 further comprising drawing splines between the nodes of the new graph.

9. The computer-implemented process of claim 1 wherein determine an interim layout of the new directed acyclic graph using a Coffman-Graham scheduling procedure comprises:

defining a layout function as a version of a Coffman-Graham procedure that uses the graph layer capacity;

computing layers of the new directed acyclic graph using the defined layout function;

ordering the layers of the new directed acyclic graph;

calculating the coordinates of the nodes of the new directed acyclic graph to create the interim layout.

10. A computer-readable medium having computer-executable instructions for performing the computer-implemented process recited in claim 1.

11. A system for generating a layout for a directed acyclic graph, comprising:

a general purpose computing device;

a computer program comprising program modules executable by the general purpose computing device, wherein the computing device is directed by the program modules of the computer program to,

(a) input a given directed graph and a desired aspect ratio;

(b) determine the minimum and maximum widths of a desired new directed acyclic graph;

(c) use the minimum and maximum widths to find a width of the new directed acyclic graph;

(d) determine an interim layout of the new directed acyclic graph using a Coffman-Graham scheduling procedure with a graph layer capacity;

(e) compute an aspect ratio using the height and width of the interim layout of the new directed acyclic graph;

(f) compare the computed aspect ratio to the desired aspect ratio;

(g) if the computed aspect ratio is close enough to the desired aspect ratio, or the maximum and minimum widths are too close, output the new directed acyclic graph with the interim layout; and

(h) if the computed aspect ratio is not close enough to the desired aspect ratio, compute a new width and repeat (b) through (h) until the computed aspect ratio is close enough to the desired aspect ratio.

12. The system of claim 11 further comprising a module to draw splines between the nodes in the new directed acyclic graph.

13. The system of claim 11 wherein a binary search is used to find the width of the new directed acyclic graph.

14. The system of claim 11 further comprising a module for adjusting the overall height and width of the new directed acyclic graph so that it precisely matches the given aspect ratio.

15. The system of claim 11 wherein the module to determine an interim layout of the new directed acyclic graph using a Coffman-Graham scheduling procedure comprises:

defining a layout function as a version of a Coffman-Graham procedure using the graph layer capacity;

computing layers of the new directed acyclic graph using the defined layout function;

ordering the layers of the new directed acyclic graph;

calculating the coordinates of the nodes of the new directed acyclic graph to create the interim layout.

16. A computer-implemented process for laying out a directed acyclic graph, comprising using a computer to perform the process actions of:

(a) inputting a desired aspect ratio of a graph and directed acyclic graph comprising nodes and edges, a separation function, a weight function and node boundaries;

(b) initializing the lower and upper boundaries on the graph layer capacity;

(c) using the lower and upper boundaries to determine an interim capacity for the new layout;

(d) computing the layers for the new layout using a modified Coffman-Graham scheduling process using the graph layer capacity;

(e) creating a properly layered graph using the new layout;

(f) ordering layers of the properly layered graph;

(g) calculating the x-coordinates of the nodes in the properly layered graph;

(f) computing an aspect ratio of the new layout in the properly layered graph format;

(g) comparing the computed aspect ratio to the desired aspect ratio; and

(h) if the computed aspect ratio is close enough to the desired aspect ratio, using the new layout as the layout of the new directed acyclic graph; and

(i) if the computed aspect ratio is not close enough to the desired aspect ratio, or the upper and lower boundaries are too close to each other, computing new upper and lower boundaries and a new width of the desired directed acyclic graph, and repeating (d) through (i).

17. The computer-implemented process of claim 16 further comprising balancing nodes of the properly layered graph so that they are visually pleasing.

18. The computer-implemented process of claim 17 further comprising shortening lengths of the edges between the nodes of the new directed acyclic graph.

19. The computer-implemented process of claim 16 further comprising adjusting the overall height and width of the new graph so that it more precisely matches the given aspect ratio in the aspect ratio adjustment module.

20. The computer-implemented process of claim 16 further comprising drawing splines between the nodes of the new graph.