[Axiom-developer] RE: graphs and finite graphs.

[Bill Page]

Martin,

On September 13, 2005 8:39 AM you wrote:
> 
> I think that it is a great thing that you start experimenting 
> with graphs. I hope I can assist you when it comes to the
> theoretic framework.

Excellent! Thanks.

> 
> Two (rather different) suggestions:
> 
> * you might want to look at how graphs are done in mupad and in
>   Mathematica. For Mathematica, the relevant source is available
>   at
> 
>   http://www.cs.sunysb.edu/~skiena/combinatorica/
> 
>   you will probable have to install MathReader from Wolfram. 
>   Mupads libraries are open source anyway, and the documentation
>   is well done, too.
>

I am reasonably familiar with graph theory from a computer
science perspective and from the point of view of category
theory. What I had in mind is an implementation of graphs in
Axiom more or less from first principles. Looking at Mathematica
and Mupad should be interesting as examples of applications
but I am sceptical (maybe I am wrong?) that they would provide
the kind of foundation that is needed in Axiom.

Do you have some specific suggestions for things to look for?
 
> * more importantly, I urge you to *sketch* the interactions 
> within the whole complex of graph-like structures on a piece
> of papers -- asking questions, where needed.

That is a good idea, but for other reasons I am motivated to
use MathAction SandBox and email rather than paper. :)

> 
>   I'd love to have (oriented) Matroids, (weighted) Graphs, 
> (weighted) Digraphs, greedoids, etc. treated in a uniform
> fashion.

Yes. One of the things I want graphs for in Axiom is that
(eventually) I also want categories. Being able to explore
matroids in Axiom is also very attractive. We (including
Bertfried Fauser) discussed matroids here long ago in connection
with general (possibly cyclical) dependency structures in
Axiom.

But more immediately, I think FiniteGraph would be very useful
for an implementation of the dependency computation in Peter
Broadbery's Aldor interface (to replace the Java code). To do
that it makes sense to implement this code in Aldor so that it
could be compiled stand alone. But trying this in Axiom lead me
to the distraction of an apparent problem in the way Aldor
categories are handled in Axiom.

Still, this can be done entirely in Axiom with SPAD for now
and we can worry about porting it to Aldor later.

> Some thinking should go in the appropriate representation,
> probably. I think that your approach is good, though. It would
> certainly pay to collect the various common data structures
> and see which concepts match and which don't.

I expect that one would need multiple representations depending
on the particular purpose. For example, from a formal point of
view I want both FiniteGraph with explicit added nodes and
edges, as well as the IntegerGraph with the < order relation to
be in GraphCategory. The issue here with respect to defining
GraphCategory seems to be as inclusive as possible in the
interface, i.e. the exported operations. In both the example
graph domains above I can ask

  edge?(n1,n2)

but I might not expect

  edgeList(G)

to be available for all domains in GraphCategory (although
perhaps in the case of IntegerGraph, it might return an iterator).

> Note, for example, that oriented matroids do *not* correspond
> to digraphs. Then, we'd have to see whether unweighted and
> weighted graphs should be together in one domain or should
> rather be two domains.

I would expect two domains but *maybe* in the same category.
Maybe GraphCategory can be defined from MatroidCategory?

> It is pretty clear to me that digraphs and graphs should be
> two separate domains, maybe having a common ancestor.
>

Undirected graphs (as an Axiom category) could be defined in
terms of directed graphs with an extra condition and then a
undirected graph might be represented as a pair of directed
edges, etc. But this might not be particularly efficient for
some graph algorithms. It is certainly an advantage in Axiom
that we can (usually) write polymorphic algorithms that can
be applied independent of the underlying representation. In
other cases the algorithms might need to take specific advantage
of a given representation. I think I understand how this can
be made to work in Axiom.

So for me the design issues concern mostly how we might choose
to encode the known mathematics of graphs (and related
combinatoric structures) in Axiom at a higher level, i.e. in
terms of Axiom categories.
 
>   In fact, what is probably necessary is to find good common 
> ancestors. Note that a domain may be of several different
> categories!
>

Yes, that is quite important. In Axiom we are not constrained
to simply define class hierarchies.
 
> 
>   Some examples for possible coercions:
> 
>   weighted Graph +-> weighted Digraph: 
>

Agreed.
 
>     each edge becomes two arcs in opposite directions, each 
> of the arcs having the same weight as the edge.
> 
>   Digraph +-> Graph: 
>
>     take the underlying graph. But what happens with weights

Probably we need to consider other functors in addition to
coercions? I would really like to have more "category theory"
here in Axiom to deal with things like this.

> 
>   Graph +-> Matroid:
>   
>     take the cycle matroid of the graph
> 
>   Graph +-> Matroid:
> 

I am interested in this. Could you elaborate a little?

>     there are other constructions, too.
> 
>   3-connected Matroid <-> 3-connected Graph
> 
>     it is possible to reconstruct the stars of the graph here.
> 
>   etc, etc.

Yes, I agree that being able to express these mathematical
concepts in Axiom is a very desirable goal!

Regards,
Bill Page.