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. _______________________________________________ Axiom-developer mailing list [email protected] http://lists.nongnu.org/mailman/listinfo/axiom-developer
