|
# GAP Implementation
# This file was generated from
# $Id: ordering.gi,v 1.2 2012/02/27 12:26:34 sunnyquiver Exp $
InstallMethod(LessThanByOrdering,
"for orderings and two paths",
true,
[IsQuiverOrdering, IsPath, IsPath], 0,
function(O,a,b)
return ComparisonFunction(O)(a,b) < 0;
end
);
InstallMethod(IsWellOrdering,
"for an ordering",
true,
[IsQuiverOrdering],0,
function(O)
return IsWellSubset(O,GeneratorsOfQuiver(O!.quiver));
end
);
InstallMethod(IsWellReversedOrdering,
"for an ordering",
true,
[IsQuiverOrdering],0,
function(O)
return IsWellReversedSubset(O,GeneratorsOfQuiver(O!.quiver));
end
);
InstallMethod(IsTotalOrdering,
"for an ordering",
true,
[IsQuiverOrdering],0,
function(O)
return IsTotalSubset(O,GeneratorsOfQuiver(O!.quiver));
end
);
InstallMethod(IsAdmissibleOrdering,
"for an ordering",
true,
[IsQuiverOrdering],0,
function(O)
#Check IsTotalOrdering() first, because it is often faster
return IsTotalOrdering(O) and IsWellOrdering(O);
end
);
DeclareGlobalFunction("CheckQuiverSubsetForCycles");
InstallGlobalFunction(CheckQuiverSubsetForCycles,
function(Q,L)
local h,n,a,b,i,r,visit;
#Possibly a big shortcut
if HasIsAcyclicQuiver(Q) and IsAcyclicQuiver(Q) then
return true;
fi;
#Identify every arrow in the list, as well as every vertex we
#can start from
h:=[];
for a in L do
if IsArrow(a) then
i:=ExtRepOfObj(a)[1];
h[i]:=a;
b:=SourceOfPath(a);
h[ExtRepOfObj(b)[1]]:=b;
fi;
od;
#If we have some arrows
if Length(h)>0 then
n:=[];
i:=1;
#Visit a vertex
#v is the vertex
#j is 3 * the generator position of the vertex
#c is the label of the source vertex for the last arrow which was in the subset
#n[j] = the depth-first search label of the vertex
#n[j-1] = true: the vertex was visited successfully; false: vertex is being visited
#n[j-2] = index of the highest vertex reachable from cycles containing this vertex
visit:=function(v,j,c)
local adj,k,t,p,m;
n[j]:=i; #Label the vertex
n[j-1]:=true; #Mark us in the process of being visited
i:=i+1;
#Check all the arrows
adj:=OutgoingArrowsOfVertex(v);
for p in adj do
t:=TargetOfPath(p);
k:=ExtRepOfObj(t)[1]*3;
#Arrow is inside our subset
if IsBound(h[ExtRepOfObj(p)[1]]) then
#Arrow points to an unvisited vertex
if not IsBound(n[k]) then
if not visit(t,k,n[j]) then
return false;
fi;
#The vertex can reach us
#Or the vertex is part of a cycle that reaches us
elif n[k-1] or (IsBound(n[k-2]) and n[n[k-2]-1]) then
return false;
fi;
#Arrow is outside our subset
else
#Arrow points to an unvisited vertex
if not IsBound(n[k]) then
if not visit(t,k,c) then
return false;
#If it's part of a cycle that reaches us, mark us
elif IsBound(n[k-2]) and n[n[k-2]-1] and
((not IsBound(n[j-2])) or n[n[j-2]]>n[n[k-2]]) then
n[j-2]:=n[k-2];
fi;
#The vertex can reach us
elif n[k-1] or (IsBound(n[k-2]) and n[n[k-2]-1]) then
if IsBound(n[k-2]) then
m:=n[k-2];
else
m:=k;
fi;
#The cycle contains something from our set
if n[m]<=c then
return false;
#Mark us as belonging to the cycle
elif (not IsBound(n[j-2])) or n[n[j-2]]>n[m] then
n[j-2]:=m;
fi;
fi;
fi;
od;
n[j-1]:=false;
return true;
end;
for b in h do
if not IsQuiverVertex(b) then
break;
fi;
r:=ExtRepOfObj(b)[1]*3;
if not IsBound(n[r]) then
if not visit(b,r,0) then
return false;
fi;
fi;
od;
fi;
return true;
end
);
InstallGlobalFunction(LengthOrdering,function(arg)
local O,fam;
if not ((Length(arg) = 1 or (Length(arg) = 2 and IsQuiverOrdering(arg[2])))
and IsQuiver(arg[1])) then
Error("usage: LengthOrdering(Q) or LengthOrdering(Q,O)",
" where Q is a quiver and O is an ordering");
fi;
fam := NewFamily("FamilyLengthOrdering", IsLengthOrdering);
O := Objectify(NewType(fam,IsLengthOrdering and IsAttributeStoringRep),
rec() );
SetOrderingName(O, "length");
# Set quiver in record:
O!.quiver:=arg[1];
# We already know that the argument is an ordering
if Length(arg)=2 then
SetNextOrdering(O, arg[2]);
if HasLexicographicTable(arg[2]) then
SetLexicographicTable(O,LexicographicTable(arg[2]));
O!.lex:=arg[2]!.lex;
fi;
fi;
SetComparisonFunction(O,function(a,b)
local lena, lenb;
if HasWalkOfPath(a) then
lena := Length(WalkOfPath(a));
else
lena := 0;
fi;
if HasWalkOfPath(b) then
lenb := Length(WalkOfPath(b));
else
lenb := 0;
fi;
#Print("lena: ",lena,", lenb: ",lenb,"\n");
if lena < lenb then
return -1;
elif lena = lenb then
if HasNextOrdering(O) then
return ComparisonFunction(NextOrdering(O))(a,b);
else
return 0;
fi;
else
return 1;
fi;
end
);
return O;
end
);
InstallMethod(IsWellReversedOrdering,
"for a length ordering",
true,
[IsLengthOrdering],0,
function(O)
return IsFinite(O!.quiver);
end
);
InstallMethod(IsTotalOrdering,
"for a length ordering",
true,
[IsLengthOrdering],0,
function(O)
if Length(VerticesOfQuiver(O!.quiver))<1 then
return true;
elif HasNextOrdering(O) then
return IsTotalOrdering(NextOrdering(O));
else
return false;
fi;
end
);
InstallMethod(IsWellSubset,
"for a length ordering and a list of generators",
true,
[IsLengthOrdering,IsHomogeneousList],0,
function(O,L)
return true;
end
);
InstallMethod(IsWellReversedSubset,
"for a length ordering",
true,
[IsLengthOrdering,IsHomogeneousList],0,
function(O,L)
return CheckQuiverSubsetForCycles(O!.quiver,L);
end
);
InstallMethod(IsTotalSubset,
"for a length ordering and a list of generators",
true,
[IsLengthOrdering,IsHomogeneousList],0,
function(O,L)
if Length(L)<1 then
return true;
elif HasNextOrdering(O) then
return IsTotalSubset(NextOrdering(O),L);
else
return false;
fi;
end
);
InstallMethod(IsWellOrdering,
"for a lexicographic ordering and a quiver",
true,
[IsLexicographicOrdering],0,
function(O)
local i,l,a,v,m,ret;
if IsFinite(O!.quiver) then
return true;
else
l:=LexicographicTable(O);
#This must be an arrow, or we wouldn't be infinite
a:=l[Length(l)];
v:=SourceOfPath(a);
i:=ExtRepOfObj(v)[1];
if i<>ExtRepOfObj(TargetOfPath(a))[1] or InDegreeOfVertex(v)>1 then
return false;
fi;
m:=AdjacencyMatrixOfQuiver(O!.quiver);
m[i][i]:=0;
ret:=IsFinite(Quiver(m));
m[i][i]:=1;
return ret;
fi;
end
);
InstallMethod(IsWellOrdering,
"for a lexicographic ordering and a quiver",
true,
[IsLexicographicOrdering],0,
function(O)
local i,l,a,v,m,ret;
if IsFinite(O!.quiver) then
return true;
else
l:=LexicographicTable(O);
#This must be an arrow, or we wouldn't be infinite
a:=l[Length(VerticesOfQuiver(O!.quiver))+1];
v:=SourceOfPath(a);
i:=ExtRepOfObj(v)[1];
if i<>ExtRepOfObj(TargetOfPath(a))[1] or InDegreeOfVertex(v)>1 then
return false;
fi;
m:=AdjacencyMatrixOfQuiver(O!.quiver);
m[i][i]:=0;
ret:=IsFinite(Quiver(m));
m[i][i]:=1;
return ret;
fi;
end
);
InstallMethod(IsWellSubset,
"for a lexicographic ordering and a list of generators",
true,
[IsLexicographicOrdering,IsHomogeneousList],0,
function(O,L)
local h,n,a,b,i,r,lgst,lgst_lex,visit;
#Possibly a big shortcut
if HasIsAcyclicQuiver(O!.quiver) and IsAcyclicQuiver(O!.quiver) then
return true;
fi;
#Identify every arrow in the list, as well as every vertex we
#can start from, and the largest arrow
h:=[];
for a in L do
if IsArrow(a) then
i:=ExtRepOfObj(a)[1];
h[i]:=a;
if not IsBound(lgst) or
lgst_lex<O!.lex[i] then
lgst:=a;
lgst_lex:=O!.lex[i];
fi;
b:=SourceOfPath(a);
h[ExtRepOfObj(b)[1]]:=b;
fi;
od;
#If we have some arrows
if IsBound(lgst) then
#The largest arrow may appear in cycles
Unbind(h[ExtRepOfObj(lgst)[1]]);
n:=[];
i:=1;
visit:=#Visit a vertex
#v is the vertex
#j is 3 * the generator position of the vertex
#p is the 3 * the generator position of the vertex's parent, or -1
#c is the label of the source vertex for the last arrow which was a parent
#n[j] = the depth-first search label of the vertex
#n[j-1] = -1: being visited, -2: and has cycle, 1: done being visited, 2: and has cycle
#n[j-2] = index of the highest vertex reachable from cycles containing this vertex
function(v,j,c)
local adj,k,t,p,m;
n[j]:=i; #Label the vertex
n[j-1]:=-1; #Mark us as being visited
i:=i+1;
#Check all the arrows
adj:=OutgoingArrowsOfVertex(v);
for p in adj do
t:=TargetOfPath(p);
k:=ExtRepOfObj(t)[1]*3;
#Arrow is inside our subset, and not the largest
if IsBound(h[ExtRepOfObj(p)[1]]) then
#Arrow points to an unvisited vertex
if not IsBound(n[k]) then
if not visit(t,k,n[j]) then
return false;
fi;
#Arrow points to the largest arrow and largest arrow belongs to a cycle
#Or the vertex can reach us
#Or the vertex is part of a cycle that reaches us
elif (n[k]=1 and n[k-1]=2) or n[k-1]<0 or
(IsBound(n[k-2]) and n[n[k-2]-1]<0) then
return false;
fi;
#Arrow is outside our subset, or the largest
else
#Arrow points to an unvisited vertex
if not IsBound(n[k]) then
if p=lgst then
if not visit(t,k,-1) then
return false;
fi;
else
if not visit(t,k,c) then
return false;
fi;
fi;
if IsBound(n[k-2]) and (n[n[k-2]-1]<0) and
((not IsBound(n[j-2])) or n[n[j-2]]>n[n[k-2]]) then
n[j-2]:=n[k-2];
fi;
#The vertex can possibly reach us
elif n[k-1]<0 or
(IsBound(n[k-2]) and n[n[k-2]-1]<0) then
if IsBound(n[k-2]) then
m:=n[k-2];
else
m:=k;
fi;
#The cycle contains something from our set
if n[m]<=c then
return false;
#The cycle is outside our set
elif (not IsBound(n[j-2])) or n[n[j-2]]>n[m] then
n[j-2]:=m;
fi;
#The cycle descends directly from the largest arrow
if c<0 or p=lgst then
n[m-1]:=-2;
fi;
fi;
fi;
od;
n[j-1]:=-n[j-1]; #Mark us as done being visited
return true;
end;
#Visit source of largest arrow first
b:=SourceOfPath(lgst);
r:=ExtRepOfObj(b)[1]*3;
if not visit(b,r,0) then
return false;
fi;
#Visit any unconnected components reachable from our subset
for b in h do
if not IsQuiverVertex(b) then
break;
fi;
r:=ExtRepOfObj(b)[1]*3;
if not IsBound(n[r]) then
if not visit(b,r,0) then
return false;
fi;
fi;
od;
fi;
return true;
end
);
InstallMethod(IsWellReversedSubset,
"for a lexicographic ordering and a list of generators",
true,
[IsLexicographicOrdering,IsHomogeneousList],0,
function(O,L)
local h,n,a,b,i,r,lgst,lgst_lex,visit;
#Possibly a big shortcut
if HasIsAcyclicQuiver(O!.quiver) and IsAcyclicQuiver(O!.quiver) then
return true;
fi;
#Identify every arrow in the list, as well as every vertex we
#can start from, and the largest arrow
h:=[];
for a in L do
if IsArrow(a) then
i:=ExtRepOfObj(a)[1];
h[i]:=a;
if not IsBound(lgst) or
lgst_lex>O!.lex[i] then
lgst:=a;
lgst_lex:=O!.lex[i];
fi;
b:=SourceOfPath(a);
h[ExtRepOfObj(b)[1]]:=b;
fi;
od;
#If we have some arrows
if IsBound(lgst) then
#The largest arrow may appear in cycles
Unbind(h[ExtRepOfObj(lgst)[1]]);
n:=[];
i:=1;
visit:=#Visit a vertex
#v is the vertex
#j is 3 * the generator position of the vertex
#p is the 3 * the generator position of the vertex's parent, or -1
#c is the label of the source vertex for the last arrow which was a parent
#n[j] = the depth-first search label of the vertex
#n[j-1] = -1: being visited, -2: and has cycle, 1: done being visited, 2: and has cycle
#n[j-2] = index of the highest vertex reachable from cycles containing this vertex
function(v,j,c)
local adj,k,t,p,m;
n[j]:=i; #Label the vertex
n[j-1]:=-1; #Mark us as being visited
i:=i+1;
#Check all the arrows
adj:=OutgoingArrowsOfVertex(v);
for p in adj do
t:=TargetOfPath(p);
k:=ExtRepOfObj(t)[1]*3;
#Arrow is inside our subset, and not the largest
if IsBound(h[ExtRepOfObj(p)[1]]) then
#Arrow points to an unvisited vertex
if not IsBound(n[k]) then
if not visit(t,k,n[j]) then
return false;
fi;
#Arrow points to the largest arrow and largest arrow belongs to a cycle
#Or the vertex can reach us
#Or the vertex is part of a cycle that reaches us
elif (n[k]=1 and n[k-1]=2) or n[k-1]<0 or
(IsBound(n[k-2]) and n[n[k-2]-1]<0) then
return false;
fi;
#Arrow is outside our subset, or the largest
else
#Arrow points to an unvisited vertex
if not IsBound(n[k]) then
if p=lgst then
if not visit(t,k,-1) then
return false;
fi;
else
if not visit(t,k,c) then
return false;
fi;
fi;
if IsBound(n[k-2]) and (n[n[k-2]-1]<0) and
((not IsBound(n[j-2])) or n[n[j-2]]>n[n[k-2]]) then
n[j-2]:=n[k-2];
fi;
#The vertex can possibly reach us
elif n[k-1]<0 or
(IsBound(n[k-2]) and n[n[k-2]-1]<0) then
if IsBound(n[k-2]) then
m:=n[k-2];
else
m:=k;
fi;
#The cycle contains something from our set
if n[m]<=c then
return false;
#The cycle is outside our set
elif (not IsBound(n[j-2])) or n[n[j-2]]>n[m] then
n[j-2]:=m;
fi;
#The cycle descends directly from the largest arrow
if c<0 or p=lgst then
n[m-1]:=-2;
fi;
fi;
fi;
od;
n[j-1]:=-n[j-1]; #Mark us as done being visited
return true;
end;
#Visit source of largest arrow first
b:=SourceOfPath(lgst);
r:=ExtRepOfObj(b)[1]*3;
if not visit(b,r,0) then
return false;
fi;
#Visit any unconnected components reachable from our subset
for b in h do
if not IsQuiverVertex(b) then
break;
fi;
r:=ExtRepOfObj(b)[1]*3;
if not IsBound(n[r]) then
if not visit(b,r,0) then
return false;
fi;
fi;
od;
fi;
return true;
end
);
InstallMethod(IsTotalSubset,
"for a lexicographic ordering and a list of generators",
true,
[IsLexicographicOrdering,IsHomogeneousList],0,
function(O,L)
return true;
end);
InstallGlobalFunction(LeftLexicographicOrdering,function(arg)
local fam,O,Q,lex,i,j,rep,gens,oldgens;
if not (Length(arg)=1 or (Length(arg)=2 and IsHomogeneousList(arg[2])) and IsQuiver(arg[1])) then
Error("usage: LeftLexicographicOrdering(Q,L), Q must be q quiver, L is an optional list of gens");
fi;
fam:=NewFamily("FamilyLeftLexicographicOrderings",
IsLeftLexicographicOrdering);
O:=Objectify(NewType(fam,IsLeftLexicographicOrdering and
IsAttributeStoringRep),rec());
Q:=arg[1];
O!.quiver:=Q;
oldgens:=GeneratorsOfQuiver(Q);
lex:=[];
gens:=[];
j:=1;
if Length(arg)>=2 then
for i in arg[2] do
if IsQuiverVertex(i) then
rep:=ExtRepOfObj(i)[1];
if not IsBound(lex[rep]) then
lex[rep]:=j;
j:=j+1;
Add(gens,i);
fi;
fi;
od;
fi;
if Length(VerticesOfQuiver(Q))>=j then
for i in oldgens do
if not IsQuiverVertex(i) then
break;
fi;
rep:=ExtRepOfObj(i)[1];
if not IsBound(lex[rep]) then
lex[rep]:=j;
j:=j+1;
Add(gens,i);
fi;
od;
fi;
if Length(arg)>=2 then
for i in arg[2] do
if IsArrow(i) then
rep:=ExtRepOfObj(i)[1];
if not IsBound(lex[rep]) then
lex[rep]:=j;
j:=j+1;
Add(gens,i);
fi;
fi;
od;
fi;
if Length(oldgens)>=j then
for i in [Length(VerticesOfQuiver(Q))+1..Length(oldgens)] do
rep:=ExtRepOfObj(oldgens[i])[1];
if not IsBound(lex[rep]) then
lex[rep]:=j;
j:=j+1;
Add(gens,oldgens[i]);
fi;
od;
fi;
SetOrderingName(O,"left lexicographic");
SetLexicographicTable(O,gens);
O!.lex:=lex;
SetComparisonFunction(O,function(a,b)
local m,n,l,r,s,j;
if IsZeroPath(a) then
if IsZeroPath(b) then
return 0;
else
return -1;
fi;
elif IsZeroPath(b) then
return 1;
fi;
r:=ExtRepOfObj(a); # remember, these are paths
s:=ExtRepOfObj(b);
m:=Length(r);
n:=Length(s);
l:=Minimum(m, n);
for j in [1..l] do
if lex[r[j]]<>lex[s[j]] then
if lex[r[j]]<lex[s[j]] then
return -1;
else
return 1;
fi;
fi;
od;
if m<n then
return -1;
elif m=n then
if HasNextOrdering(O) then
return ComparisonFunction(NextOrdering(O))(a,b);
else
return 0;
fi;
else
return 1;
fi;
end);
return O;
end
);
InstallGlobalFunction(RightLexicographicOrdering,function(arg)
local fam,O,Q,lex,i,j,rep,gens,oldgens;
if not (Length(arg)=1 or (Length(arg)=2 and IsHomogeneousList(arg[2])) and IsQuiver(arg[1])) then
Error("usage: RightLexicographicOrdering(Q,L), Q must be q quiver, L is an optional list of gens");
fi;
fam:=NewFamily("FamilyRightLexicographicOrderings",
IsRightLexicographicOrdering);
O:=Objectify(NewType(fam,IsRightLexicographicOrdering and
IsAttributeStoringRep),rec());
Q:=arg[1];
O!.quiver:=Q;
oldgens:=GeneratorsOfQuiver(Q);
lex:=[];
gens:=[];
j:=1;
if Length(arg)>=2 then
for i in arg[2] do
if IsQuiverVertex(i) then
rep:=ExtRepOfObj(i)[1];
if not IsBound(lex[rep]) then
lex[rep]:=j;
j:=j+1;
Add(gens,i);
fi;
fi;
od;
fi;
if Length(VerticesOfQuiver(Q))>=j then
for i in oldgens do
if not IsQuiverVertex(i) then
break;
fi;
rep:=ExtRepOfObj(i)[1];
if not IsBound(lex[rep]) then
lex[rep]:=j;
j:=j+1;
Add(gens,i);
fi;
od;
fi;
if Length(arg)>=2 then
for i in arg[2] do
if IsArrow(i) then
rep:=ExtRepOfObj(i)[1];
if not IsBound(lex[rep]) then
lex[rep]:=j;
j:=j+1;
Add(gens,i);
fi;
fi;
od;
fi;
if Length(oldgens)>=j then
for i in [Length(VerticesOfQuiver(Q))+1..Length(oldgens)] do
rep:=ExtRepOfObj(oldgens[i])[1];
if not IsBound(lex[rep]) then
lex[rep]:=j;
j:=j+1;
Add(gens,oldgens[i]);
fi;
od;
fi;
SetOrderingName(O,"right lexicographic");
SetLexicographicTable(O,gens);
O!.lex:=lex;
SetComparisonFunction(O,function(a,b)
local m,n,l,r,s,j;
if IsZeroPath(a) then
if IsZeroPath(b) then
return 0;
else
return -1;
fi;
elif IsZeroPath(b) then
return 1;
fi;
r:=ExtRepOfObj(a); # remember, these are paths
s:=ExtRepOfObj(b);
m:=Length(r);
n:=Length(s);
l:=Minimum(m, n);
for j in [0..l-1] do
if lex[r[m-j]]<>lex[s[n-j]] then
if lex[r[m-j]]<lex[s[n-j]] then
return -1;
else
return 1;
fi;
fi;
od;
if m<n then
return -1;
elif m=n then
if HasNextOrdering(O) then
return ComparisonFunction(NextOrdering(O))(a,b);
else
return 0;
fi;
else
return 1;
fi;
end);
SetIsTotal(O,true);
return O;
end
);
InstallGlobalFunction(ReverseOrdering,function(arg)
local fam,O;
if not (Length(arg)=2 and IsQuiverOrdering(arg[2]) and IsQuiver(arg[1])) then
Error("Usage: ReverseOrdering(Q,O) where Q is a quiver and O is an ordering");
fi;
fam:=NewFamily("FamilyReverseOrderings",IsReverseOrdering);
O:=Objectify(NewType(fam,IsReverseOrdering and IsAttributeStoringRep),
rec());
O!.quiver:=arg[1];
SetOrderingName(O,"reverse");
SetNextOrdering(O,arg[2]);
if HasLexicographicTable(arg[2]) then
SetLexicographicTable(O,LexicographicTable(arg[2]));
O!.lex:=arg[2]!.lex;
fi;
SetComparisonFunction(O,function(a,b)
local ret;
if IsZeroPath(a) then
if IsZeroPath(b) then
return 0;
else
return ComparisonFunction(NextOrdering(O))(a,b);
fi;
elif IsZeroPath(b) then
return ComparisonFunction(NextOrdering(O))(a,b);
fi;
if IsQuiverVertex(a) then
if not IsQuiverVertex(b) then
return ComparisonFunction(NextOrdering(O))(a,b);
fi;
elif IsQuiverVertex(b) then
return ComparisonFunction(NextOrdering(O))(a,b);
fi;
return -ComparisonFunction(NextOrdering(O))(a,b);
end);
return O;
end
);
InstallMethod(IsWellOrdering,
"for a reverse ordering and a quiver",
true,
[IsReverseOrdering],0,
function(O)
return IsWellReversedOrdering(NextOrdering(O));
end
);
InstallMethod(IsWellReversedOrdering,
"for a reverse ordering and a quiver",
true,
[IsReverseOrdering],0,
function(O)
return IsWellOrdering(NextOrdering(O));
end
);
InstallMethod(IsTotalOrdering,
"for a reverse ordering",
true,
[IsReverseOrdering],0,
function(O)
return IsTotalOrdering(NextOrdering(O));
end
);
InstallMethod(IsWellSubset,
"for a reverse ordering and a list of generators",
true,
[IsReverseOrdering,IsHomogeneousList],0,
function(O,L)
return IsWellReversedSubset(NextOrdering(O),L);
end
);
InstallMethod(IsWellReversedSubset,
"for a reverse ordering and a list of generators",
true,
[IsReverseOrdering,IsHomogeneousList],0,
function(O,L)
return IsWellSubset(NextOrdering(O),L);
end
);
InstallMethod(IsTotalSubset,
"for a reverse ordering and a list of generators",
true,
[IsReverseOrdering,IsHomogeneousList],0,
function(O,L)
return IsTotalSubset(NextOrdering(O),L);
end
);
InstallMethod(IsWellReversedOrdering,
"for a vector ordering",
true,
[IsVectorOrdering],0,
function(O)
return IsFinite(O!.quiver);
end
);
InstallMethod(IsTotalOrdering,
"for a vector ordering",
true,
[IsVectorOrdering],0,
function(O)
if Length(VerticesOfQuiver(O!.quiver))<1 then
return true;
elif HasNextOrdering(O) then
return IsTotalOrdering(NextOrdering(O));
else
return false;
fi;
end
);
InstallMethod(IsWellSubset,
"for a vector ordering and a list of generators",
true,
[IsVectorOrdering,IsHomogeneousList],0,
function(O,L)
return true;
end
);
InstallMethod(IsWellReversedSubset,
"for a vector ordering and a list of generators",
true,
[IsVectorOrdering,IsHomogeneousList],0,
function(O,L)
return CheckQuiverSubsetForCycles(O!.quiver,L);
end
);
InstallMethod(IsTotalSubset,
"for a vector ordering and a list of generators",
true,
[IsVectorOrdering,IsHomogeneousList],0,
function(O,L)
if Length(L)<1 then
return true;
elif HasNextOrdering(O) then
return IsTotalSubset(NextOrdering(O),L);
else
return false;
fi;
end
);
InstallGlobalFunction(LeftVectorOrdering,function(arg)
local fam,O,Q,lex,i,j,rep,gens,oldgens;
if not (Length(arg)=1 or (Length(arg)=2 or (Length(arg)=3 and
IsQuiverOrdering(arg[3])) and IsHomogeneousList(arg[2])) and IsQuiver(arg[1]))
then
Error("usage: LeftVectorOrdering(Q,L,O), the first arg must be a quiver, the second a list of generators, and the optional third argument an ordering");
fi;
fam:=NewFamily("FamilyLeftVectorOrderings",IsLeftVectorOrdering);
O:=Objectify(NewType(fam,IsLeftVectorOrdering and IsAttributeStoringRep),
rec());
Q:=arg[1];
O!.quiver:=Q;
if Length(arg)>=3 and HasLexicographicTable(arg[3]) then
oldgens:=LexicographicTable(arg[3]);
else
oldgens:=GeneratorsOfQuiver(Q);
fi;
lex:=[];
gens:=[];
j:=1;
if Length(arg)>=2 then
for i in arg[2] do
if IsQuiverVertex(i) then
rep:=ExtRepOfObj(i)[1];
if not IsBound(lex[rep]) then
lex[rep]:=j;
j:=j+1;
Add(gens,i);
fi;
fi;
od;
fi;
if Length(VerticesOfQuiver(Q))>=j then
for i in oldgens do
if not IsQuiverVertex(i) then
break;
fi;
rep:=ExtRepOfObj(i)[1];
if not IsBound(lex[rep]) then
lex[rep]:=j;
j:=j+1;
Add(gens,i);
fi;
od;
fi;
if Length(arg)>=2 then
for i in arg[2] do
if IsArrow(i) then
rep:=ExtRepOfObj(i)[1];
if not IsBound(lex[rep]) then
lex[rep]:=j;
j:=j+1;
Add(gens,i);
fi;
fi;
od;
fi;
if Length(oldgens)>=j then
for i in [Length(VerticesOfQuiver(Q))+1..Length(oldgens)] do
rep:=ExtRepOfObj(oldgens[i])[1];
if not IsBound(lex[rep]) then
lex[rep]:=j;
j:=j+1;
Add(gens,oldgens[i]);
fi;
od;
fi;
if Length(arg)>=3 then
SetNextOrdering(O,arg[3]);
if HasLexicographicTable(arg[3]) then
if LexicographicTable(arg[3])<>gens then
Error("Must use same lexicographic table");
fi;
O!.lex:=arg[3]!.lex;
SetLexicographicTable(O,LexicographicTable(arg[3]));
else
O!.lex:=lex;
SetLexicographicTable(O,gens);
fi;
else
O!.lex:=lex;
SetLexicographicTable(O,gens);
fi;
SetOrderingName(O,"left vector");
SetComparisonFunction(O,function(a,b)
local v,w,r,s,i,j,o;
if IsQuiverVertex(a) or IsZeroPath(a) then
if IsQuiverVertex(b) or IsZeroPath(b) then
if HasNextOrdering(O) then
return ComparisonFunction(NextOrdering(O))(a,b);
else
return 0;
fi;
else
return -1;
fi;
elif IsQuiverVertex(b) or IsZeroPath(b) then
return 1;
fi;
# At this point, both items are paths
o:=Length(VerticesOfQuiver(O!.quiver));
v:=ListWithIdenticalEntries(Length(gens)-o,0);
r:=ExtRepOfObj(a);
for i in [1..Length(r)] do
j:=lex[r[i]]-o;
v[j]:=v[j]+1;
od;
w:=ListWithIdenticalEntries(Length(gens)-o,0);
s:=ExtRepOfObj(b);
for i in [1..Length(s)] do
j:=lex[s[i]]-o;
w[j]:=w[j]+1;
od;
for i in [1..Length(v)] do
if v[i]<w[i] then
return -1;
elif v[i]>w[i] then
return 1;
fi;
od;
if HasNextOrdering(O) then
return ComparisonFunction(NextOrdering(O))(a,b);
else
return 0;
fi;
end);
return O;
end
);
InstallGlobalFunction(RightVectorOrdering,function(arg)
local fam,O,Q,lex,i,j,rep,gens,oldgens;
if not (Length(arg)=1 or (Length(arg)=2 or (Length(arg)=3 and
IsQuiverOrdering(arg[3])) and IsHomogeneousList(arg[2])) and IsQuiver(arg[1]))
then
Error("usage: RightVectorOrdering(Q,L,O), the first arg must be a quiver, the second a list of generators, and the optional third argument an ordering");
fi;
fam:=NewFamily("FamilyRightVectorOrderings",IsRightVectorOrdering);
O:=Objectify(NewType(fam,IsRightVectorOrdering and IsAttributeStoringRep),
rec());
Q:=arg[1];
O!.quiver:=Q;
if Length(arg)>=3 and HasLexicographicTable(arg[3]) then
oldgens:=LexicographicTable(arg[3]);
else
oldgens:=GeneratorsOfQuiver(Q);
fi;
lex:=[];
gens:=[];
j:=1;
if Length(arg)>=2 then
for i in arg[2] do
if IsQuiverVertex(i) then
rep:=ExtRepOfObj(i)[1];
if not IsBound(lex[rep]) then
lex[rep]:=j;
j:=j+1;
Add(gens,i);
fi;
fi;
od;
fi;
if Length(VerticesOfQuiver(Q))>=j then
for i in oldgens do
if not IsQuiverVertex(i) then
break;
fi;
rep:=ExtRepOfObj(i)[1];
if not IsBound(lex[rep]) then
lex[rep]:=j;
j:=j+1;
Add(gens,i);
fi;
od;
fi;
if Length(arg)>=2 then
for i in arg[2] do
if IsArrow(i) then
rep:=ExtRepOfObj(i)[1];
if not IsBound(lex[rep]) then
lex[rep]:=j;
j:=j+1;
Add(gens,i);
fi;
fi;
od;
fi;
if Length(oldgens)>=j then
for i in [Length(VerticesOfQuiver(Q))+1..Length(oldgens)] do
rep:=ExtRepOfObj(oldgens[i])[1];
if not IsBound(lex[rep]) then
lex[rep]:=j;
j:=j+1;
Add(gens,oldgens[i]);
fi;
od;
fi;
if Length(arg)>=3 then
SetNextOrdering(O,arg[3]);
if HasLexicographicTable(arg[3]) then
if LexicographicTable(arg[3])<>gens then
Error("Must use same lexicographic table");
fi;
O!.lex:=arg[3]!.lex;
SetLexicographicTable(O,LexicographicTable(arg[3]));
else
O!.lex:=lex;
SetLexicographicTable(O,gens);
fi;
else
O!.lex:=lex;
SetLexicographicTable(O,gens);
fi;
SetOrderingName(O,"right vector");
SetComparisonFunction(O,function(a,b)
local v,w,r,s,i,j,l,o;
if IsQuiverVertex(a) or IsZeroPath(a) then
if IsQuiverVertex(b) or IsZeroPath(b) then
if HasNextOrdering(O) then
return ComparisonFunction(NextOrdering(O))(a,b);
else
return 0;
fi;
else
return -1;
fi;
elif IsQuiverVertex(b) or IsZeroPath(b) then
return 1;
fi;
# At this point, both items are paths
o:=Length(VerticesOfQuiver(O!.quiver));
v:=ListWithIdenticalEntries(Length(gens)-o,0);
r:=ExtRepOfObj(a);
for i in [1..Length(r)] do
j:=lex[r[i]]-o;
v[j]:=v[j]+1;
od;
w:=ListWithIdenticalEntries(Length(gens)-o,0);
s:=ExtRepOfObj(b);
for i in [1..Length(s)] do
j:=lex[s[i]]-o;
w[j]:=w[j]+1;
od;
l:=Length(v);
for i in [0..l-1] do
if v[l-i]<w[l-i] then
return -1;
elif v[l-i]>w[l-i] then
return 1;
fi;
od;
if HasNextOrdering(O) then
return ComparisonFunction(NextOrdering(O))(a,b);
else
return 0;
fi;
end);
return O;
end
);
InstallGlobalFunction(WeightOrdering,function(arg)
local fam,O,Q,weight,i,j,rep,gens,p;
if not (Length(arg)=1 or (Length(arg)=2 or (Length(arg)=3 and
IsQuiverOrdering(arg[3])) and IsHomogeneousList(arg[2])) and IsQuiver(arg[1]))
then
Error("usage: WeightOrdering(Q,L,O), the first arg must be a quiver, the second a list of weights, one for each arrow in the quiver, and the optional third argument an ordering");
fi;
fam:=NewFamily("FamilyWeightOrderings",IsWeightOrdering);
O:=Objectify(NewType(fam,IsWeightOrdering and IsAttributeStoringRep),
rec());
Q:=arg[1];
O!.quiver:=Q;
weight:=ListWithIdenticalEntries(Length(ArrowsOfQuiver(Q)),0);
if Length(arg)>=2 and Length(arg[2])>0 then
for p in [1..Length(arg[2])] do
weight[p]:=arg[2][p];
od;
fi;
O!.weight:=weight;
if Length(arg)>=3 then
SetNextOrdering(O,arg[3]);
if HasLexicographicTable(arg[3]) then
SetLexicographicTable(O,LexicographicTable(arg[3]));
O!.lex:=arg[3]!.lex;
fi;
fi;
SetOrderingName(O,"weight");
SetComparisonFunction(O,function(a,b)
local v,w,r,s,i,o;
if IsQuiverVertex(a) or IsZeroPath(a) then
if IsQuiverVertex(b) or IsZeroPath(b) then
if HasNextOrdering(O) then
return ComparisonFunction(NextOrdering(O))(a,b);
else
return 0;
fi;
else
return -1;
fi;
elif IsQuiverVertex(b) or IsZeroPath(b) then
return 1;
fi;
# At this point, both items are paths
o:=Length(VerticesOfQuiver(O!.quiver));
r:=ExtRepOfObj(a);
s:=ExtRepOfObj(b);
w:=0;
for i in r do
w:=w+weight[i-o];
od;
v:=0;
for i in s do
v:=v+weight[i-o];
od;
if w=v then
if HasNextOrdering(O) then
return ComparisonFunction(NextOrdering(O))(a,b);
else
return 0;
fi;
else
return w-v;
fi;
end);
return O;
end
);
InstallMethod(IsWellReversedOrdering,
"for a weight ordering",
true,
[IsWeightOrdering],0,
function(O)
local z,o;
if IsFinite(O!.quiver) then
return true;
fi;
o:=Length(VerticesOfQuiver(O!.quiver));
z:=Filtered(ArrowsOfQuiver(O!.quiver),function(a)
return O!.weight[ExtRepOfObj(a)[1]-o]<>0;
end);
if Length(z)>0 and not CheckQuiverSubsetForCycles(O!.quiver,z) then
return false;
fi;
return not HasNextOrdering(O) or
IsWellReversedSubset(NextOrdering(O),z);
end
);
InstallMethod(IsTotalOrdering,
"for a weight ordering",
true,
[IsWeightOrdering],0,
function(O)
if Length(VerticesOfQuiver(O!.quiver))<1 then
return true;
elif HasNextOrdering(O) then
return IsTotalOrdering(NextOrdering(O));
else
return true;
fi;
end
);
InstallMethod(IsWellSubset,
"for a weight ordering and a list of generators",
true,
[IsWeightOrdering,IsHomogeneousList],0,
function(O,L)
return true;
end
);
InstallMethod(IsWellReversedSubset,
"for a weight ordering and a list of generators",
true,
[IsWeightOrdering,IsHomogeneousList],0,
function(O,L)
local z,o;
if HasIsAcyclicQuiver(O!.quiver) and IsAcyclicQuiver(O!.quiver) then
return true;
fi;
o:=Length(VerticesOfQuiver(O!.quiver));
z:=Filtered(L,function(a)
return IsArrow(a) and O!.weight[ExtRepOfObj(a)[1]-o]<>0;
end);
if Length(z)>0 and not CheckQuiverSubsetForCycles(O!.quiver,z) then
return false;
fi;
z:=Filtered(L,function(a)
return IsArrow(a) and O!.weight[ExtRepOfObj(a)[1]-o]=0;
end);
if Length(z)>0 and not CheckQuiverSubsetForCycles(O!.quiver,z) then
return not HasNextOrdering(O) or
IsWellReversedSubset(NextOrdering(O),z);
fi;
return true;
end
);
InstallMethod(IsTotalSubset,
"for a weight ordering and a list of generators",
true,
[IsWeightOrdering,IsHomogeneousList],0,
function(O,L)
if Length(L)<1 or
(Length(L)=1 and IsArrow(L[1]) and
O!.weight[ExtRepOfObj(L[1])[1]-
Length(VerticesOfQuiver(O!.quiver))]<>0) then
return true;
elif HasNextOrdering(O) then
return IsTotalSubset(NextOrdering(O,L));
else
return true;
fi;
end
);
DeclareOperation("PathFromArrowList",[IsQuiver,IsHomogeneousList]);
InstallMethod(PathFromArrowList,
"for a list of arrows",
true,
[IsQuiver,IsHomogeneousList],0,
function(Q,L)
local ret;
if Length(L)<1 then
return Zero(Q);
elif Length(L)=1 then
return L[1]; #This handles vertices, too
else
ret:=Objectify(NewType(FamilyObj(Q),
IsPath and IsAttributeStoringRep),
rec());
SetSourceOfPath(ret,SourceOfPath(L[1]));
SetTargetOfPath(ret,TargetOfPath(L[Length(L)]));
SetLengthOfPath(ret,Length(L));
SetWalkOfPath(ret,L);
SetIsZeroPath(ret,false);
return ret;
fi;
end
);
DeclareOperation("CompareArrowLists",[IsQuiverOrdering,IsHomogeneousList,IsHomogeneousList]);
InstallMethod(CompareArrowLists,
"for an ordering and two lists of arrows",
true,
[IsQuiverOrdering,IsHomogeneousList,IsHomogeneousList],0,
function(O,a,b)
return ComparisonFunction(O)(PathFromArrowList(O!.quiver,a),
PathFromArrowList(O!.quiver,b));
end
);
InstallGlobalFunction(BlockOrdering,function(arg)
local fam,O,Q,L,block,orders,i,j,rep;
if not (Length(arg)=1 or (Length(arg)=2 or (Length(arg)=3 and
IsQuiverOrdering(arg[3])) and IsHomogeneousList(arg[2])) and IsQuiver(arg[1]))
then
Error("usage: BlockOrdering(Q,L,O), the first arg must be a quiver, the second a list of [ordering,[generator list]] pairs, and the optional third argument an ordering");
fi;
L:=arg[2];
if Length(L)<1 then
Error("BlockOrdering: Subset list cannot be empty");
fi;
fam:=NewFamily("FamilyBlockOrderings",IsBlockOrdering);
O:=Objectify(NewType(fam,IsBlockOrdering and IsAttributeStoringRep),
rec());
Q:=arg[1];
O!.quiver:=Q;
block:=[];
orders:=[];
L:=Flat(L);
i:=1;
while i<Length(L) do
if not IsQuiverOrdering(L[i]) then
Error("Second argument must be a list of [ordering,[generator list]] pairs");
fi;
Add(orders,L[i]);
if HasLexicographicTable(L[i]) then
if HasLexicographicTable(O) then
if LexicographicTable(O)<>LexicographicTable(L[i]) then
Error("Conflicting lexicographic tables");
fi;
else
SetLexicographicTable(O,LexicographicTable(L[i]));
O!.lex:=L[i]!.lex;
fi;
fi;
i:=i+1;
while i<Length(L) do
if (not IsArrow(L[i])) and (not IsQuiverVertex(L[i])) then
break;
fi;
block[ExtRepOfObj(L[i])[1]]:=Length(orders);
i:=i+1;
od;
od;
L:=Length(GeneratorsOfQuiver(Q));
if L>0 then
for i in [1..L] do
if not IsBound(block[i]) then
block[i]:=Length(orders);
fi;
od;
fi;
O!.block:=block;
O!.orders:=orders;
if Length(arg)>=3 then
SetNextOrdering(O,arg[3]);
if HasLexicographicTable(arg[3]) then
if HasLexicographicTable(O) then
if LexicographicTable(O)<>LexicographicTable(arg[3]) then
Error("Conflicting lexicographic tables");
fi;
else
SetLexicographicTable(O,LexicographicTable(arg[3]));
O!.lex:=arg[3]!.lex;
fi;
fi;
fi;
SetOrderingName(O,"block");
SetComparisonFunction(O,function(a,b)
local ret,e,f,p,q,o,i,g;
o:=Length(O!.orders);
p:=[];
for i in [1..o] do
Add(p,[]);
od;
q:=StructuralCopy(p);
g:=GeneratorsOfQuiver(O!.quiver);
if not IsZeroPath(a) then
e:=ExtRepOfObj(a);
for i in e do
Add(p[block[i]],g[i]);
od;
fi;
if not IsZeroPath(b) then
f:=ExtRepOfObj(b);
for i in f do
Add(q[block[i]],g[i]);
od;
fi;
while o>0 do
ret:=CompareArrowLists(O!.orders[o],p[o],q[o]);
if ret<>0 then
return ret;
fi;
o:=o-1;
od;
if HasNextOrdering(O) then
return ComparisonFunction(NextOrdering(O))(a,b);
fi;
return 0;
end);
return O;
end
);
DeclareGlobalFunction("CheckBlocksForCycles");
InstallGlobalFunction(CheckBlocksForCycles,
function(O,block)
local i,r,n,visit;
#Possibly a big shortcut
if HasIsAcyclicQuiver(O!.quiver) and IsAcyclicQuiver(O!.quiver) then
return true;
fi;
n:=[];
i:=1;
#Visit a vertex
#v is the vertex
#j is 4 * the generator position of the vertex
#c is the label of the source vertex for the last arrow which transitioned blocks
#b is the current block number, or 0
#a is the label of the source vertex for highest previous 0 arrow in a row
#n[j] = the depth-first search label of the vertex
#n[j-1] = true: the vertex was visited successfully; false: vertex is being visited
#n[j-2] = index of the highest vertex reachable from cycles containing this vertex
#n[j-3] = the block number of any cycle this vertex belongs to, or 0
visit:=function(v,j,c,b,a)
local adj,k,t,p,d,e,f,m;
n[j]:=i;
n[j-1]:=true;
n[j-3]:=0;
i:=i+1;
#Check all the arrows
adj:=OutgoingArrowsOfVertex(v);
for p in adj do
t:=TargetOfPath(p);
k:=ExtRepOfObj(t)[1]*4;
#Look for block transition
e:=block[ExtRepOfObj(p)[1]];
if e>0 then
if b>0 and e<>b then
f:=a;
else
f:=c;
fi;
d:=i;
else
e:=b;
f:=c;
d:=a;
fi;
#Arrow points to an unvisited vertex
if not IsBound(n[k]) then
if not visit(t,k,f,e,d) then
return false;
#If it's part of a cycle that reaches us
elif IsBound(n[k-2]) and n[n[k-2]-1] then
#Mark how high we can reach
if (not IsBound(n[j-2])) or n[n[j-2]]>n[n[k-2]] then
n[j-2]:=n[k-2];
fi;
#Mark what block the cycle is in
if n[k-3]<>0 then
n[j-3]:=n[k-3];
fi;
fi;
#The vertex can reach us
elif n[k-1] or (IsBound(n[k-2]) and n[n[k-2]-1]) then
if IsBound(n[k-2]) then
m:=[k-2];
else
m:=k;
fi;
#The cycle contains something outside our block
if n[m]<f or (n[k-3]>0 and e>0 and n[k-3]<>e) then
return false;
#Mark us a belonging to the cycle
elif (not IsBound(n[j-2])) or n[n[j-2]]>n[m] then
n[j-2]:=m;
fi;
fi;
od;
n[j-1]:=false;
return true;
end;
for i in [1..Length(VerticesOfQuiver(O!.quiver))] do
if block[i]>0 then
r:=i*4;
if not IsBound(n[r]) then
if not visit(VerticesOfQuiver(O!.quiver)[i],r,0,0,0) then
return false;
fi;
fi;
fi;
od;
return true;
end
);
InstallMethod(IsTotalOrdering,
"for a block ordering",
true,
[IsBlockOrdering],0,
function(O)
local l,s,i,block;
l:=GeneratorsOfQuiver(O!.quiver);
s:=[];
block:=O!.block;
for i in [1..Length(O!.orders)] do
Add(s,[]);
od;
for i in l do
Add(s[block[ExtRepOfObj(i)[1]]],i);
od;
for i in [1..Length(O!.orders)] do
if not IsTotalSubset(O!.orders[i],s[i]) then
if HasNextOrdering(O) then
return IsTotalOrdering(NextOrdering(O));
else
return false;
fi;
fi;
od;
if Length(block)>0 then
if not CheckBlocksForCycles(O,block) then
if HasNextOrdering(O) then
return IsTotalOrdering(NextOrdering(O));
else
return false;
fi;
fi;
fi;
return true;
end
);
InstallMethod(IsWellSubset,
"for a block ordering and a list of generators",
true,
[IsBlockOrdering,IsHomogeneousList],0,
function(O,L)
local s,i,block;
s:=[];
block:=O!.block;
for i in [1..Length(O!.orders)] do
Add(s,[]);
od;
for i in L do
Add(s[block[ExtRepOfObj(i)[1]]],i);
od;
for i in [1..Length(O!.orders)] do
if not IsWellSubset(O!.orders[i],s[i]) then
return false;
fi;
od;
return true;
end
);
InstallMethod(IsWellReversedSubset,
"for a block ordering and a list of generators",
true,
[IsBlockOrdering,IsHomogeneousList],0,
function(O,L)
local s,i,block;
s:=[];
block:=O!.block;
for i in [1..Length(O!.orders)] do
Add(s,[]);
od;
for i in L do
Add(s[block[ExtRepOfObj(i)[1]]],i);
od;
for i in [1..Length(O!.orders)] do
if not IsWellReversedSubset(O!.orders[i],s[i]) then
return false;
fi;
od;
return true;
end
);
InstallMethod(IsTotalSubset,
"for a block ordering and a list of generators",
true,
[IsBlockOrdering,IsHomogeneousList],0,
function(O,L)
local l,s,i,j,block;
s:=[];
block:=ListWithIdenticalEntries(Length(O!.block),0);
for i in [1..Length(O!.orders)] do
Add(s,[]);
od;
for i in L do
if IsArrow(i) then
j:=ExtRepOfObj(SourceOfPath(i))[1];
block[j]:=O!.block[j];
fi;
j:=ExtRepOfObj(i)[1];
block[j]:=O!.block[j];
Add(s[block[j]],i);
od;
for i in [1..Length(O!.orders)] do
if not IsTotalSubset(O!.orders[i],s[i]) then
if HasNextOrdering(O) then
return IsTotalSubset(NextOrdering(O),L);
else
return false;
fi;
fi;
od;
if Length(block)>0 then
if not CheckBlocksForCycles(O,block) then
if HasNextOrdering(O) then
return IsTotalOrdering(NextOrdering(O));
else
return false;
fi;
fi;
fi;
return true;
end
);
InstallGlobalFunction(WreathOrdering,function(arg)
local fam,O,Q,L,block,orders,i,j,rep;
if not (Length(arg)=1 or (Length(arg)=2 or (Length(arg)=3 and
IsQuiverOrdering(arg[3])) and IsHomogeneousList(arg[2])) and IsQuiver(arg[1]))
then
Error("usage: WreathOrdering(Q,L,O), the first arg must be a quiver, the second a list of [ordering,[generator list]] pairs, and the optional third argument an ordering");
fi;
L:=arg[2];
if Length(L)<1 then
Error("WreathOrdering: Subset list cannot be empty");
fi;
fam:=NewFamily("FamilyWreathOrderings",IsWreathOrdering);
O:=Objectify(NewType(fam,IsWreathOrdering and IsAttributeStoringRep),
rec());
Q:=arg[1];
O!.quiver:=Q;
block:=[];
orders:=[];
L:=Flat(L);
i:=1;
while i<Length(L) do
if not IsQuiverOrdering(L[i]) then
Error("Second argument must be a list of [ordering,[generator list]] pairs");
fi;
Add(orders,L[i]);
if HasLexicographicTable(L[i]) then
if HasLexicographicTable(O) then
if LexicographicTable(O)<>LexicographicTable(L[i]) then
Error("Conflicting lexicographic tables");
fi;
else
SetLexicographicTable(O,LexicographicTable(L[i]));
O!.lex:=L[i]!.lex;
fi;
fi;
i:=i+1;
while i<Length(L) do
if (not IsArrow(L[i])) and (not IsQuiverVertex(L[i])) then
break;
fi;
block[ExtRepOfObj(L[i])[1]]:=Length(orders);
i:=i+1;
od;
od;
L:=Length(GeneratorsOfQuiver(Q));
if L>0 then
for i in [1..L] do
if not IsBound(block[i]) then
block[i]:=Length(orders);
fi;
od;
fi;
O!.block:=block;
O!.orders:=orders;
if Length(arg)>=3 then
SetNextOrdering(O,arg[3]);
if HasLexicographicTable(arg[3]) then
if HasLexicographicTable(O) then
if LexicographicTable(O)<>LexicographicTable(arg[3]) then
Error("Conflicting lexicographic tables");
fi;
else
SetLexicographicTable(O,LexicographicTable(arg[3]));
O!.lex:=arg[3]!.lex;
fi;
fi;
fi;
SetOrderingName(O,"wreath");
SetComparisonFunction(O,function(a,b)
local ret,e,f,o,s,t,i,j,c,d,p,q,m,n,x,y,g;
if IsZeroPath(a) then
e:=[];
else
e:=ExtRepOfObj(a);
fi;
if IsZeroPath(b) then
f:=[];
else
f:=ExtRepOfObj(b);
fi;
o:=1;
i:=Minimum(Length(e),Length(f));
# Skip equal elements
while o<=i do
if e[o]<>f[o] then
break;
fi;
o:=o+1;
od;
# If we skipped everything, the paths are identical
if o>Length(e) and o>Length(f) then
return 0;
fi;
g:=GeneratorsOfQuiver(O!.quiver);
s:=0;
m:=0;
p:=[];
c:=[];
x:=[];
if o<=Length(e) then
for i in [o..Length(e)] do
j:=block[e[i]];
if j>m then
s:=s+1;
m:=j;
Add(c,m);
Add(p,[g[e[i]]]);
elif j=m then
Add(p[s],g[e[i]]);
else
Add(x,g[e[i]]);
fi;
od;
fi;
t:=0;
n:=0;
q:=[];
d:=[];
y:=[];
if o<=Length(f) then
for i in [o..Length(f)] do
j:=block[f[i]];
if j>n then
t:=t+1;
n:=j;
Add(d,n);
Add(q,[g[f[i]]]);
elif j=n then
Add(q[t],g[f[i]]);
else
Add(y,g[f[i]]);
fi;
od;
fi;
while s>0 and t>0 do
if c[s]=d[t] then
ret:=CompareArrowLists(orders[c[s]],p[s],q[t]);
s:=s-1;
t:=t-1;
elif c[s]>d[t] then
ret:=CompareArrowLists(orders[c[s]],p[s],[]);
s:=s-1;
else
ret:=CompareArrowLists(orders[d[t]],[],q[t]);
t:=t-1;
fi;
if ret<>0 then
return ret;
fi;
od;
while s>0 do
ret:=CompareArrowLists(orders[c[s]],p[s],[]);
if ret<>0 then
return ret;
fi;
s:=s-1;
od;
while t>0 do
ret:=CompareArrowLists(orders[d[t]],[],q[t]);
if ret<>0 then
return ret;
fi;
t:=t-1;
od;
ret:=CompareArrowLists(O,x,y);
if ret=0 and HasNextOrdering(O) then
ret:=ComparisonFunction(NextOrdering(O))(a,b);
fi;
return ret;
end);
return O;
end
);
PrintOrdering := function(O)
local done;
done := false;
Print("<");
while not done do
if HasOrderingName(O) then
Print(OrderingName(O));
else
Print("unnamed");
fi;
Print(" ");
if HasNextOrdering(O) then
O := NextOrdering(O);
else
done := true;
fi;
od;
Print("ordering>");
end;
InstallMethod( ViewObj,
"for orderings",
true,
[IsQuiverOrdering], 0,
PrintOrdering
);
InstallMethod( PrintObj,
"for orderings",
true,
[IsQuiverOrdering], 0,
PrintOrdering
);
[ zur Elbe Produktseite wechseln0.86Quellennavigators
Analyse erneut starten
]
|
