Hi,
I started to hack together a graph theory package, available on
http://www.mat.univie.ac.at/~rubey/Maxima/graphs.lisp
Although it is primarily thought as a Maxima package, it might also be of
interest for the Lisp community. In fact, I was very surprised not to find a
single package dealing with graphs!
To try it out in Lisp, you have to comment out the first three lisp-statements:
(in-package "MAXIMA")
(macsyma-module graphs)
(displa-def %hypergraph display-graph)
and include the following line
(defun meval (x) x)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(g-spanning-trees ($complete_graph (4)))
will give you a list of the 16 spanning trees of the complete graph on 4
vertices.
There is a todo list on the top, I'd be glad if you'd contribute...
(if you like to, please contact me) Note that this is work in progress! For
example, map-edges-sorted contains an expensive test which should be
unnessecary, but I want to leave it there until I "release" the file.
Also note that I do not use some lisp features on purpose: the thing is
primarily thought for maxima and should run on many lisps...
One of the main features of the code is that it doen't forget useful
information when a graph is altered (well, at least this is intended)
For example, it is little work to deduce the list of perfect matchings for a
graph that is produced from another one by removing some edges - if the perfect
matchings are known for this graph...
Martin
The functions that start with a $ are for maxima, the rest is for lisp:
The "user" functions are
* defun hypergraphp (hgraph)
is hgraph a hypergraph?
* defun print-props (hgraph)
for debugging: print the properties of the hypergraph
* defun hypergraph (n-vertices np-edges &optional undirected)
(hypergraph '(1 2 3 4) '(((1 2) 5) ((1 3)) (4 3 1))) gives a new directed
hypergraph with vertices 1 2 3 4 and 3 edges, one of which is a 3-edge, one is
weighted (default weight is 1).
(hypergraph '(1 2 3 4) '(((1 2) 5) ((1 3)) (1 3 4)) T) gives an undirected
graph (assumes that the edges are ordered
* defun remove-edges (hgraph edges)
removes the edges specified. To translate edge-patterns as above to
edge-structures use
(p-edges-to-edges (g-edges hgraph) p-edges)
* defun remove-loops (hgraph &optional (number-of-identical-vertices 1))
removes those edges which contain at least one edge more than
number-of-identical-vertices times
* defun graph-difference (hgraph1 hgraph2)
* defun contract-vertices (hgraph vertices newname)
To translate vertex-names to vertex-structures use
(n-vertices-to-vertices (g-vertices hgraph) n-vertices)
* defun graph-composition (hgraph hgraphs)
* defun G-dim (hgraph)
returns a number if all edges in hgraph have the same length - i.e. 2 for
normal graphs, nil otherwise
* defun G-undirected (hgraph)
* defun loop-p (edge &optional (number-of-identical-vertices 1))
* defun p-edge (edge)
* defun p-edges (edges)
returns a readable form of edges
* defun G-edges (hgraph) (prop-get hgraph 'edges))
* defun G-vertices (hgraph) (prop-get hgraph 'vertices))
* defun G-adjacency-matrix (hgraph)
returns an array containing the adjacency matrix (array) of the (hyper)graph
* defun G-spanning-trees (hgraph)
returns a list of spanning trees
* defun G-perfect-matchings (hgraph)
returns a list of perfect matchings
* defun G-components (hgraph)
* defun G-degree-sequence (hgraph)
* defun G-Tutte (hgraph x y)
returns the Tutte polynomial in x and y (well, this is probably useful in
maxima only
* defun complete-product (hgraph1 hgraph2)
* defun threshold-graph (partition &optional weights)
and here are some exceptions to the $ rule:
* defun $graph_plot (hgraph)
to make this work you have to replace $system with system and install
http://pigale.sourceforge.net/
This is very easy and really worth the effort!
* defun $path (n)
* defun $cycle (n)
* defun $complete_product (hgraph1 hgraph2)
* defun $wheel (n)
* defun $fan (n)
* defun $complete_graph (n &optional weights)
* defun $threshold_graph (partition &optional weights)
* defun $three_aztec (n)