Edit detail for SandBoxAdjacencyMatrix revision 1 of 2

changed:
-
\begin{aldor}
#include "axiom.as"

AdjacencyMatrix(S:Type): with {
       --constructor
       adjacencyMatrix:(Matrix Integer, List S) -> %;
       ++ \spad{adjacencyMatrix(A:Matrix Integer, V:List S)} constructs an adjacency matrix
       ++ with with vertices V and Matrix A
       --access
       vertices:% -> OneDimensionalArray S;
       ++ \spad{vertices(A)} returns vertices of the adjacency matrix A
       matrix:% -> Matrix Integer;
       ++ \spad{vertices(A)} returns the 0-1 matrix of the adjacency matrix A
       apply:(%,Integer,Integer)-> Integer;
       ++ \spad{A(i,j)} returns $A_{i,j}$
       apply:(%,S,S)-> Integer;
       ++ \spad{A(s,t)} returns $A_{i,tj}$, where $i$, $j$ are the positions
       ++ of $s$ and $t$ in the vertex list.
       -- output
       coerce:% -> OutputForm;
       -- manipulations
       _*:(Permutation Integer,%)->%;
       ++ \spad{pi * A} permutes the vertices and the matrix according to the
       ++ permutation $\pi$.
} == add {
       Rep == Record(matrix:Matrix Integer,vertices:OneDimensionalArray S);
       adjacencyMatrix(A:Matrix Integer, V:List S):% == {
               import from NonNegativeInteger;
               if (nrows A ~= #V) or (ncols A ~= #V) then {
                       error "Sizes not compatible";
               }
               import from Rep;
               per [A,oneDimensionalArray V];
       }

       vertices(A:%):OneDimensionalArray S == {
               import from Rep;
               (rep A).vertices;
       }
       matrix(A:%):Matrix Integer == {
               import from Rep;
               (rep A).matrix;
       }
       apply(A:%,i:Integer,j:Integer):Integer == {
               import from Rep;
               ((rep A).matrix) (i,j);
       }

       apply(A:%,i:S,j:S):Integer == {
               import from Rep;
               reali:Integer := position(i,(rep A).vertices);
               zero? reali => error "First index is not a vertex";
               realj:Integer := position(j,(rep A).vertices);
               zero? realj => error "Second index is not a vertex";
               A(reali,realj);
       }
       (p:Permutation Integer) * (A:%):% == {
               mp:Set Integer:= movedPoints p;
               n:Integer := (# vertices A)::Integer;
               import from List Integer, OneDimensionalArray S,NonNegativeInteger;
               if (min mp) < 1 or (max mp) > n then {
                       error "Permutation out of range";
               }
               -- permute the vertices
               import from Rep;
               import from NonNegativeInteger;
               import from List S;
               newvertices:OneDimensionalArray S := oneDimensionalArray [ (vertices A)(eval(p,i)) for i:Integer in 1@Integer..(#vertices A)::Integer];
               -- permutation matrix
               indic:List Integer := [eval(p,i) for i in 1..n];
               newA:Matrix Integer:= (matrix A)(indic,indic);
               per [newA,newvertices];
       }

       coerce(A:%):OutputForm == {
               import from List OutputForm, Matrix Integer, OneDimensionalArray S;
               bracket commaSeparate [(matrix A)::OutputForm , (vertices A)::OutputForm];
       }

}
GraphCategory(nodes:Type, edges:Type): Category ==  with {
 source:edges->nodes;
 target:edges->nodes;
 outedges:(nodes,%)-> List edges;
 inedges:(nodes,%)-> List edges;
 neighbours:(nodes,%)->List nodes;
 nodesType:(%)-> Type;
}
Edge(nodes:SetCategory):SetCategory with {
       edge: (nodes,nodes) -> %;
       first:%-> nodes;
       ++ \spad{first(e)} returns the first vertex of an edge e.
       second:%-> nodes;
       ++ \spad{second(e)} returns the second vertex of an edge e.
       parts:%-> List nodes;
       ++ \spad{parts(e)} returns the list of vertices of an edge e.
       member?:(nodes,%)->Boolean;
       ++ \spad{member?(n,e)} checks if the vertex n is adjacent to the edge e.
       -- required by SetCategory
       _=:(%,%)->Boolean;
       ~=:(%,%)->Boolean;
       coerce:% -> OutputForm;
       subst:(nodes,nodes,%)->%;
       ++ \spad{subst(x,y,e)} substitutes vertex x by vertex y.
} == add {
       Rep == Record(source:nodes,target:nodes);

       first(x:%):nodes == {
               import from Rep;
               (rep x) source;
       }
       second(x:%):nodes == {
               import from Rep;
               (rep x) target;
       }
       parts(e:%):List nodes == {
               [first e, second e];
       }
       edge(x:nodes,y:nodes):% == {
               import from Rep;
               per [x,y];
       }

       _=(x:%,y:%):Boolean ==  {
               import from nodes;
               (first(x)=first(y) and second(x)=second(y)) or (first(x)=second(y) and second(x)=first(y));
       }

       ~=(x:%,y:%):Boolean ==  not (x = y);

       coerce(e:%):OutputForm == {
               import from List OutputForm, nodes;
               bracket commaSeparate [(first e)::OutputForm, (second e)::OutputForm];
       }

       member?(x:nodes,e:%):Boolean == x=first e or x = second e;
       subst(x:nodes,y:nodes,e:%):% == {
               edge(if first e = x then y else first e, if second e = x then y else second e);
       }
}
edges ==> Edge(nodes);
FiniteGraph(nodes: SetCategory):GraphCategory(nodes,edges) with {
       new:()-> %;
       ++ \spad{new()} creates an empty graph.
       empty:()-> %;
       ++ \spad{empty()} creates an empty graph.
       copy:%->%;
       ++ \spad{new()} creates a copy of a graph G.
       _=:(%,%) -> Boolean;
       ++ \spad{G1=G2} returns true if the vertex sets and the edge sets coincide.
       coerce:% -> OutputForm;
       ++ \spad{G::OutputForm} returns a pair of vertex and edge lists.
       --access
       member?:(nodes,%)->Boolean;
       ++ \spad{member?(x,G)} checks if x is a vertex of G;
       member?:(edges,%)->Boolean;
       ++ \spad{member?(e,G)} checks if e is a vertex of G;
       edgeList: (%) -> List edges;
       nodeList: (%) -> List nodes;
       --in place manipulations
       addNode!: (%,List nodes) -> List nodes;
       ++ \spad{addNode!(G,[x1,x2,...])} adds a list of vertices to a graph G.
       addNode!: (%,nodes) -> List nodes;
       ++ \spad{addNode!(G,x)} adds the vertex x to a graph G.
       addEdge!: (%,nodes,nodes) -> edges;
       ++ \spad{addEdge!(G,x,y)} adds the edge [x,y] to the graph G.
       addEdge!: (%,List edges) -> List edges;
       ++ \spad{addEdge!(G,[e1,e2,...)} adds the edges e1,e2,... to the graph G.
       deleteEdge!: (%,nodes,nodes) -> edges;
       ++ \spad{deleteEdge!(G,x,y)} deletes the edge [x,y].
       deleteNode!: (%,nodes) -> Boolean;
       ++ \spad{deleteNode!(G,x)} deletes the node x and all adjacent edges.
       subst!:(nodes,nodes,%) -> Boolean;
       ++ \spad{subst!(x,y,G)} replaces vertex x by vertex y if possible. If y already is there, nothing is done.
       fuse!:(nodes,nodes,%) -> Boolean;
       ++ \spad{fuse!(x,y,G)} collapses vertex x and vertex y if possible. The new vertex is called y and duplicate edges are removed.
       --copying modifications
       addNode:(%,List nodes) -> %;
       addNode:(%,nodes) -> %;
       addEdge:(%,nodes,nodes) -> %;

       delete:(%,nodes) -> %;
       ++ \spad{delete(G,x)} deletes the vertex x and all adjacent edges.
       fuse:(nodes,nodes,%) -> %;
       ++ \spad{fuse(x,y,G)} returns the graph with x and y identified. Duplicate edges are removed and the new vertex is called y.
       removeLoops:(%) -> %;
       ++ \spad{removeLoops(G)} returns the graph with all loops removed.
       animals:(%,nodes) -> List Set nodes;
       ++ \spad{animals(G,x)} returns the list of animals based at vertex x.
       adjacencyMatrix:%->AdjacencyMatrix nodes;
       ++ \spad{adjacencyMatrix(G)} returns the adjacency matrix of G
       LaplaceMatrix:% -> Matrix Integer;
       ++ \spad{LaplaceMatrix(G)} returns the Laplace matrix of G,
       ++ i.e., the diagonal matrix of degrees minus the adjacency matrix
} == add {
       import from NonNegativeInteger;
       Rep == Record(node: List nodes, edge: List edges);
       new():% == {
               import from Rep;
               n:List(nodes):=copy [];
               e:List(edges):=copy [];
               per([n,e]$Rep);
       }
       empty():% == {
               import from Rep;
               n:List(nodes):=copy [];
               e:List(edges):=copy [];
               per([n,e]$Rep);
       }
       copy(G:%):% == {
               import from Rep, List nodes, List edges;
               per [ copy nodeList G, copy edgeList G];
       }

       _=(G1:%,G2:%):Boolean == {
               import from Set nodes, Set edges;
               nodeq:Boolean := set nodeList G1 = set nodeList G2;
               edgeq:Boolean := set edgeList G1 = set edgeList G2;
               nodeq and edgeq;
       }

       coerce(G:%):OutputForm == {
               import from List OutputForm, List nodes, List edges;
               bracket commaSeparate [ nodeList(G)::OutputForm, edgeList(G)::OutputForm ];
       }
       member?(x:nodes,G:%):Boolean == {
               import from List nodes;
               member?(x , nodeList G);
       }
       member?(e:edges,G:%):Boolean == {
               import from List edges;
               member?(e , edgeList G);
       }



       edgeList(g:%):List edges == {
               G:Rep:=rep g;
               G.edge;
       }
       nodeList(g:%):List nodes == {
               G:Rep:=rep g;
               G.node;
       }
       outedges(x:nodes,G:%):List edges == [e for e:edges in edgeList G | source e = x];
       inedges(x:nodes,G:%):List edges == [e for e:edges in edgeList G | target e = x];
       neighbours(x:nodes,G:%):List nodes == {
               Gr:Rep:= rep G;
               inn:List nodes == [ source e for e:edges in  Gr.edge | target e = x];
               outn:List nodes == [ target e for e:edges in  Gr.edge |source e = x];
               removeDuplicates concat( inn,outn);
       }
       nodesType(g:%):Type == nodes;

       source(e:edges):nodes == first(e);
       target(e:edges):nodes == second(e);
       addNode!(g:%,n:nodes):List nodes == addNode!(g,[n]);
       addNode!(g:%,n:List nodes):List nodes == {
               G:Rep:=rep g;
               if empty? G.node then {
                       G.node:=n;
               }
               else {
                       G.node:=concat!(G.node,n);
               }
               removeDuplicates! (G.node);
               n;
       }
       addEdge!(g:%,source:nodes,target:nodes):edges == {
               G:Rep:= rep g;
               e:edges := edge(source,target);
               --first add the vertices
               import from List nodes;
               addNode!(g,[source,target]);
               if empty? G.edge then {
                       G.edge:=[e];
               }
               else {
                       if not member? (e, G.edge) then {
                               G.edge:=concat!(G.edge,[e]);
                       }
               }
               edge(source,target);
       }
       addEdge!(g:%,ee:List edges):List edges == {
               --first add the vertices
               import from List nodes, ListFunctions2(edges,List nodes), List List nodes;
               newnodes:List nodes:= removeDuplicates reduce(concat, map(parts, ee));
               addNode!(g,newnodes);
               G:Rep:= rep g;
               if empty? G.edge then {
                       G.edge:=removeDuplicates ee;
               }
               else {
                       G.edge:=removeDuplicates concat!(G.edge,ee);
               }
               ee;
       }
       deleteEdge!(g:%,source:nodes,target:nodes):edges == {
               G:Rep:= rep g;
               e:edges:= edge(source,target);
               import from List edges;
               if not empty? G.edge then {
                       k:Integer := position(e,G.edge);
                       if not zero? k then {
                               G.edge:=delete!(G.edge,k);
                       }
               }
               edge(source,target);
       }
       deleteNode!(g:%,x:nodes):Boolean == {
               G:Rep := rep g;
               k:Integer := position(x,G.node) ;
               zero? k => false;
               G.node:= delete!(G.node,k);
               G.edge:= [ e for e:edges in G.edge | not member? (x,e)];
               true;
       }
       subst!(x:nodes,y:nodes,G:%):Boolean == {
               -- first check trivialities
               member?(y, nodeList G) => false;
               not member?(x, nodeList G) => false;
               import from Rep, List nodes, List edges;
               (rep G).node:= map!( (v:nodes):nodes +-> (if v=x then y else v),  (rep G).node);
               (rep G).edge:= map!( (e:edges):edges +-> subst(x,y,e), (rep G).edge);
               true;
       }
       fuse!(x:nodes,y:nodes,G:%):Boolean == {
               import from Rep, List nodes, List edges;
               -- check for trivialities
               k:Integer := position(x,nodeList G);
               zero? k or not member?(y,nodeList G) => false;
               -- remove vertex
               (rep G).node := delete!((rep G).node, k);
               -- update edges and remove duplicates
               (rep G).edge := map!( (e:edges):edges +-> subst(x,y,e), (rep G).edge);
               (rep G).edge := removeDuplicates! ((rep G).edge);
               true;
       }
       addNode(G:%,x:List nodes):% == {
               import from List nodes, List edges, Rep;
               per [ removeDuplicates concat(nodeList G, x), copy edgeList G ];
       }
       addNode(G:%,x: nodes):% == {
               member? (x,G) => copy G;
               import from List nodes, List edges, Rep;
               per [ concat(nodeList G, [x]), copy edgeList G ];
       }

       addEdge(g:%,source:nodes,target:nodes):% == {
               e:edges := edge (source,target);
               -- check if anything todo
               member? (e, edgeList g) => copy g;
               resnodes:List nodes := removeDuplicates concat(nodeList g, [source,target]);
               resedges:List edges :=  concat(edgeList g, [e]);
               import from Rep;
               per [resnodes,resedges];
       }

       delete(G:%,x:nodes):% == {
               k:Integer := position(x,nodeList G);
               zero? k => copy G;
               node: List nodes := delete(nodeList G,k);
               edge: List edges := [ e for e:edges in edgeList G | not member? (x,e)];
               import from Rep;
               per [node,edge];
       }

       fuse(x:nodes,y:nodes,G:%):% == {
               import from Rep, List nodes, List edges;
               -- check for trivialities
               k:Integer := position(x,nodeList G);
               zero? k or not member?(y,nodeList G) => G;
               -- remove vertex
               node:= delete(nodeList G, k);
               -- update edges and remove duplicates
               edge := removeDuplicates map( (e:edges):edges +-> subst(x,y,e), edgeList G);
               per [ node,edge];
       }
       removeLoops(G:%):% == {
               import from Rep, List nodes, List edges, edges;
               per [copy nodeList G, [ e for e in edgeList G | not ((first e) = (second e))]];
       }
       animals(G:%,x:nodes):List Set nodes == {
               -- check for trivialities
               not member? (x, G) => empty();

               recursiveanimals(G,x);
       }

       recursiveanimals(G:%,x:nodes):List Set nodes == {
               import from Set nodes;
               nbx:List nodes:= neighbours(x,G);
               empty? nbx => [set [x]];
               y:nodes := first nbx;
               -- case 1: y is not in the animal -> delete it
               res1:List Set nodes:= recursiveanimals(delete(G,y),x);
               -- case 2: y is in the animal -> keep it and fuse
               res2:List Set nodes:= recursiveanimals(removeLoops fuse(y,x,G),x);
               concat(res1, [ union(y,S) for S:Set nodes in res2 ]);
       }

       adjacencyMatrix(g:%):AdjacencyMatrix nodes == {
               import from Integer;
               import from List List Integer;
               import from Matrix Integer;
               import from List nodes, List edges;
               res:Matrix Integer := zero(#nodeList g,#nodeList g);
               for e:edges in edgeList(g) repeat {
                       i:Integer := position(source e,nodeList g);
                       j:Integer := position(target e,nodeList g);
                       res(i,j):=1@Integer;
                       res(j,i):=1@Integer;
               }
               return adjacencyMatrix(res,nodeList g);
       }

       LaplaceMatrix(g:%):Matrix Integer == {
               import from AdjacencyMatrix nodes, NonNegativeInteger,Integer;
               A:Matrix Integer := - matrix adjacencyMatrix(g);
               -- simply sum up rows
               for i:Integer in 1..(nrows A)::Integer repeat {
                       import from List Integer,Vector Integer;
                       A(i,i):=- reduce(_+,parts row(A,i::Integer));
               }
               A;
       }
       myposition(l:List edges,source:nodes,target:nodes):Integer == {
               e:edges:= edge(source,target);
               import from List edges, UniversalSegment NonNegativeInteger;
               for f:edges in l for i:NonNegativeInteger in 1..#l repeat {
                       if (f=e) then return i::Integer;
               }
               import from Integer;
               0@Integer;
       }
}
\end{aldor}
G:=new()$FiniteGraph Integer
addNode!(G,[1,2,3,4,5])
for i in 1..5 repeat for j in 1..i-1 repeat addEdge!(G,i,j)
A5:=LaplaceMatrix G
determinant A5
\begin{axiom}

\end{axiom}

aldor
#include "axiom.as"
AdjacencyMatrix(S:Type): with {
       --constructor
       adjacencyMatrix:(Matrix Integer, List S) -> %;
       ++ \spad{adjacencyMatrix(A:Matrix Integer, V:List S)} constructs an adjacency matrix
       ++ with with vertices V and Matrix A
       --access
       vertices:% -> OneDimensionalArray S;
       ++ \spad{vertices(A)} returns vertices of the adjacency matrix A
       matrix:% -> Matrix Integer;
       ++ \spad{vertices(A)} returns the 0-1 matrix of the adjacency matrix A
       apply:(%,Integer,Integer)-> Integer;
       ++ \spad{A(i,j)} returns $A_{i,j}$
       apply:(%,S,S)-> Integer;
       ++ \spad{A(s,t)} returns $A_{i,tj}$, where $i$, $j$ are the positions
       ++ of $s$ and $t$ in the vertex list.
       -- output
       coerce:% -> OutputForm;
       -- manipulations
       _*:(Permutation Integer,%)->%;
       ++ \spad{pi * A} permutes the vertices and the matrix according to the
       ++ permutation $\pi$.
} == add {
       Rep == Record(matrix:Matrix Integer,vertices:OneDimensionalArray S);
       adjacencyMatrix(A:Matrix Integer, V:List S):% == {
               import from NonNegativeInteger;
               if (nrows A ~= #V) or (ncols A ~= #V) then {
                       error "Sizes not compatible";
               }
               import from Rep;
               per [A,oneDimensionalArray V];
       }
       vertices(A:%):OneDimensionalArray S == {
               import from Rep;
               (rep A).vertices;
       }
       matrix(A:%):Matrix Integer == {
               import from Rep;
               (rep A).matrix;
       }
       apply(A:%,i:Integer,j:Integer):Integer == {
               import from Rep;
               ((rep A).matrix) (i,j);
       }
       apply(A:%,i:S,j:S):Integer == {
               import from Rep;
               reali:Integer := position(i,(rep A).vertices);
               zero? reali => error "First index is not a vertex";
               realj:Integer := position(j,(rep A).vertices);
               zero? realj => error "Second index is not a vertex";
               A(reali,realj);
       }
       (p:Permutation Integer) * (A:%):% == {
               mp:Set Integer:= movedPoints p;
               n:Integer := (# vertices A)::Integer;
               import from List Integer, OneDimensionalArray S,NonNegativeInteger;
               if (min mp) < 1 or (max mp) > n then {
                       error "Permutation out of range";
               }
               -- permute the vertices
               import from Rep;
               import from NonNegativeInteger;
               import from List S;
               newvertices:OneDimensionalArray S := oneDimensionalArray [ (vertices A)(eval(p,i)) for i:Integer in 1@Integer..(#vertices A)::Integer];
               -- permutation matrix
               indic:List Integer := [eval(p,i) for i in 1..n];
               newA:Matrix Integer:= (matrix A)(indic,indic);
               per [newA,newvertices];
       }
       coerce(A:%):OutputForm == {
               import from List OutputForm, Matrix Integer, OneDimensionalArray S;
               bracket commaSeparate [(matrix A)::OutputForm , (vertices A)::OutputForm];
       }
}
GraphCategory(nodes:Type, edges:Type): Category ==  with {
 source:edges->nodes;
 target:edges->nodes;
 outedges:(nodes,%)-> List edges;
 inedges:(nodes,%)-> List edges;
 neighbours:(nodes,%)->List nodes;
 nodesType:(%)-> Type;
}
Edge(nodes:SetCategory):SetCategory with {
       edge: (nodes,nodes) -> %;
       first:%-> nodes;
       ++ \spad{first(e)} returns the first vertex of an edge e.
       second:%-> nodes;
       ++ \spad{second(e)} returns the second vertex of an edge e.
       parts:%-> List nodes;
       ++ \spad{parts(e)} returns the list of vertices of an edge e.
       member?:(nodes,%)->Boolean;
       ++ \spad{member?(n,e)} checks if the vertex n is adjacent to the edge e.
       -- required by SetCategory
       _=:(%,%)->Boolean;
       ~=:(%,%)->Boolean;
       coerce:% -> OutputForm;
       subst:(nodes,nodes,%)->%;
       ++ \spad{subst(x,y,e)} substitutes vertex x by vertex y.
} == add {
       Rep == Record(source:nodes,target:nodes);
       first(x:%):nodes == {
               import from Rep;
               (rep x) source;
       }
       second(x:%):nodes == {
               import from Rep;
               (rep x) target;
       }
       parts(e:%):List nodes == {
               [first e, second e];
       }
       edge(x:nodes,y:nodes):% == {
               import from Rep;
               per [x,y];
       }
       _=(x:%,y:%):Boolean ==  {
               import from nodes;
               (first(x)=first(y) and second(x)=second(y)) or (first(x)=second(y) and second(x)=first(y));
       }
       ~=(x:%,y:%):Boolean ==  not (x = y);
       coerce(e:%):OutputForm == {
               import from List OutputForm, nodes;
               bracket commaSeparate [(first e)::OutputForm, (second e)::OutputForm];
       }
       member?(x:nodes,e:%):Boolean == x=first e or x = second e;
       subst(x:nodes,y:nodes,e:%):% == {
               edge(if first e = x then y else first e, if second e = x then y else second e);
       }
}
edges ==> Edge(nodes);
FiniteGraph(nodes: SetCategory):GraphCategory(nodes,edges) with {
       new:()-> %;
       ++ \spad{new()} creates an empty graph.
       empty:()-> %;
       ++ \spad{empty()} creates an empty graph.
       copy:%->%;
       ++ \spad{new()} creates a copy of a graph G.
       _=:(%,%) -> Boolean;
       ++ \spad{G1=G2} returns true if the vertex sets and the edge sets coincide.
       coerce:% -> OutputForm;
       ++ \spad{G::OutputForm} returns a pair of vertex and edge lists.
       --access
       member?:(nodes,%)->Boolean;
       ++ \spad{member?(x,G)} checks if x is a vertex of G;
       member?:(edges,%)->Boolean;
       ++ \spad{member?(e,G)} checks if e is a vertex of G;
       edgeList: (%) -> List edges;
       nodeList: (%) -> List nodes;
       --in place manipulations
       addNode!: (%,List nodes) -> List nodes;
       ++ \spad{addNode!(G,[x1,x2,...])} adds a list of vertices to a graph G.
       addNode!: (%,nodes) -> List nodes;
       ++ \spad{addNode!(G,x)} adds the vertex x to a graph G.
       addEdge!: (%,nodes,nodes) -> edges;
       ++ \spad{addEdge!(G,x,y)} adds the edge [x,y] to the graph G.
       addEdge!: (%,List edges) -> List edges;
       ++ \spad{addEdge!(G,[e1,e2,...)} adds the edges e1,e2,... to the graph G.
       deleteEdge!: (%,nodes,nodes) -> edges;
       ++ \spad{deleteEdge!(G,x,y)} deletes the edge [x,y].
       deleteNode!: (%,nodes) -> Boolean;
       ++ \spad{deleteNode!(G,x)} deletes the node x and all adjacent edges.
       subst!:(nodes,nodes,%) -> Boolean;
       ++ \spad{subst!(x,y,G)} replaces vertex x by vertex y if possible. If y already is there, nothing is done.
       fuse!:(nodes,nodes,%) -> Boolean;
       ++ \spad{fuse!(x,y,G)} collapses vertex x and vertex y if possible. The new vertex is called y and duplicate edges are removed.
       --copying modifications
       addNode:(%,List nodes) -> %;
       addNode:(%,nodes) -> %;
       addEdge:(%,nodes,nodes) -> %;
       delete:(%,nodes) -> %;
       ++ \spad{delete(G,x)} deletes the vertex x and all adjacent edges.
       fuse:(nodes,nodes,%) -> %;
       ++ \spad{fuse(x,y,G)} returns the graph with x and y identified. Duplicate edges are removed and the new vertex is called y.
       removeLoops:(%) -> %;
       ++ \spad{removeLoops(G)} returns the graph with all loops removed.
       animals:(%,nodes) -> List Set nodes;
       ++ \spad{animals(G,x)} returns the list of animals based at vertex x.
       adjacencyMatrix:%->AdjacencyMatrix nodes;
       ++ \spad{adjacencyMatrix(G)} returns the adjacency matrix of G
       LaplaceMatrix:% -> Matrix Integer;
       ++ \spad{LaplaceMatrix(G)} returns the Laplace matrix of G,
       ++ i.e., the diagonal matrix of degrees minus the adjacency matrix
} == add {
       import from NonNegativeInteger;
       Rep == Record(node: List nodes, edge: List edges);
       new():% == {
               import from Rep;
               n:List(nodes):=copy [];
               e:List(edges):=copy [];
               per([n,e]$Rep);
       }
       empty():% == {
               import from Rep;
               n:List(nodes):=copy [];
               e:List(edges):=copy [];
               per([n,e]$Rep);
       }
       copy(G:%):% == {
               import from Rep, List nodes, List edges;
               per [ copy nodeList G, copy edgeList G];
       }
       _=(G1:%,G2:%):Boolean == {
               import from Set nodes, Set edges;
               nodeq:Boolean := set nodeList G1 = set nodeList G2;
               edgeq:Boolean := set edgeList G1 = set edgeList G2;
               nodeq and edgeq;
       }
       coerce(G:%):OutputForm == {
               import from List OutputForm, List nodes, List edges;
               bracket commaSeparate [ nodeList(G)::OutputForm, edgeList(G)::OutputForm ];
       }
       member?(x:nodes,G:%):Boolean == {
               import from List nodes;
               member?(x , nodeList G);
       }
       member?(e:edges,G:%):Boolean == {
               import from List edges;
               member?(e , edgeList G);
       }
       edgeList(g:%):List edges == {
               G:Rep:=rep g;
               G.edge;
       }
       nodeList(g:%):List nodes == {
               G:Rep:=rep g;
               G.node;
       }
       outedges(x:nodes,G:%):List edges == [e for e:edges in edgeList G | source e = x];
       inedges(x:nodes,G:%):List edges == [e for e:edges in edgeList G | target e = x];
       neighbours(x:nodes,G:%):List nodes == {
               Gr:Rep:= rep G;
               inn:List nodes == [ source e for e:edges in  Gr.edge | target e = x];
               outn:List nodes == [ target e for e:edges in  Gr.edge |source e = x];
               removeDuplicates concat( inn,outn);
       }
       nodesType(g:%):Type == nodes;
       source(e:edges):nodes == first(e);
       target(e:edges):nodes == second(e);
       addNode!(g:%,n:nodes):List nodes == addNode!(g,[n]);
       addNode!(g:%,n:List nodes):List nodes == {
               G:Rep:=rep g;
               if empty? G.node then {
                       G.node:=n;
               }
               else {
                       G.node:=concat!(G.node,n);
               }
               removeDuplicates! (G.node);
               n;
       }
       addEdge!(g:%,source:nodes,target:nodes):edges == {
               G:Rep:= rep g;
               e:edges := edge(source,target);
               --first add the vertices
               import from List nodes;
               addNode!(g,[source,target]);
               if empty? G.edge then {
                       G.edge:=[e];
               }
               else {
                       if not member? (e, G.edge) then {
                               G.edge:=concat!(G.edge,[e]);
                       }
               }
               edge(source,target);
       }
       addEdge!(g:%,ee:List edges):List edges == {
               --first add the vertices
               import from List nodes, ListFunctions2(edges,List nodes), List List nodes;
               newnodes:List nodes:= removeDuplicates reduce(concat, map(parts, ee));
               addNode!(g,newnodes);
               G:Rep:= rep g;
               if empty? G.edge then {
                       G.edge:=removeDuplicates ee;
               }
               else {
                       G.edge:=removeDuplicates concat!(G.edge,ee);
               }
               ee;
       }
       deleteEdge!(g:%,source:nodes,target:nodes):edges == {
               G:Rep:= rep g;
               e:edges:= edge(source,target);
               import from List edges;
               if not empty? G.edge then {
                       k:Integer := position(e,G.edge);
                       if not zero? k then {
                               G.edge:=delete!(G.edge,k);
                       }
               }
               edge(source,target);
       }
       deleteNode!(g:%,x:nodes):Boolean == {
               G:Rep := rep g;
               k:Integer := position(x,G.node) ;
               zero? k => false;
               G.node:= delete!(G.node,k);
               G.edge:= [ e for e:edges in G.edge | not member? (x,e)];
               true;
       }
       subst!(x:nodes,y:nodes,G:%):Boolean == {
               -- first check trivialities
               member?(y, nodeList G) => false;
               not member?(x, nodeList G) => false;
               import from Rep, List nodes, List edges;
               (rep G).node:= map!( (v:nodes):nodes +-> (if v=x then y else v),  (rep G).node);
               (rep G).edge:= map!( (e:edges):edges +-> subst(x,y,e), (rep G).edge);
               true;
       }
       fuse!(x:nodes,y:nodes,G:%):Boolean == {
               import from Rep, List nodes, List edges;
               -- check for trivialities
               k:Integer := position(x,nodeList G);
               zero? k or not member?(y,nodeList G) => false;
               -- remove vertex
               (rep G).node := delete!((rep G).node, k);
               -- update edges and remove duplicates
               (rep G).edge := map!( (e:edges):edges +-> subst(x,y,e), (rep G).edge);
               (rep G).edge := removeDuplicates! ((rep G).edge);
               true;
       }
       addNode(G:%,x:List nodes):% == {
               import from List nodes, List edges, Rep;
               per [ removeDuplicates concat(nodeList G, x), copy edgeList G ];
       }
       addNode(G:%,x: nodes):% == {
               member? (x,G) => copy G;
               import from List nodes, List edges, Rep;
               per [ concat(nodeList G, [x]), copy edgeList G ];
       }
       addEdge(g:%,source:nodes,target:nodes):% == {
               e:edges := edge (source,target);
               -- check if anything todo
               member? (e, edgeList g) => copy g;
               resnodes:List nodes := removeDuplicates concat(nodeList g, [source,target]);
               resedges:List edges :=  concat(edgeList g, [e]);
               import from Rep;
               per [resnodes,resedges];
       }
       delete(G:%,x:nodes):% == {
               k:Integer := position(x,nodeList G);
               zero? k => copy G;
               node: List nodes := delete(nodeList G,k);
               edge: List edges := [ e for e:edges in edgeList G | not member? (x,e)];
               import from Rep;
               per [node,edge];
       }
       fuse(x:nodes,y:nodes,G:%):% == {
               import from Rep, List nodes, List edges;
               -- check for trivialities
               k:Integer := position(x,nodeList G);
               zero? k or not member?(y,nodeList G) => G;
               -- remove vertex
               node:= delete(nodeList G, k);
               -- update edges and remove duplicates
               edge := removeDuplicates map( (e:edges):edges +-> subst(x,y,e), edgeList G);
               per [ node,edge];
       }
       removeLoops(G:%):% == {
               import from Rep, List nodes, List edges, edges;
               per [copy nodeList G, [ e for e in edgeList G | not ((first e) = (second e))]];
       }
       animals(G:%,x:nodes):List Set nodes == {
               -- check for trivialities
               not member? (x, G) => empty();
               recursiveanimals(G,x);
       }
       recursiveanimals(G:%,x:nodes):List Set nodes == {
               import from Set nodes;
               nbx:List nodes:= neighbours(x,G);
               empty? nbx => [set [x]];
               y:nodes := first nbx;
               -- case 1: y is not in the animal -> delete it
               res1:List Set nodes:= recursiveanimals(delete(G,y),x);
               -- case 2: y is in the animal -> keep it and fuse
               res2:List Set nodes:= recursiveanimals(removeLoops fuse(y,x,G),x);
               concat(res1, [ union(y,S) for S:Set nodes in res2 ]);
       }
       adjacencyMatrix(g:%):AdjacencyMatrix nodes == {
               import from Integer;
               import from List List Integer;
               import from Matrix Integer;
               import from List nodes, List edges;
               res:Matrix Integer := zero(#nodeList g,#nodeList g);
               for e:edges in edgeList(g) repeat {
                       i:Integer := position(source e,nodeList g);
                       j:Integer := position(target e,nodeList g);
                       res(i,j):=1@Integer;
                       res(j,i):=1@Integer;
               }
               return adjacencyMatrix(res,nodeList g);
       }
       LaplaceMatrix(g:%):Matrix Integer == {
               import from AdjacencyMatrix nodes, NonNegativeInteger,Integer;
               A:Matrix Integer := - matrix adjacencyMatrix(g);
               -- simply sum up rows
               for i:Integer in 1..(nrows A)::Integer repeat {
                       import from List Integer,Vector Integer;
                       A(i,i):=- reduce(_+,parts row(A,i::Integer));
               }
               A;
       }
       myposition(l:List edges,source:nodes,target:nodes):Integer == {
               e:edges:= edge(source,target);
               import from List edges, UniversalSegment NonNegativeInteger;
               for f:edges in l for i:NonNegativeInteger in 1..#l repeat {
                       if (f=e) then return i::Integer;
               }
               import from Integer;
               0@Integer;
       }
}

   Compiling FriCAS source code from file 
      /var/zope2/var/LatexWiki/7564286725989313503-25px001.as using 
      AXIOM-XL compiler and options 
-O -Fasy -Fao -Flsp -laxiom -Mno-AXL_W_WillObsolete -DAxiom -Y $AXIOM/algebra
      Use the system command )set compiler args to change these 
      options.
#1 (Warning) Deprecated message prefix: use `ALDOR_' instead of `_AXL'
"/var/zope2/var/LatexWiki/7564286725989313503-25px001.as", line 252: 
       nodesType(g:%):Type == nodes;
.................^
[L252 C18] #2 (Warning) Function returns a domain that might not be constant (which may cause problems if it is used in a dependent type).
   Compiling Lisp source code from file 
      ./7564286725989313503-25px001.lsp
   Issuing )library command for 7564286725989313503-25px001
   Reading /var/zope2/var/LatexWiki/7564286725989313503-25px001.asy
   FiniteGraph is now explicitly exposed in frame initial 
   FiniteGraph will be automatically loaded when needed from 
      /var/zope2/var/LatexWiki/7564286725989313503-25px001
   GraphCategory is now explicitly exposed in frame initial 
   GraphCategory will be automatically loaded when needed from 
      /var/zope2/var/LatexWiki/7564286725989313503-25px001
   Edge is now explicitly exposed in frame initial 
   Edge will be automatically loaded when needed from 
      /var/zope2/var/LatexWiki/7564286725989313503-25px001
   AdjacencyMatrix is now explicitly exposed in frame initial 
   AdjacencyMatrix will be automatically loaded when needed from 
      /var/zope2/var/LatexWiki/7564286725989313503-25px001