Well, since I was sick last week and had no mathematics with me I did some
more graph hacking. You can find the result on
http://www.mat.univie.ac.at/~rubey/Maxima/graphs.lisp
Martin
list of functions, changes...
-----------------------------
(defun $hypergraph (m-vertices m-edges &optional undirected)
undirected is simply true or false. to set up an undirected graph the
edges should contain the vertices in increasing order
was (defun $hypergraph (vertices edges &rest type)
sets up a hypergraph, for example
z:hypergraph(['a,'b,'c,'d],[[['a,'b],'w],[['a,'b]],[['c,'d]],[['a,'c]]]);
makes z a graph with four vertices and three edges, two of which are
weighted (an unweighted edge has in fact weight one)
z:hypergraph(['a,'b,'c,'d],[[['a,'b],'w],[['a,'b]],[['c,'d]],[['a,'c]]],T);
would give the underlying undirected graph.
(defun $graph_plot (hgraph)
plots the graph using pigale http://pigale.sourceforge.net/
(works great, Thanks Hubert!!!!)
(defun $remove_edges (hgraph m-edges)
(defun $graph_difference (hgraph1 hgraph2)
(defun $contract_vertices (hgraph m-vertices)
contracts the given vertices to a given vertex, thereby possibly creating
loops...
(defun $graph_composition (hgraph &rest hgraphs)
also known as local join or lexicographic product
(defun $graph_dim (hgraph)
is 2 for graphs, n for n-hypergraphs, False if there are edges of
different length (not to be confused with loops)
(defun $edges (hgraph)
(defun $vertices (hgraph)
(defun $adjacency_matrix (hgraph)
an array for n-graphs, for graphs a matrix
-----------------------------------------------------
to make this work for g-dim=2 you will have to apply my patch to genmatrix
in comm2.lisp or simply replace
(if (= 2 (G-dim hgraph))
(let ((m (G-adjacency-matrix hgraph)))
(apply '$genmatrix m
(nconc (make-list 2
:initial-element
(1- (array-dimension m 0)))
(make-list 2 :initial-element 0))))
(G-adjacency-matrix hgraph))
by
(G-adjacency-matrix hgraph)
in (defun $adjacency_matrix (hgraph)
-------------------------------------------------------
(defun $spanning_trees (hgraph)
is a list of the spanning trees of hgraph
(defun $perfect_matchings (hgraph)
(defun $components (hgraph)
(defun $degree (hgraph n-vertex)
(defun $degree_sequence (hgraph)
(defun $path (n)
(defun $cycle (n)
(defun $complete_product (hgraph1 hgraph2)
(defun $wheel (n)
(defun $fan (n)
(defun $complete_graph (n &optional weights)
is the (undirected) complete graph on n vertices 0 to (n-1) (was n+1
vertices) and takes now optionally a function like lambda([i,j],f[i,j])
that is called on all vertex pairs i<j
(defun $threshold_graph (partition &optional weights)
is an undirected graph on n vertices, vertex i having degree l_i,
defined for partitions [l1,l2,...,ln] as follows:
x x x x x x z z z z
x x x x x x z z
x x x x x x z z
... z z
x x x x x x z z
x x x x x x
y y y y y
y y
y y y
y y
and l_i is the number of x's, y's or z's in line i. The lower shape
(composed of y's is the transpose of the shope composed of z's and the
x's form the larges rectangle with k columns and k+1 lines in the total
shape...
eg: 5 5 3 3 2 2.