login  home  contents  what's new  discussion  bug reports     help  links  subscribe  changes  refresh  edit

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
  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?

#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 
      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 
   The )library system command was not called after compilation.

G:=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 !!
  ( 14 subscribers )  
Please rate this page: