graphopt

words
screenshot
examples
download


words

Overview
-------------------------
This program optimizes graph layouts. That's pretty much it.

graphopt exists because of the inability of freely-available graph layout optimizers to produce human-digestable graphs for many of the graphs I have needed. Class inheritance graphs, class containment graphs, and logical diagrams for large (thousands of nodes) networks have all been laid out more clearly (sometimes with a little post-optimization help from Visio) than otherwise possible.

Graphs can be imported using a subset of the dot format from AT&T Research and Lucent Bell Labs' Graphviz tools (see below). There is also a module to export graphs in a Visio-importable format. Other export modules are in the works.



Description
-------------------------
In contrast to Graphviz and other graph optimizers, graphopt does not use a finite-pass approach to layout optimization. Instead, it uses basic principles of physics to iteratively determine an optimal layout.

Each node is given mass and an electric charge, and each edge is represented as a spring. Node mass, electric charge, optimal spring length, and the spring constant are tweakable in the gui in realtime.

For most graphs, this is all that is needed - hit 'go' and the graph organizes itself much as the analagous real-life system would if constrained to two dimensions. For more complex graphs, some fiddling with the physical parameters at different stages of optimization usually does the trick.

To accomodate very large graphs, an additional mechanism called layering was added. When a graph is loaded, nodes are assigned to layers based on their relative positions. During optimization, you can choose to hide any number of layers. Any nodes assigned to a layer lower than the selected layer are not only hidden, but neither their electric charges nor the forces of the springs attached to them are figured into the forces acting on the visible nodes. In effect, those nodes cease to exist, and a smaller graph is allowed to lay itself out without being constrained by an excessive number of nodes.

Layers are assigned iteratively until all nodes belong to a layer. In each pass, all leaf nodes are assigned to the current layer. If there are no leaf nodes, then nodes that point to only one other node are taken. If there are no nodes that point to only one other node, nodes that point to only two other nodes are taken (and so on...).

Nodes can be moved within the gui by clicking first on the node, then on the location you want the node to move to.



Installation
-------------------------
Installation is completely generic. See INSTALL if you are not familiar with the ./configure;make;make install game.



dot-like import format
-------------------------
The subset of the dot format that is recognized is the simple node to node edge declaration. Both directed and undirected are supported, as are node chains. Since the previous sentences just confuse me, here are some examples:
   "a" -> "b";
   "b" -> "c";
   "c" -- "my node";
   "a" -- "c";
   "a" -- "f" -- "g" -- "h" -- "k" -- "a";
   "a" -> "my node" -> "k";
Any line that does not contain '--' or '->' is ignored.



Future work
-------------------------
See TODO to see what's being worked on. Feel free to suggest changes, or better yet, contribute patches.



Copyright and License
-------------------------
graphopt is copyright 2003 Michael Schmuhl <michael@schmuhl.org>

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA



screenshot (it only takes one...)





examples

some network map examples:
dot file graphopt Graphviz dot Graphviz neato
nohosts.dot
a sample network without leaf hosts
(a sample; the acutal graph is extremely wide)
netmap.dot
the same network with leaf hosts		 absolutely massive; practically unviewable exhausts 256M mem + 256M swap

as you can see in the no-leaf-hosts version, some optimized graphs are just short of ready for human consumption. A few minutes in Visio is enough to clean it up nicely, though -- the hard part has been done.
nohosts.csv - the no-leaf-hosts version, in a Visio-importable format.



download

version 0.1 - initial release
version 0.2 - added support for gcc 3.x
version 0.3 - file opening and importing robustness, change of some default settings
version 0.4 - added postscript export, fixed pixmap install



download hosted at SourceForge.net Logo