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

[Bill Page]

On Friday, January 21, 2005 4:46 AM Pierre Doucy wrote:
>
> Bill Page wrote:
> > 
> > You are very welcome to try this again. I can provide you 
> > will a file in graphviz format that contains Axiom's algebra
> > dependencies.
> > 
> 
> OK, send it to me and I'll see what I can do.
>

Here is the Axiom algebra directed graph is Graphviz (dot)
format (158 Kb compressed):

http://page.axiom-developer.org/axiom-algebra.dot.gz

It contains a little over 50,000 arcs. Because of the way the
Axiom compiler reports the dependencies (i.e. the Loading ...
messages) many of these arcs are redundant. For example if we
have the arcs (dependencies):

  A -> B
  B -> C

then when compiling module A, the compiler may also include
the message "Loading C", resulting in the redundant arc:

  A -> C

Pruning these redundant arcs should reduce the size of
the graph considerably.

> 
> > [...]
> > 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.
> 
> I guess I can to it, but probably not before the beginning of 
> February.

Of course as your time permits.

> I've got quite a lot of material related to big graphs and 
> their algorithms.
> The graphviz format should be ok to work w/ your graph (unless
> you have specific needs that graphviz can't meet).
>

I think graphviz format is fine. For now all we need to do is
very simple (bug large) graph manipulations and visualization.
Later perhaps we might want to do much fancier things with
symbols, text and clickable links etc., but don't worry about
that now.

------

Having taken a closer look at Graphviz, I think it would be
quite nice to have Graphviz as an input format for MathAction
so that one could include Graphviz output in web pages like
this

\begin{graphviz}
 ... graphviz commands ...
\end{graphviz}

I notice that TeXmacs already includes a plug-in for
incorporating Graphviz graphs into documents. Neat.

----------

While looking for a quick way to convert GraphXML format
(what I am using now for the Axiom algebra graph) to the
Graphviz dot format, I stumbled across two things that
I found very interesting:

http://www.compendiumdev.co.uk/stareast2003/practical1_2.htm

Practical Experiences in Graph-Based Testing

Alan Richardson

Abstract
 
Herein you are introduced to different structural diagramming
techniques, but primarily the generic directed graph. Graph
usage is explained as part of a structured testing process
and during exploratory testing. The thought processes and
models of testing which have led to my usage of graphs are
examined. I will also list, review and comment on free and
inexpensive tools which you can use to incorporate graph based
tests into your testing process. 

-------

I also was fascinated by:
 
http://catamaran.labs.cs.uu.nl/twiki/pt/bin/view/Transform/WebHome

 The Program Transformation Wiki

Program transformation techniques are used in a many areas of
software engineering ranging from program synthesis, via program
optimization and program refactoring, to reverse engineering and
documentation generation. Many theories, tools and applications
have been developed over the last 30 years. Often the results of
these efforts are used only in the community that developed them.

-----

Here I found a program called GraphXML2dot. It turned out however
that although this was the "simple solution" that I was looking
for, it was not this program itself that was so interesting but
rather the language in which it was written called "Stratego".

http://catamaran.labs.cs.uu.nl/twiki/pt/bin/view/Stratego/WebHome

Stratego is a modular language for the specification of fully
automatic program transformation systems based on the paradigm of
rewriting strategies. The construction of transformation systems
with Stratego is supported by the XT bundle of transformation tools.
The Stratego/XT distribution integrates Stratego and XT.

---------

So typical of the web, my search for a simple solution lead to
investigating something quite different - more intelligent software
tools that might eventually be very useful for future development
of Axiom.

I have stated several times that I think further development of
Axiom reached a significant plateau some years based on it's
overall complexity, the available tools and basic human limitations.
Stratego and related tools might be one important way overcome some
of these limitations and let us get on with the job of testing,
debugging and improving Axiom.

Regards,
Bill Page.