Links

AJAX Digital Watch

Downloadable Automatic Layout Implementations

AGD: A Library of Algorithms for Graph Drawing

http://www.ads.tuwien.ac.at/AGD/

Offers implementations of various automatic graph layout algorithms. Unfortunately, one of the dependencies is commercial, although a free trial version is available.

aiSee - Graph Visualization

http://www.absint.com/aisee/

A commercial tool which accepts models in the form of a very simple ASCII format and then handles the display of the model. Not suited for interactive creation/editing of a model, however. Note: among the many layout algorithms available to it, it has the spring model (aka: force directed model). The results are quite good, based on the examples provided.

Cassowary - an incremental constraint solving toolkit

Solves linear inequalities efficiently. Similar to the QOCA solver. The first link allows you to download either a C or a Java implementation of the constraint solver. The 2nd link brings you to a Java applet that uses the constraint solver in an interactive graphical editor. Although it seems somewhat impressive, there are some terrific problems that linear constraints cannot handle, including object overlapping (no conjunction of linear equations solves this), and the maintenance of distance metrics between objects (non-linear constraint, although there is a special case where all the objects are on a single axis, where a linear constraint will work).

DiaGen: The Diagram Editor Generator

http://www2-data.informatik.unibw-muenchen.de/DiaGen/

Allows you to specify the language of your diagram and generate an editor automatically from it. You still have to code/modify the components to suit your diagram however (ie: boxes, circles, arrows, multi-segment arrows with text support). Often though, you can just copy component code with little or no modification. Nice features: it automatically highlights diagrams that follow the specification you gave it, it provides printing, postscript, zooming, cut & paste, multiple item selection, undo & redo, and if you specify linear constraints with the language definition, it can lock components together in a logical way (ie: nested states will be "trapped" inside their super-state, and arrows will be "trapped" inside the components they connect). By manipulating the visual representation of arrows, it is also fairly simple to get arrows that halt outside circle and box components. While there is code to prevent components from overalapping, using it in your own diagram editor is difficult because it's not documented at this time. May 28,2004.

Drawing Graphs with VGJ

http://www.eng.auburn.edu/department/cse/research/graph_drawing/graph_drawing.html

Another Java graph editor. This one implements tree, spring, and a directed graph layout algorithm.

GraphPlace

ftp://ftp.dcs.warwick.ac.uk/people/Martyn.Amos/packages/graphplace

A program written in C that can quickly generate a graph layout and even export postscript. Apparently, it can even be used in interactive contexts. Written in 1993-1994.

Graphviz - open source graph drawing software

http://www.research.att.com/sw/tools/graphviz/

Uses spring layouts and hierarchical layouts. Same old smae old... but the source is freely available.

JGraphpad Diagram Editor and Application Toolkit

http://www.jgraph.com/jgraphpad.html

This is an open source diagram editor, written in Java, which features 4 layout algorithm implementations. The simulated annealing method is particularly interesting, as the solution it returns minimize the number of edege crossing, thus yielding a better looking graph. Unfortunately, this algorithm appears to have great difficulty avoidign overlapping nodes & edges, so it requires some work on the user's part. I suspect it bogs down quickly as the number of nodes & edges increases (after reading the paper on it, I seriously doubt it can be used interactively). Another algorithm involves a spring model. This algorithm has no difficulties with overlapping nodes & edges, but it does result in more edge crossings than necessary. The implementation is not omptimized either, O(|V|^2 * |E|), so it's definately not interactive either. Finally, there's the GEM algorithm, which is fast, can avoid overlapping, and although doesn't explicitly try to minimize edge crossings does a fair job in that area as well. The only downside is that it doesn't generate the most compact graph.Simulated Annealing taken from: "Drawing Graphs Nicely Using Simulated Annealing" from Ron Davidson and David Harel. ACM Transactions on Graphics, Vol. 15, available: http://citeseer.ist.psu.edu/davidson96drawing.html GEM algorithm: "A Fast Adaptive Layout Algorithm for Undirected Graphs", available: http://citeseer.ist.psu.edu/frick94fast.html

Three Dimensional UML Using Force Directed Layout

http://portal.acm.org/citation.cfm?id=564050&coll=portal&dl=ACM&CFID=21623583&CFTOKEN=37450551

Uses spring directed forces to generate a 3D layout. The interesting thing here is the interview with UML designers and how they found the 3D layout advantageous over 2D. The paper also links to a Java implementation: http://www.wilmascope.org/

A Topology-Shape-Metrics Approach for the Automatic Layout of UML Class Diagrams

http://portal.acm.org/citation.cfm?id=774860&jmp=indexterms&dl=portal&dl=ACM

Implementation available: http://www-pr.informatik.uni-tuebingen.de/c/forschung/uml/jarinspector.xml#Getting%20Started

Points out how unsuited hierarchical algorithms are in free form diagrams like UML.
Proposes a topology-shape-metrics approach instead.
A recap of major aesthetic criteria:

