axiom-developer
[Top][All Lists]

## [Axiom-developer] graphs and finite graphs.

 From: Martin Rubey Subject: [Axiom-developer] graphs and finite graphs. Date: Tue, 13 Sep 2005 14:38:47 +0200

```Dear Bill,

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.

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/

are open source anyway, and the documentation is well done, too.

* 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.

I'd love to have (oriented) Matroids, (weighted) Graphs, (weighted) Digraphs,
greedoids, etc. treated in a uniform fashion. 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. 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. It is pretty clear to me that digraphs and
graphs should be two separate domains, maybe having a common ancestor.

In fact, what is probably necessary is to find good common ancestors. Note
that a domain may be of several different categories!

Some examples for possible coercions:

weighted Graph +-> weighted Digraph:

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

Graph +-> Matroid:

take the cycle matroid of the graph

Graph +-> Matroid:

there are other constructions, too.

3-connected Matroid <-> 3-connected Graph

it is possible to reconstruct the stars of the graph here.

etc, etc.

Martin

```