[Axiom-developer] graphs and finite graphs.

[Martin Rubey]

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/

  you will probable have to install MathReader from Wolfram. Mupads libraries
  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