• minimize number of edge crossings CROSSING
• minimize number of bends BEND
• minimize number of node and edge overlap OVERLAP
• maximize number of orthogonal edges ORTHOGONAL
• maximize angular resolution RESOLUTION
• minimize edge length EDGE LENGTH
• minimize area AREA
• maximize rectangular aspect-ratio ASPECT RATIO
• maximize number of edges respecting flow FLOW
• maximize symmetry SYMMETRY

Note: the implementation is very interesting in its own right, as it allows you to build a UML diagram of Java JAR or Class files automatically. The algorithm described in the paper, Orthogonal, is fairly good. The tool lets you compare it with "Circular", "Hierarchical", and "Force-Directed" algorithm implementations. Trying the JAR inspector on itself, I tried the various layout algorithms, and I think it's best to make as many algorithms available to end-user as possible, since a given graph or subgraph may respond better to one or another. For example: the circular algorithm can make nice symetric circles of dependencies that are very clear in some situations, whereas the other algorithms wouldn't make this clear at all. The circle algorithm implementation tends to place nodes way too far out though. Unfortunately, you can only download the JAR, no source files.

Tuplip

http://www.tulip-software.org/

Another graph visualizer, supporting both 2D and 3D graphs. The code is available under GPL, however it requires OpenGL and QT as dependencies. Supports a variety of automatic layout algorithms, including GEM and "spring electrical".

Visualization of Compiler Graphs

http://rw4.cs.uni-sb.de/~sander/html/gsvcg1.html#availability

Has a number of automatic layout algorithms included. The source code is freely available, however the details of the layout algorithms themselves were uglified for licensing reasons. Nonetheless it should be possible to plug-in to this tool for automatic layout services, including crossing minimization. "There are 13 basic layout methods, including a specialized version for trees, and 4 variants of crossing reduction, and various optional optimization methods. Further, the priorities of edges and the number of layout iterations may be set to influence the layout."

yEd - JavaTM Graph Editor

http://www.yworks.com/en/products_yed_about.htm

