Hi guys! (why are there no women out there ???)
Various people (guys only, sadly...) replied:
> I dont know if I have enough expertise to help you, but I became very
> interested in your proposal and I used neato/graphviz one year ago with
> reasonable success. There is some Perl classes GraphViz that manage
> these interfaces, they coulb be inspiring ... I can send them to you
> if you so wish...
>
> If we could integrate graphviz or a similar program inside Maxima it
> would be really great (at least for us).
>
> I am at your disposal if you need a beta tester ...
>
> Daniel
> Sounds interesting. What representation(s) of graphs do you support
> within Maxima, and what operations?
> -s
> Sounds interesting! Will it be includable in share?
>
> Having zero experience, I thought I'd ask - are there tutorials
> somewhere on this? I must confess I wouldn't have thought of this
> application of Maxima, although it sounds cool.
> CY
I have no experence, probably too little knowledge of graph theory, but
the following ideas:
1. the representation of a graph should be fairly general, allowing
(directed) (weighted) (Hyper)graphs. I do not know enough about matroids
to include them, but if anybody is (really) interested, I know some people
who do and we could get a discussion started.
Also I think that it should be possible to have more than one
representation allowed, eg. the adjacency matrix or a a list of vertices
and edges, because of:
2. every day there are new properties of graphs being discussed
and
3. there are some properties of graphs which are time-consuming to compute
and if you change the graph only a little (eg, remove an edge), it is easy
to adjust those properties.
So I think that it is reasonable for the internal rep of such a graph to
look like:
((%hypergraph) alist)
where alist is a list of properties (in any order) and values:
(vertices a b c 1 2 3)
(edges (a b 2.5) (1 b) (2 3) (1 c))
(adjacency-matrix (($matrix) ...))
(perfect-matchings ((edge1 edge2 e3) (e4 e5 e3) ... )
(planar T)
(god-only-knows-what-property value)
So my principal idea (and what makes it interesting for me -- though I'm
not shure whether it's a good one) was, to make every operation on a graph
keep all the old information and bring it up-to-date on demand.
A simple example: Suppose we have a hypergraph with a list of its perfect
matchings, ie., all subsets of the edges so that every vertex gets touched
by exactly one edge. Example:
a--b
| |
c--d
has 2 perfect matchings, ((a b) (c d)) and ((a c) (b d)).
Next the user deletes an edge. Then he asks for the perfect matchings
again. So we could either recompute all the perfect matchings of the new
graph or, we could also just delete all those perfect matchings where this
edge occurs...
So my (current) solution is to have all the property-functions always
return 2 values, ie. the desired result and the new hypergraph.
Problems: in many many situations this ability is probably not needed. So
the computational and memory overhead should be negligible.
Also:
4. it should be easy to add new properties...
So we have to find a proper framework for that. How can we make it
possible to let the user add a new property, and also let him specify what
happens with it when the structure of the graph changes... Maybe hooks as
in emacs?
Well, if you have critisicsm of my ideas, you are welcome. If you want the
current piece of (lisp)-code you can have it. Please keep in mind that I
did this just out of curiousity, maybe it could be done far simpler. Most
of the algorithms are rather straightforeward to implement, see Skiena's
Combinatorica.m... I'm more concerned with the overall framework. Still,
maybe my ideas are just impractical. I do not do much graph research, and
thus I do not know how often it will happen that a result is reusable.
Martin