LinksAJAX Digital Watch
Downloadable Automatic Layout ImplementationsAGD: A Library of Algorithms for Graph Drawinghttp://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 VisualizationA 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 toolkithttp://www.cs.washington.edu/research/constraints/cassowary/http://www.cs.washington.edu/research/constraints/cda/run.html 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 (nonlinear 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 Generatorhttp://www2data.informatik.unibwmuenchen.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, multisegment 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 superstate, 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 VGJhttp://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. GraphPlaceftp://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 19931994. Graphviz  open source graph drawing softwarehttp://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 Toolkithttp://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 Layouthttp://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 TopologyShapeMetrics Approach for the Automatic Layout of UML Class Diagramshttp://portal.acm.org/citation.cfm?id=774860&jmp=indexterms&dl=portal&dl=ACM Implementation available: http://wwwpr.informatik.unituebingen.de/c/forschung/uml/jarinspector.xml#Getting%20Started
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 "ForceDirected" 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 enduser 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. Tupliphttp://www.tulipsoftware.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 Graphshttp://rw4.cs.unisb.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 plugin 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 Editorhttp://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 postprocessing step. Automatic Layout DocumentsAn Algorithm for Blob Hierarchy Layouthttp://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 Organizationhttp://ieeexplore.ieee.org/iel1/21/6915/00278993.pdf?tp=&arnumber=278993&isnumber=6915 Discuses rulebased 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 rulebased 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 layouthttp://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... Constraintbased Diagram Beautificationhttp://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 Exampleshttp://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 Algorithmshttp://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 Layouthttp://www.cs.usyd.edu.au/~aquigley/papers/aqgd2000.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 realtime 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 MultiDimensional Algorithm for Drawing Large Graphs (2000)http://citeseer.ist.psu.edu/gajer00fast.html An alternative method to force directed and other approaches that generalizes ndimensional 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). Forcetransfer: a new approach to removing overlapping nodes in graph layoutAdding 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 SemiAutomatic 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 studyhttp://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 Layoutshttp://www.research.att.com/areas/visualization/papers_videos/papers/1999gn.pdf This is a very promissing paper for noninteractive automatic layout of a densely connected graph, such as a reachability graph. Nodes are intially spread out using force direction, then overlapping of nonpoint 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 interfaceshttp://www2data.informatik.unibwmuenchen.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.

Maintained by Denis Dube.  Last Modified: 2008/09/09 18:03:05. 