This product is available free, albeit not the source. It is possible to build graphs interactively, or to import and export GML files. The node layout and edge routing algorithms are excellent (ie: I've tested it with a randomly generated 30 node, 90 edge graph, consisting of small square nodes. I then randomly resized some of the nodes and applied the Smart Organic Layout and then the Organic Edge Router to it). In its current form yED cannot be used to directly create arbitrary diagrams however, since it lacks components and the ability to create them (it does an excellent job of UML diagram however! The edge router even avoids edge crossing on arrow labels). However, it should be possible to output an arbitrary graph from another application to yEd and retrieve the optimized layout. Hence yEd is not recommended for interactive diagram generation, but as a post-processing step.

Automatic Layout Documents

An Algorithm for Blob Hierarchy Layout

http://portal.acm.org/citation.cfm?id=345240&coll=portal&dl=ACM&CFID=21623583&CFTOKEN=37450551

This algorithm is only applicable to diagrams with no edges. It highlights the fact that there are many different diagram types, with very different requirements for automatic layout systems.

Automating the Layout of Network Diagrams with Specified Visual Organization

http://ieeexplore.ieee.org/iel1/21/6915/00278993.pdf?tp=&arnumber=278993&isnumber=6915

Discuses rule-based approaches to graph layout as well as the use of genetic algorithms with mutation, crossover, and reproduction operators. Genetic algorithms work nicely but they are expensive to compute. The rule-based approach is limited due to its application of rules locally, making aesthetic criteria like edge crossings very difficult to minimize. Provides visual examples of the better & worse diagram elements.

Competitive learning of network diagram layout

http://ieeexplore.ieee.org/iel4/5725/15315/00706134.pdf?tp=&arnumber=706134&isnumber=15315 http://www.csse.monash.edu.au/~berndm/ISOM/index.html

Application of neural networks to automatic diagram layout. Very good computational performance. Not sure how applicable it is to a broad range of diagrams yet. Applet available with 2nd link... but I lack the necessary Java plugin on this lab machine...

Constraint-based Diagram Beautification

http://ieeexplore.ieee.org/iel5/6451/17255/00795870.pdf?tp=&arnumber=795870&isnumber=17255

A remarkably similar approach to DiaGen. The Penguins system uses the QOCA linear constraint solver to apply beautification to a diagram using grammar based parsing rules.

Constraints for Visualization (TRIP)

http://www.is.titech.ac.jp/~shin/TRIP/cw95/subsection3_3_1.html#SECTION0003100000000000000

A useful mapping of visual rules into linear constraints.

Evolutionary Learning of Graph Layout Constraints from Examples

http://portal.acm.org/citation.cfm?id=192468&dl=ACM&coll=portal

Perhaps something to look to in the future. The premise is to select good and bad graph examples, present it to the algorithm, and have it create automatic layout based on this. The beauty of it is that even people without technical knowlege can specify complex layout constraints. Unfortunately, I'm not seeing any concrete results or implementations.

An Experimental Study of the Basis for Graph Drawing Algorithms

http://www.jea.acm.org/1997/PurchaseDrawing/

This paper experimentally determines that arc bends are more deterimental the graph readability than arc crossings. Symmetry is apparently not a big hindrance to graph understanding, although the author's point out this may not be fully accurate.

Fast Force Directed 2D Graph Layout

http://www.cs.usyd.edu.au/~aquigley/papers/aq-gd2000.pdf

A paper on the Fade2D algorithm that can efficiently do force directed layouts on large numbers of nodes. Uses knowledge gained from physics simulations of large numbers of particles. Makes spring model possible with tens of thousands of nodes in real-time with less than 1% error from a directly calculated model. For < 1000 nodes though, the direct force O(n^2) algorithm has acceptable speed...

A Fast Multi-Dimensional Algorithm for Drawing Large Graphs (2000)

http://citeseer.ist.psu.edu/gajer00fast.html

An alternative method to force directed and other approaches that generalizes n-dimensional graphs to boot. It would be very interesting to find an implementation of this for comparison with outher methods (in terms of graph beauty and usefullness in interactive contexts).

Force-transfer: a new approach to removing overlapping nodes in graph layout

http://portal.acm.org/ft_gateway.cfm?id=783146&type=pdf&coll=portal&dl=ACM&CFID=21677133&CFTOKEN=77939544

Adding a node to an existing graph can involve manually moving chunks of nodes to make room. Force directed systems will automatically "push" nodes away from the new overlapping node to make room. The standard algorithm pushes in both the vertical and horizontal directions at once and thus often results in a diagram that is larger than it needs to be. This paper proposes an algorithm, which has been implemented and emperically tested successfully, which results in far more compact diagrams.

GLIDE: A Semi-Automatic Graph Drawing Editor <-- update soon -->

http://www.cs.virginia.edu/~glide/

Interesting because instead of having an intelligent drawing tool, they have instead opted for a tool that performs actions only when the user requests them. These requests are essentially visually placed constraints on the diagram. The example run of the program looks very interesting. No source or downloads available though. No reffering sites found. May 17, 2004.

Graph drawing aesthetics and the comprehension of UML class diagrams: an empirical study

http://portal.acm.org/citation.cfm?id=564056&coll=portal&dl=ACM&CFID=21623583&CFTOKEN=37450551

Again, indicates that reducing arc bends can increase the understandability of a diagram. Unfortunately, the paper also shows how difficult it is to measure aesthetics in an emperical fashion (many of the authors hypotheses were not statisically proven correct).

Improved Force Directed Layouts

http://www.research.att.com/areas/visualization/papers_videos/papers/1999gn.pdf

This is a very promissing paper for non-interactive automatic layout of a densely connected graph, such as a reachability graph. Nodes are intially spread out using force direction, then overlapping of non-point sized nodes is taken care of, and finally edges are routed between the nodes, using curves where straight lines aren't possible. Example graphs using this technique appear to be quite readable, even though edge crossing isn't minimized. A simple improvement, such as assigning random colors to edges could increase readability even more.

Interaction in really graphical user interfaces

http://www2-data.informatik.unibw-muenchen.de/People/minas/papers/VL94.pdf

Briefly talks about the problems encountered when using linear inequality solvers for constrained layout. Namely, not every type of constraint has a linear counterpart. There are hacks around it, but they add complexity and uglify code.

Interval arithmetic and interval constraints implementations

http://interval.sourceforge.net/interval/index.html

If the automatic layout problem can be reduced to interval constraints, then these solvers could be quite useful.

Layout-by-example: a fuzzy visual language for specifying stereotypes of diagram layout

http://ieeexplore.ieee.org/iel2/895/6833/00275779.pdf?tp=&arnumber=275779&isnumber=6833

and

Automatic layout of diagrams for software specification

http://ieeexplore.ieee.org/iel5/413/5910/00227922.pdf?tp=&arnumber=227922&isnumber=5910

The basic idea here is to specify automatic layout rules in an intuitive way using stereotypical diagrams, in a given formalism. The authors admit that it doesn't work for every formalism however, especially where there are a limited number of node types and the diagram has a rather free form sytle (ie: Petri Nets).

A Modular Geometric Constraint Solver for User Interface Applications

http://citeseer.ist.psu.edu/467493.html

Discusses the limitations of linear constraints solvers in GUI and graph layouts. Namely, linear constraints cannot be used to directly prevent node overlap nor limit the distance between nodes. Therefore, the non-linear constraint solver Chorus, is proposed. Unfortunately, no implementation is provided. Also, the solver may not be suitable for interactive use (with only 26 nodes, it can take about 4 seconds to compute a layout, although it is possible to drag a node, with virtually no performance penalty).

Spring embedder preprocessing for WWW visualization

http://ieeexplore.ieee.org/iel5/7989/22105/01028861.pdf?tp=&arnumber=1028861&isnumber=22105

An improvement to algorithms using springs to get a graph layout, the proposed preprocessing step takes linear time and produces an intermediary graph that has a shape close to the final result. This means that the expensive spring embedding iterations are drastically reduced in large graphs. Although the paper discusses this in the context off 3D WWW visualization, the concept is fairly simply and should generalize.