[vtkusers] Graph In VTK

[David Duke]

Amir Youssefi wrote:

> Hi All,
>
> I need graph layout algorithms implemented in VTK. Anybody have such 
> things?

Hi Amir,

It depends on what type of graph you have, and what type of layout you 
want -- do you have a tree, a DAG,  a general graph?  Do you know if 
your graph is planar?  Do you want 2D or 3D layout?

There is a vtkGraphLayoutFilter in the toolkit, which implements a 
Fruchterman-Reingold force-directed layout using polydata as input to 
represent the graph.  This layout is good for some kinds of graphs; 
force directed layout can bring out symmetries and structure, but in 
general force-directed placement is (or at least has been) too 
computationally expensive for "large" graphs -- the state of the art is 
improving, I think a force-directed technique with significantly lower 
time complexity was published in '01, but I don't have books or 
references to hand.

I've done work on some graph filters for VTK, but these have involved 
awkward classes that were trying to do something more general, with 
graphs as a special case; (see http://www.cs.bath.ac.uk/~djd/vtk.html)  
I think the code in my archive contains a 3D tree layout filter, but not 
the one I used for general graphs. I have recent, simpler, code 
specifically for graphs, but am not sure when I can make it available. 
 If force-directed placement is not what you need, you could adapt a 
different layout strategy using the existing vtkGraphLayoutFilter class 
as a guide.  There are a number of graph visualization tools around, 
look for example at the "Tulip" tool (www.tulip-software.org) for 
example; this has a nice set of C++ layout filters that, modulo any 
copyright restrictions and your own needs, you may be able to port 
relatively easily.

regards,
David