login  home  contents  what's new  discussion  bug reports help  links  subscribe  changes  refresh  edit
 Topics FrontPage SandBox SandBoxAdjacencyMatrix <-- You are here. On Tue, Jun 17, 2008 at 10:07 AM Franz Lehner wrote: Subject: fricas-devel Matrix Integer disappears the following strange error happens. I wrote a small graph package in aldor, mainly to compute adjacency and Laplace matrices (which are of type Matrix Integer). When I generate a graph in a fresh fricas (gcl, rev 276) session:  ********************************** 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 **********************************  I get:  Internal Error The function determinant with signature hashcode is missing from domain Matrix(Integer)  Some observations: If the domain Matrix Integer is loaded before the command LaplaceMatrix? G is invoked, the error does not occur invoking Matrix Float does not help the same error occurs with minordet, but not with other functions from Matrix Integer, e.g. trace, rowEchelon, inverse the functions determinant and minordet appear always together in matrix.spad like:  if R has commutative("*") then determinant x == determinant(x)$MATLIN minordet x == minordet(x)$MATLIN  What is going on here? 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; } } aldor Compiling FriCAS source code from file /var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/7564286725989313503-25px001.as using Aldor compiler and options -O -Fasy -Fao -Flsp -lfricas -Mno-ALDOR_W_WillObsolete -DFriCAS -Y$FRICAS/algebra -I $FRICAS/algebra Use the system command )set compiler args to change these options. The )library system command was not called after compilation. fricasG:=new()$FiniteGraph Integer The right-hand side of the \$ operator must be a package or domain name, but FiniteGraph(Integer) is a category.

 Subject:   Be Bold !! ( 15 subscribers )