Layered Graph Layouts with a Given Aspect Ratio

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.

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