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

[Martin Rubey]

Dear Bill,

Bill Page writes:

 > > * you might want to look at how graphs are done in mupad and in
 > >   Mathematica. 

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

Exactly.

 > Do you have some specific suggestions for things to look for?

not yet. One idea I had when I implemented my graphs-package for maxima (which
is not in a useable state, though) is to extensively use lazy evaluation, very
much like the way polymake works. In terms of graphs, a graph would be
represented by a list of properties, and when you ask for some property, like,
for example, connected?, the list is searched for the property itself, then for
other properties which might imply connectedness and if all fails, an algorithm
that computes the desired property is invoked. This idea works well, if the
amount of storage needed doesn't matter or else for properties that don't need
much, like the chromatic index or the Tutte polynomial. It is, of course,
nearly the same as caching previously computed values. (Nearly, because
sometimes a property has already been computed that implies the desired
property.)


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

I missed polytopes and simplicial complexes. Oh my god!

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

Yes, I very much like the idea to have a category of graphs and then domains
for finite and infinite graphs. (I think that there is not yet a package that
handles infinite graphs at all.)

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

Exactly.

 > Maybe GraphCategory can be defined from MatroidCategory?

Hmm, maybe we shouldn't have categories for structures (like matroids, graphs,
digraphs, etc.) but rather for properties. In fact, this led to a definition of
matroid: a matroid is a collection I of sets (called independend sets) such
that

* \emptyset \in I

* I1\in I and I2\subseteq I1 => I2\in I

* the greedy algorithm works, i.e., it always finds a set I1 \in I achieving
  the maximum weight, regardless of the (nonnegative) weight function.

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

I'm afraid that this can lead to trouble. It can be done - and it might be even
the *right* way to do it, but it entails a lot of work. Many concepts used for
graphs and digraphs nearly match but not quite. One example, which does work is
the concept of degree: the degree in the graph is the indegree (which equals
the outdegree) in the corresponding digraph.

But as I noted before: what are we going to do with the weights. Usually, the
degree in a graph is the sum of the weights of the edges. This will be the same
as the sum of the weight of the incoming arcs in the corresponding digraph.

However: the total weight of the graph is (usually) the product of all its edge
weights. Hence the total weight of the corresponding digraph is the weight of
the graph squared. Thus we can have an operation weight in the category of all
graphs, but it means slightly different things in digraphs and in graphs.

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

So, the first step possibly is to propose some categories. A different approach
is to concentrate on finite graphs first and write the categories later.

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

I don't understand you here.

 > >   Graph +-> Matroid:
 > >   
 > >     take the cycle matroid of the graph
 > > 
 > >   Graph +-> Matroid:
 > 
 > I am interested in this. Could you elaborate a little?

Elaborate on what, other constructions?

 > >     there are other constructions, too.


All the best,

Martin