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:
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.fricas
G:=new()$FiniteGraph Integer
The right-hand side of the $ operator must be a package or domain
name, but FiniteGraph(Integer) is a category.