|
#############################################################################
##
## orbits.gi
## Copyright (C) 2016-19 James D. Mitchell
##
## Licensing information can be found in the README file of this package.
##
#############################################################################
##
InstallGlobalFunction(DIGRAPHS_TraceSchreierVector,
function(gens, sch, r)
local word, w;
word := [];
w := sch[r];
while w > 0 do
Add(word, w);
r := r / gens[w];
w := sch[r];
od;
return rec(word := Reversed(word), representative := -w);
end);
InstallGlobalFunction(DIGRAPHS_EvaluateWord,
function(gens, word)
local out, i;
out := ();
for i in word do
out := out * gens[i];
od;
return out;
end);
# This is arranged like this in case we want to change the method in future,
# and also to allow its use **before** the creation of a digraph (such as when
# the group is given as an argument to the constructor).
InstallGlobalFunction(DIGRAPHS_Orbits,
function(G, domain)
local N, sch, orbs, lookup, gens, genstoapply, o, l, i, j, k;
N := Length(domain);
sch := [1 .. N] * 0;
orbs := [];
lookup := [];
gens := GeneratorsOfGroup(G);
genstoapply := [1 .. Length(gens)];
for i in domain do
if sch[i] = 0 then # new orbit
o := [i];
Add(orbs, o);
sch[i] := -Length(orbs);
lookup[i] := Length(orbs);
for j in o do
for k in genstoapply do
l := j ^ gens[k];
if sch[l] = 0 then # new point in the orbit
Add(o, l);
sch[l] := k;
lookup[l] := Length(orbs);
fi;
od;
od;
fi;
od;
return rec(orbits := orbs, schreier := sch, lookup := lookup);
end);
InstallGlobalFunction(DIGRAPHS_AddOrbitToHashMap,
function(G, set, act, hashmap)
local gens, o, im, pt, g;
gens := GeneratorsOfGroup(G);
o := [set];
Assert(1, not set in hashmap);
hashmap[set] := true;
for pt in o do
for g in gens do
im := act(pt, g);
if not im in hashmap then
hashmap[im] := true;
Add(o, im);
fi;
od;
od;
return o;
end);
InstallMethod(RepresentativeOutNeighbours, "for a digraph by out-neighbours",
[IsDigraphByOutNeighboursRep],
function(D)
local reps, out, nbs, i;
if IsTrivial(DigraphGroup(D)) then
return OutNeighbours(D);
fi;
reps := DigraphOrbitReps(D);
out := EmptyPlist(Length(reps));
nbs := OutNeighbours(D);
for i in [1 .. Length(reps)] do
out[i] := nbs[reps[i]];
od;
return out;
end);
BindGlobal("DIGRAPHS_DigraphGroup",
function(D)
if IsMultiDigraph(D) then
return Range(Projection(AutomorphismGroup(D), 1));
fi;
return AutomorphismGroup(D);
end);
InstallImmediateMethod(DigraphGroup, IsDigraph and HasAutomorphismGroup, 0,
DIGRAPHS_DigraphGroup);
InstallMethod(DigraphGroup, "for a digraph", [IsDigraph],
DIGRAPHS_DigraphGroup);
InstallMethod(DigraphOrbits, "for a digraph",
[IsDigraph],
function(D)
local record;
record := DIGRAPHS_Orbits(DigraphGroup(D),
DigraphVertices(D));
if IsImmutableDigraph(D) then
SetDigraphSchreierVector(D, record.schreier);
fi;
return record.orbits;
end);
InstallMethod(DigraphSchreierVector, "for a digraph",
[IsDigraph],
function(D)
local record;
record := DIGRAPHS_Orbits(DigraphGroup(D),
DigraphVertices(D));
if IsImmutableDigraph(D) then
SetDigraphOrbits(D, record.orbits);
fi;
return record.schreier;
end);
InstallMethod(DigraphOrbitReps, "for a digraph", [IsDigraph],
D -> List(DigraphOrbits(D), Representative));
InstallMethod(DigraphStabilizer, "for a digraph and a vertex",
[IsDigraph, IsPosInt],
function(D, v)
local pos, gens, sch, trace, word, stabs;
if v > DigraphNrVertices(D) then
ErrorNoReturn("the 2nd argument <v> must not exceed ",
DigraphNrVertices(D), ", the number of vertices of the ",
"digraph in the 1st argument <D>,");
fi;
pos := DigraphSchreierVector(D)[v];
if pos < 0 then # rep is one of the orbit reps
word := ();
pos := pos * -1;
else
gens := GeneratorsOfGroup(DigraphGroup(D));
sch := DigraphSchreierVector(D);
trace := DIGRAPHS_TraceSchreierVector(gens, sch, v);
pos := trace.representative;
word := DIGRAPHS_EvaluateWord(gens, trace.word);
fi;
stabs := DIGRAPHS_Stabilizers(D);
if not IsBound(stabs[pos]) then
stabs[pos] := Stabilizer(DigraphGroup(D), DigraphOrbitReps(D)[pos]);
fi;
return stabs[pos] ^ word;
end);
InstallMethod(DIGRAPHS_Stabilizers, "for a digraph", [IsDigraph], D -> []);
[ Dauer der Verarbeitung: 0.6 Sekunden
(vorverarbeitet)
]
|
