|
#############################################################################
##
## constructors.gi
## Copyright (C) 2019 James D. Mitchell
##
## Licensing information can be found in the README file of this package.
##
#############################################################################
##
# This file contains constructions of certain types of digraphs, from other
# digraphs.
InstallMethod(BipartiteDoubleDigraph, "for a mutable digraph by out-neighbours",
[IsMutableDigraph and IsDigraphByOutNeighboursRep],
function(D)
local list, N, i, j;
list := D!.OutNeighbours;
N := Length(list);
Append(list, List([1 .. N], x -> []));
for i in [1 .. N] do
for j in [1 .. Length(list[i])] do
list[i + N][j] := list[i][j];
list[i][j] := list[i][j] + N;
od;
od;
return D;
end);
InstallMethod(BipartiteDoubleDigraph, "for an immutable digraph",
[IsImmutableDigraph],
function(D)
local C, X, N, p;
C := MakeImmutable(BipartiteDoubleDigraph(DigraphMutableCopy(D)));
if HasDigraphGroup(D) then
X := GeneratorsOfGroup(DigraphGroup(D));
N := DigraphNrVertices(D);
p := PermList(Concatenation([1 .. N] + N, [1 .. N]));
X := List(X, x -> x * (x ^ p));
Add(X, p);
SetDigraphGroup(C, Group(X));
fi;
return C;
end);
InstallMethod(DoubleDigraph, "for a mutable digraph by out-neighbours",
[IsMutableDigraph and IsDigraphByOutNeighboursRep],
function(D)
local list, N, i, j;
list := D!.OutNeighbours;
N := Length(list);
Append(list, list + N);
for i in [1 .. N] do
for j in [1 .. Length(list[i])] do
Add(list[i + N], list[i][j]);
Add(list[i], list[i][j] + N);
od;
od;
return D;
end);
InstallMethod(DoubleDigraph, "for an immutable digraph",
[IsImmutableDigraph],
function(D)
local C, X, N, p;
C := MakeImmutable(DoubleDigraph(DigraphMutableCopy(D)));
if HasDigraphGroup(D) then
X := GeneratorsOfGroup(DigraphGroup(D));
N := DigraphNrVertices(D);
p := PermList(Concatenation([1 .. N] + N, [1 .. N]));
X := List(X, x -> x * (x ^ p));
Add(X, p);
SetDigraphGroup(C, Group(X));
fi;
return C;
end);
InstallMethod(DistanceDigraph,
"for a mutable digraph by out-neighbours and a list of distances",
[IsMutableDigraph and IsDigraphByOutNeighboursRep, IsList],
function(D, distances)
local list, x;
# Can't change D!.OutNeighbours in-place, since it is used by
# DigraphDistanceSet
list := EmptyPlist(DigraphNrVertices(D));
for x in DigraphVertices(D) do
list[x] := DigraphDistanceSet(D, x, distances);
od;
D!.OutNeighbours := list;
return D;
end);
InstallMethod(DistanceDigraph,
"for an immutable digraph and a list of distances",
[IsImmutableDigraph, IsList],
function(D, distances)
local list, G, o, rem, sch, gen, record, rep, g, C, x;
if HasDigraphGroup(D) and not IsTrivial(DigraphGroup(D)) then
list := EmptyPlist(DigraphNrVertices(D));
G := DigraphGroup(D);
o := DigraphOrbitReps(D);
for x in o do
list[x] := DigraphDistanceSet(D, x, distances);
od;
rem := Difference(DigraphVertices(D), o);
sch := DigraphSchreierVector(D);
gen := GeneratorsOfGroup(G);
for x in rem do
record := DIGRAPHS_TraceSchreierVector(gen, sch, x);
rep := o[record.representative];
g := DIGRAPHS_EvaluateWord(gen, record.word);
list[x] := List(list[rep], x -> x ^ g);
od;
C := DigraphNC(list);
else
C := MakeImmutable(DistanceDigraph(DigraphMutableCopy(D), distances));
fi;
SetDigraphGroup(C, DigraphGroup(D));
return C;
end);
InstallMethod(DistanceDigraph, "for a digraph and an integer",
[IsDigraph, IsInt],
function(D, distance)
if distance < 0 then
ErrorNoReturn("the 2nd argument <distance> must be a non-negative ",
"integer,");
fi;
return DistanceDigraph(D, [distance]);
end);
# Warning: unlike the other methods the next two do not change their arguments
# in place, and always return an immutable digraph. There is currently no
# method for creating a mutable digraph with 4 arguments, as required by the
# next two methods.
InstallMethod(LineDigraph, "for a digraph", [IsDigraph],
function(D)
local G, opt;
if HasDigraphGroup(D) then
G := DigraphGroup(D);
else
G := Group(());
fi;
if IsMutableDigraph(D) then
opt := IsMutableDigraph;
else
opt := IsImmutableDigraph;
fi;
return Digraph(opt,
G,
DigraphEdges(D),
OnPairs,
{x, y} -> x <> y and x[2] = y[1]);
end);
InstallMethod(LineUndirectedDigraph, "for a digraph", [IsDigraph],
function(D)
local G, opt;
if not IsSymmetricDigraph(D) then
ErrorNoReturn("the argument <D> must be a symmetric digraph,");
elif HasDigraphGroup(D) then
G := DigraphGroup(D);
else
G := Group(());
fi;
if IsMutableDigraph(D) then
opt := IsMutableDigraph;
else
opt := IsImmutableDigraph;
fi;
return Digraph(opt,
G,
Set(DigraphEdges(D), Set),
OnSets,
{x, y} -> x <> y and not IsEmpty(Intersection(x, y)));
end);
[ Dauer der Verarbeitung: 0.32 Sekunden
(vorverarbeitet)
]
|
