RE: [Axiom-developer] touchgraph, hypertex, hypergraph

[Bill Page]

On Thursday, January 20, 2005 5:04 AM Pierre Doucy wrote:
> 
> I'm not sure I fully understand what you what to do w/ graphs and
> if you really need the "click somewhere to move the graph", but
> here we go
> 
> > There is another project called HyperGraph that is quite similar
> > to TouchGraph but uses a hyperbolic layout. See
> >
> > [...] 
> 
> Graphviz ( http://www.graphviz.org/ ) might help too. I won't give
> you a java applet, but just any graphic file format (PDF, PS, JPG,
> ...), and is available both from a standalone command-line program,
> or through a programmatic interface.

Yes, we experimented with graphviz earlier in this project. See the
axiom-developer archives:

http://lists.gnu.org/archive/cgi-bin/namazu.cgi?query=graphviz&submit=Search
%21&idxname=axiom-developer&max=10&result=normal&sort=date%3Alate

Basically it has similar problems as hypergraph when dealing with
very large graphs. Also it is strictly speaking not open source
software, so that was a bit discouraging.

> 
> > 
> > But when I gave it the full 1300 node graph, what it drew was
> > a graph so dense that all the edges overlapped into something
> > that looked just like a big ball of wool and the program took
> > a very long time to redraw the graph if you even touched it
> > anywhere [...]
> 
> Depending on the complexity of your graph, graphviz is able to draw
> huge graphs without too much pain, and the layout is generally very
> readable.
>

You are very welcome to try this again. I can provide you will a file
in graphviz format that contains Axiom's algebra dependencies.
 
> >
> >
> > Clearly in order to draw the Axiom algebra graph, we are going
> > to have to do it in some hierarchical manner but hopefully one
> > that can be computed from the structure of the graph - not
> > imposed manually like the current layers in the Axiom makefiles.
> > Some day real soon now I hope to find a source for some cookbook
> > graph theory programs what can manipulate graphs of this size,
> > find strongly connected component, prune redundant edges, etc.
> 
> There's a (C++) library - boost (www.boost.org,
> http://www.boost.org/libs/graph/doc/table_of_contents.html), which
> is a generic programming library, allowing you to represent a
> graph in any manner (adjacency lists, adjacency matrix,...) , and
> provides some basic algorithms. The paradigm behind boost - generic
> programming - is somewhat weird, but it actually allows great
> flexibility. I used it in a project related to random graphs/social
> networks. If I remember well, someone I used to work with (and who
> reads this list) implemented the algorithm to find strongly connected
> components. Besides, it integrates with graphviz, in the sense that
> you can import and export from the graphviz format to boost (see
> http://www.boost.org/libs/graph/doc/write-graphviz.html,
> http://www.boost.org/libs/graph/doc/read-graphviz.html )
> 
> Hope that helps...
>

Great. The Boost Graph Library looks quite complete. Thank you for
the reference. Would you or anyone else here be interested in
helping me get started with this, say finding the strongly connected
components in the Axiom algebra dependency graph? Can someone sketch
what would have to be done, e.g. starting like this:

  1) download the boost distribution from here
     http://sourceforge.net/project/showfiles.php?group_id=7586

  2) convert the Axiom algebra dependency graph to format X?

  3) run program Y? to load the graph

  4) run program Z? to list the strongly connected components.

Regards,
Bill Page.