graphs



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.