[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
I've got a graph Browser that let's someone peruse a directed graph; its
got a 2d, reshapeable cursor so that you can control both (1) the number
of nodes seen in a window, and (2) the portion of the graph seen in a
window. This browser also allows you to (optionally) specify how the
nodes should appear (i.e. their shape + their contents).
I use a simple layout routine that draws all graphs in a tree format.
Cycles within the graph are handled by either duplicating a node that
starts a cycle, or by drawing lines across the tree structure. Although
I can't distribute my software (IBM's rules), Gabe Robins at ISI devised
a similar browser that he sells for about $150. His browser is called
the "ISI Grapher," and it uses the same algorithm that I use.
I'm sorry that I can't include the algorithm here -- Gabe, on the other
hand, details the algorithm on pages 24 and 25 of the ISI Grapher
manual. You can obtain the manual by writing to Gabe at
Information Sciences Institute
The Intelligent Systems Division
4676 Admiralty Way
Marina Del Rey, California 90292-6695
In your letter you also said that you wanted an algorithm that "should
strive to minimize edge crossings and edge lengths and also handle
manhattan routing." Such an "optimal layout" algorithm for an arbitrary
graph would probably take much more power than the Symbolics can offer.
You might have better luck devising a special-purpose algorithm for your
own directed graphs; most layout routines take advantage of some aspect
of the underlying graph structure. For example, I chose a tree layout
since my graphs have few cycles; that may or may not be useful to you.
If you have a highly interconnected graph, you might want to contact the
VLSI group at MIT and ask them about their layout algorithms.