Layered graph layouts with a given aspect ratio

• US 7,932,907 B2
• Filed: 05/21/2007
• Issued: 04/26/2011
• Est. Priority Date: 05/21/2007
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Robertson, George, Lee, Bongshin, Nachmanson, Lev
• Primary Examiner(s): HARRISON, CHANTE E
• Application Number:
  US11/751,610
• Publication Number:
  US 20080291203A1
• Time in Patent Office: 1,436 Days
• Field of Search: 345/440, 345/619, 715/235, 715/243, 715/853
• 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 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 wherein determining the interim layout of the new directed acyclic graph using the process comprises;

(a) defining a layout function that uses a graph layer capacity, wherein the graph layer capacity is the maximum of the sum of the node widths on a layer;

(b) computing layers of the new directed acyclic graph using the defined layout function by assigning nodes to a layer where the sum of the node widths assigned to a layer cannot be greater than the graph layer capacity, and the sum of the node widths assigned to a layer cannot be less than a minimum layer width;

(c) replacing any long edge between nodes of the new directed acyclic graph by a sequence of short edges which span only one layer each;

(d) ordering the layers of the new directed acyclic graph; and

(e) calculating the coordinates of the nodes of the new directed acyclic graph to create the interim layout;

if the aspect ratio of the interim layout of the acyclic graph does not match the desired aspect ratio, repeating (a) through (e) using a new graph layer capacity and minimum layer width; 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 4 further comprising drawing splines between the nodes of the new graph.

6. 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.

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

8. 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.

9. 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 procedure with a graph layer capacity, wherein the graph layer capacity is the maximum of the sum of the node widths on a layer, and wherein the procedure comprises;

defining a layout function that uses the graph layer capacity;

computing layers of the new directed acyclic graph using the defined layout function by assigning nodes to a layer where the sum of the node widths assigned to a layer cannot be greater than the graph layer capacity, and the sum of the node widths assigned to a layer cannot be less than a minimum layer width;

replacing any long edge between nodes of the new directed acyclic graph by a sequence of short edges which span only one layer each;

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;

(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.

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

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

12. The system of claim 9 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.

13. 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 process using the graph layer capacity, wherein the graph layer capacity is the maximum of the sum of the node widths on a layer, by assigning nodes to a layer where the sum of the node widths assigned to a layer cannot be greater than the graph layer capacity, and the sum of the node widths assigned to a layer cannot be less than a minimum layer width;

(e) creating a properly layered graph using the new layout by replacing any long edge between nodes by a sequence of short edges that span only on layer each;

(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).

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

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

16. The computer-implemented process of claim 13 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.

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