Quelle oper.gi
Sprache: unbekannt
|
|
#############################################################################
##
## oper.gi
## Copyright (C) 2014-19 James D. Mitchell
##
## Licensing information can be found in the README file of this package.
##
#############################################################################
##
#############################################################################
# This file is organised as follows:
#
# 1. Adding and removing vertices
# 2. Adding, removing, and reversing edges
# 3. Ways of combining digraphs
# 4. Actions
# 5. Substructures and quotients
# 6. In and out degrees, neighbours, and edges of vertices
# 7. Copies of out/in-neighbours
# 8. IsSomething
# 9. Connectivity
# 10. Operations for vertices
#############################################################################
#############################################################################
# 1. Adding and removing vertices
#############################################################################
InstallMethod(DigraphAddVertex,
"for a mutable digraph by out-neighbours and an object",
[IsMutableDigraph and IsDigraphByOutNeighboursRep, IsObject],
function(D, label)
Add(D!.OutNeighbours, []);
SetDigraphVertexLabel(D, DigraphNrVertices(D), label);
if IsBound(D!.edgelabels) then
Add(D!.edgelabels, []);
fi;
return D;
end);
InstallMethod(DigraphAddVertex, "for a immutable digraph and an object",
[IsImmutableDigraph, IsObject],
{D, label} -> MakeImmutable(DigraphAddVertex(DigraphMutableCopy(D), label)));
InstallMethod(DigraphAddVertex, "for a mutable digraph",
[IsMutableDigraph],
D -> DigraphAddVertex(D, DigraphNrVertices(D) + 1));
InstallMethod(DigraphAddVertex, "for an immutable digraph",
[IsImmutableDigraph],
D -> MakeImmutable(DigraphAddVertex(DigraphMutableCopy(D))));
InstallMethod(DigraphAddVertices, "for a mutable digraph and list",
[IsMutableDigraph, IsList],
function(D, labels)
local label;
for label in labels do
DigraphAddVertex(D, label);
od;
return D;
end);
InstallMethod(DigraphAddVertices, "for an immutable digraph and list",
[IsImmutableDigraph, IsList],
function(D, labels)
if IsEmpty(labels) then
return D;
fi;
return MakeImmutable(DigraphAddVertices(DigraphMutableCopy(D), labels));
end);
InstallMethod(DigraphAddVertices, "for a mutable digraph and an integer",
[IsMutableDigraph, IsInt],
function(D, m)
local N;
if m < 0 then
ErrorNoReturn("the 2nd argument <m> must be a non-negative integer,");
fi;
N := DigraphNrVertices(D);
return DigraphAddVertices(D, [N + 1 .. N + m]);
end);
InstallMethod(DigraphAddVertices, "for an immutable digraph and an integer",
[IsImmutableDigraph, IsInt],
function(D, m)
if m = 0 then
return D;
fi;
return MakeImmutable(DigraphAddVertices(DigraphMutableCopy(D), m));
end);
# Included for backwards compatibility, even though the 2nd arg is redundant.
# See https://github.com/digraphs/Digraphs/issues/264
# This is deliberately kept undocumented.
InstallMethod(DigraphAddVertices, "for a digraph, an integer, and a list",
[IsDigraph, IsInt, IsList],
function(D, m, labels)
if m <> Length(labels) then
ErrorNoReturn("the list <labels> (3rd argument) must have length <m> ",
"(2nd argument),");
fi;
return DigraphAddVertices(D, labels);
end);
InstallMethod(DigraphRemoveVertex,
"for a mutable digraph by out-neighbours and positive integer",
[IsMutableDigraph and IsDigraphByOutNeighboursRep, IsPosInt],
function(D, u)
local pos, w, v;
if u > DigraphNrVertices(D) then
return D;
fi;
RemoveDigraphVertexLabel(D, u);
if IsBound(D!.edgelabels) then
Remove(D!.edgelabels, u);
fi;
Remove(D!.OutNeighbours, u);
for v in DigraphVertices(D) do
pos := 1;
while pos <= Length(D!.OutNeighbours[v]) do
w := D!.OutNeighbours[v][pos];
if w = u then
Remove(D!.OutNeighbours[v], pos);
RemoveDigraphEdgeLabel(D, v, pos);
elif w > u then
D!.OutNeighbours[v][pos] := w - 1;
pos := pos + 1;
else
pos := pos + 1;
fi;
od;
od;
return D;
end);
InstallMethod(DigraphRemoveVertex,
"for an immutable digraph and positive integer",
[IsImmutableDigraph, IsPosInt],
function(D, u)
if u > DigraphNrVertices(D) then
return D;
fi;
return MakeImmutable(DigraphRemoveVertex(DigraphMutableCopy(D), u));
end);
InstallMethod(DigraphRemoveVertices, "for a mutable digraph and a list",
[IsMutableDigraph, IsList],
function(D, list)
local v;
if not IsDuplicateFreeList(list) or not ForAll(list, IsPosInt) then
ErrorNoReturn("the 2nd argument <list> must be a ",
"duplicate-free list of positive integers,");
elif not IsMutable(list) then
list := ShallowCopy(list);
fi;
# The next line is essential since otherwise removing the 1st node,
# the 2nd node becomes the 1st node, and so removing the 2nd node we
# actually remove the 3rd node instead.
Sort(list, {x, y} -> x > y);
for v in list do
DigraphRemoveVertex(D, v);
od;
return D;
end);
InstallMethod(DigraphRemoveVertices, "for an immutable digraph and a list",
[IsImmutableDigraph, IsList],
{D, list} -> MakeImmutable(DigraphRemoveVertices(DigraphMutableCopy(D), list)));
#############################################################################
# 2. Adding and removing edges
#############################################################################
InstallMethod(DigraphAddEdge,
"for a mutable digraph by out-neighbours, a two positive integers",
[IsMutableDigraph and IsDigraphByOutNeighboursRep, IsPosInt, IsPosInt],
function(D, src, ran)
if not src in DigraphVertices(D)then
ErrorNoReturn("the 2nd argument <src> must be a vertex of the ",
"digraph <D> that is the 1st argument,");
elif not ran in DigraphVertices(D) then
ErrorNoReturn("the 2nd argument <ran> must be a vertex of the ",
"digraph <D> that is the 1st argument,");
fi;
Add(D!.OutNeighbours[src], ran);
if HaveEdgeLabelsBeenAssigned(D) and not IsMultiDigraph(D) then
SetDigraphEdgeLabel(D, src, ran, 1);
fi;
return D;
end);
InstallMethod(DigraphAddEdge,
"for an immutable digraph and two positive integers",
[IsImmutableDigraph, IsPosInt, IsPosInt],
{D, src, ran}
-> MakeImmutable(DigraphAddEdge(DigraphMutableCopy(D), src, ran)));
InstallMethod(DigraphAddEdge, "for a mutable digraph and a list",
[IsMutableDigraph, IsList],
function(D, edge)
if Length(edge) <> 2 then
ErrorNoReturn("the 2nd argument <edge> must be a list of length 2,");
fi;
return DigraphAddEdge(D, edge[1], edge[2]);
end);
InstallMethod(DigraphAddEdge, "for a mutable digraph and a list",
[IsImmutableDigraph, IsList],
{D, edge} -> MakeImmutable(DigraphAddEdge(DigraphMutableCopy(D), edge)));
InstallMethod(DigraphAddEdges, "for a mutable digraph and a list",
[IsMutableDigraph, IsList],
function(D, edges)
local edge;
for edge in edges do
DigraphAddEdge(D, edge);
od;
return D;
end);
InstallMethod(DigraphAddEdges, "for an immutable digraph and a list",
[IsImmutableDigraph, IsList],
{D, edges} -> MakeImmutable(DigraphAddEdges(DigraphMutableCopy(D), edges)));
InstallMethod(DigraphRemoveEdge,
"for a mutable digraph by out-neighbours and two positive integers",
[IsMutableDigraph and IsDigraphByOutNeighboursRep, IsPosInt, IsPosInt],
function(D, src, ran)
local pos;
if IsMultiDigraph(D) then
ErrorNoReturn("the 1st argument <D> must be a digraph with no multiple ",
"edges,");
elif not (IsPosInt(src) and src in DigraphVertices(D)) then
ErrorNoReturn("the 2nd argument <src> must be a vertex of the ",
"digraph <D> that is the 1st argument,");
elif not (IsPosInt(ran) and ran in DigraphVertices(D)) then
ErrorNoReturn("the 3rd argument <ran> must be a vertex of the ",
"digraph <D> that is the 1st argument,");
fi;
pos := Position(D!.OutNeighbours[src], ran);
if pos <> fail then
Remove(D!.OutNeighbours[src], pos);
RemoveDigraphEdgeLabel(D, src, pos);
fi;
return D;
end);
InstallMethod(DigraphRemoveEdge,
"for a immutable digraph and two positive integers",
[IsImmutableDigraph, IsPosInt, IsPosInt],
{D, src, ran}
-> MakeImmutable(DigraphRemoveEdge(DigraphMutableCopy(D), src, ran)));
InstallMethod(DigraphRemoveEdge, "for a mutable digraph and a list",
[IsMutableDigraph, IsList],
function(D, edge)
if Length(edge) <> 2 then
ErrorNoReturn("the 2nd argument <edge> must be a list of length 2,");
fi;
return DigraphRemoveEdge(D, edge[1], edge[2]);
end);
InstallMethod(DigraphRemoveEdge,
"for a immutable digraph and a list",
[IsImmutableDigraph, IsList],
{D, edge} -> MakeImmutable(DigraphRemoveEdge(DigraphMutableCopy(D), edge)));
InstallMethod(DigraphRemoveEdges, "for a digraph and a list",
[IsMutableDigraph, IsList],
function(D, edges)
Perform(edges, edge -> DigraphRemoveEdge(D, edge));
return D;
end);
InstallMethod(DigraphRemoveEdges, "for an immutable digraph and a list",
[IsImmutableDigraph, IsList],
{D, edges} -> MakeImmutable(DigraphRemoveEdges(DigraphMutableCopy(D), edges)));
InstallMethod(DigraphReverseEdge,
"for a mutable digraph by out-neighbours and two positive integers",
[IsMutableDigraph and IsDigraphByOutNeighboursRep, IsPosInt, IsPosInt],
function(D, u, v)
local pos;
if IsMultiDigraph(D) then
ErrorNoReturn("the 1st argument <D> must be a digraph with no ",
"multiple edges,");
fi;
pos := Position(D!.OutNeighbours[u], v);
if pos = fail then
ErrorNoReturn("there is no edge from ", u, " to ", v,
" in the digraph <D> that is the 1st argument,");
elif u = v then
return D;
fi;
Remove(D!.OutNeighbours[u], pos);
Add(D!.OutNeighbours[v], u);
if Length(Positions(D!.OutNeighbours[v], u)) > 1 then
# output is a multidigraph
ClearDigraphEdgeLabels(D);
elif IsBound(D!.edgelabels)
and IsBound(D!.edgelabels[u])
and IsBound(D!.edgelabels[u][pos]) then
SetDigraphEdgeLabel(D, v, u, D!.edgelabels[u][pos]);
RemoveDigraphEdgeLabel(D, u, pos);
fi;
return D;
end);
InstallMethod(DigraphReverseEdge,
"for an immutable digraph, positive integer, and positive integer",
[IsImmutableDigraph, IsPosInt, IsPosInt],
{D, u, v} -> MakeImmutable(DigraphReverseEdge(DigraphMutableCopy(D), u, v)));
InstallMethod(DigraphReverseEdge, "for a mutable digraph and list",
[IsMutableDigraph, IsList],
function(D, e)
if Length(e) <> 2 then
ErrorNoReturn("the 2nd argument <e> must be a list of length 2,");
fi;
return DigraphReverseEdge(D, e[1], e[2]);
end);
InstallMethod(DigraphReverseEdge, "for an immutable digraph and a list",
[IsImmutableDigraph, IsList],
{D, e} -> MakeImmutable(DigraphReverseEdge(DigraphMutableCopy(D), e)));
InstallMethod(DigraphReverseEdges, "for a mutable digraph and a list",
[IsMutableDigraph, IsList],
function(D, E)
Perform(E, e -> DigraphReverseEdge(D, e));
return D;
end);
InstallMethod(DigraphReverseEdges, "for an immutable digraph and a list",
[IsImmutableDigraph, IsList],
{D, E} -> MakeImmutable(DigraphReverseEdges(DigraphMutableCopy(D), E)));
InstallMethod(DigraphClosure,
"for a mutable digraph by out-neighbours and a positive integer",
[IsMutableDigraph and IsDigraphByOutNeighboursRep, IsPosInt],
function(D, k)
local list, mat, deg, n, stop, i, j;
if not IsSymmetricDigraph(D) or DigraphHasLoops(D) or IsMultiDigraph(D) then
ErrorNoReturn("the 1st argument <D> must be a symmetric digraph with no ",
"loops, and no multiple edges,");
fi;
list := D!.OutNeighbours;
mat := BooleanAdjacencyMatrixMutableCopy(D);
deg := ShallowCopy(InDegrees(D));
n := DigraphNrVertices(D);
repeat
stop := true;
for i in [1 .. n] do
for j in [1 .. n] do
if j <> i and (not mat[i][j]) and deg[i] + deg[j] >= k then
Add(list[i], j);
Add(list[j], i);
mat[i][j] := true;
mat[j][i] := true;
deg[i] := deg[i] + 1;
deg[j] := deg[j] + 1;
stop := false;
fi;
od;
od;
until stop;
ClearDigraphEdgeLabels(D);
return D;
end);
InstallMethod(DigraphClosure,
"for an immutable digraph by out-neighbours and a positive integer",
[IsImmutableDigraph, IsPosInt],
{D, k} -> MakeImmutable(DigraphClosure(DigraphMutableCopy(D), k)));
DIGRAPHS_CheckContractEdgeDigraph := function(D, u, v)
if not IsDigraphEdge(D, u, v) then # Check if [u, v] is an edge in digraph D
ErrorNoReturn("expected an edge between the 2nd and 3rd arguments ",
"(vertices) ", u, " and ", v, " but found none");
elif IsMultiDigraph(D) then
ErrorNoReturn("The 1st argument (a digraph) must not satisfy ",
"IsMultiDigraph");
elif u = v then # edge should not be contracted if u = v
ErrorNoReturn("The 2nd argument <u> must not be equal to the 3rd ",
"argument <v>");
fi;
end;
InstallMethod(DigraphContractEdge,
"for a mutable digraph and two positive integers",
[IsMutableDigraph, IsPosInt, IsPosInt],
function(D, u, v)
local w, neighbours, transformations_to_edge, transformations_to_old_edges,
old_edge, new_edge, neighbour, t, vertices, edge_label;
DIGRAPHS_CheckContractEdgeDigraph(D, u, v);
# if (v, u) is an edge, disallow loops, so remove (v, u)
if IsDigraphEdge(D, v, u) then
DigraphRemoveEdge(D, v, u);
fi;
# remove the contracted edge
DigraphRemoveEdge(D, u, v);
# Find vertex neighbours of u and v to construct new incident edges of w
neighbours := [Immutable(InNeighboursOfVertex(D, u)),
Immutable(InNeighboursOfVertex(D, v)),
Immutable(OutNeighboursOfVertex(D, u)),
Immutable(OutNeighboursOfVertex(D, v))];
# immutable reference to old edge labels to add to any
# new transformed incident edges
DigraphAddVertex(D, [DigraphVertexLabel(D, u),
DigraphVertexLabel(D, v)]); # add vertex w
vertices := DigraphVertices(D);
w := Length(vertices); # w is the new vertex identifier
# Handle loops from edges u or w, with the same source / range
# No relevant edges are removed from D until vertices are removed
# So old edge labls are taken from D
if IsDigraphEdge(D, u, u) and IsDigraphEdge(D, v, v) then
DigraphAddEdge(D, w, w);
edge_label := [DigraphEdgeLabel(D, u, u), DigraphEdgeLabel(D, w, w)];
SetDigraphEdgeLabel(D, w, w, edge_label);
elif IsDigraphEdge(D, u, u) then
DigraphAddEdge(D, w, w);
edge_label := DigraphEdgeLabel(D, u, u);
SetDigraphEdgeLabel(D, w, w, edge_label);
elif IsDigraphEdge(D, v, v) then
DigraphAddEdge(D, w, w);
edge_label := DigraphEdgeLabel(D, v, v);
SetDigraphEdgeLabel(D, w, w, edge_label);
fi;
# translate edges based on neighbours
# transformation functions translating neighbours to their new edge
transformations_to_edge := [{x, y} -> [x, y],
{x, y} -> [x, y],
{x, y} -> [y, x],
{x, y} -> [y, x]];
# transformation functions translating neighbours
# to their original edge in D
transformations_to_old_edges := [e -> [e, u],
e -> [e, v],
e -> [u, e],
e -> [v, e]];
# Add translated new edges, and setup edge labels
for t in [1 .. Length(transformations_to_edge)] do
for neighbour in neighbours[t] do
new_edge := transformations_to_edge[t](neighbour, w);
old_edge := transformations_to_old_edges[t](neighbour);
edge_label := DigraphEdgeLabel(D, old_edge[1], old_edge[2]);
DigraphAddEdge(D, new_edge);
SetDigraphEdgeLabel(D, new_edge[1], new_edge[2], edge_label);
od;
od;
DigraphRemoveVertices(D, [u, v]); # remove the vertices of the
# contracted edge (and therefore,
# all its incident edges)
return D;
end);
InstallMethod(DigraphContractEdge,
"for an immutable digraph and two positive integers",
[IsImmutableDigraph, IsPosInt, IsPosInt],
function(D, u, v)
local w, neighbours, transformations_to_edge, transformations_to_old_edges,
existing_edges, edges_to_not_include, new_digraph, new_edge, old_edge,
neighbour, t, vertices, edge_label;
DIGRAPHS_CheckContractEdgeDigraph(D, u, v);
# Incident edges to [u, v] that will be transformed to be incident to w
edges_to_not_include := [];
existing_edges := []; # existing edges that should be re added
# contracted edge should not be added to the new digraph
new_digraph := NullDigraph(IsMutableDigraph, 0);
# if (v, u) is an edge, disallow loops, so remove (v, u)
if IsDigraphEdge(D, v, u) then
D := DigraphRemoveEdge(D, v, u);
fi;
D := DigraphRemoveEdge(D, u, v); # remove the edge to be contracted
DigraphAddVertices(new_digraph, DigraphVertexLabels(D));
# add vertex w with combined labels from u and v
DigraphAddVertex(new_digraph, [DigraphVertexLabel(D, u),
DigraphVertexLabel(D, v)]); # add vertex w
vertices := DigraphVertices(new_digraph);
w := Length(vertices); # w is the new vertex identifier
# Handle loops from edges u or w, with the same source / range
if IsDigraphEdge(D, u, u) and IsDigraphEdge(D, v, v) then
DigraphAddEdge(new_digraph, w, w);
SetDigraphEdgeLabel(new_digraph, w, w, [DigraphEdgeLabel(D, u, u),
DigraphEdgeLabel(D, v, v)]);
elif IsDigraphEdge(D, u, u) then
DigraphAddEdge(new_digraph, w, w);
SetDigraphEdgeLabel(new_digraph, w, w,
DigraphEdgeLabel(D, u, u));
elif IsDigraphEdge(D, v, v) then
DigraphAddEdge(new_digraph, w, w);
SetDigraphEdgeLabel(new_digraph, w, w, DigraphEdgeLabel(D, v, v));
fi;
# if there were loops in D at the vertices u or w, don't include these edges,
# but include a new loop at w
Append(edges_to_not_include, [[u, u], [v, v]]);
# Find vertex neighbours of u and v to construct new incident edges of w
neighbours := [InNeighboursOfVertex(D, u),
InNeighboursOfVertex(D, v),
OutNeighboursOfVertex(D, u),
OutNeighboursOfVertex(D, v)];
# translate edges based on neighbours
# transformation functions translating neighbours to their new edge
transformations_to_edge := [{x, y} -> [x, y], {x, y} -> [x, y],
{x, y} -> [y, x], {x, y} -> [y, x]];
# transformation functions translating neighbours to their original edge in D
transformations_to_old_edges := [e -> [e, u],
e -> [e, v],
e -> [u, e],
e -> [v, e]];
# remove edges that will be adjusted
for t in [1 .. Length(transformations_to_old_edges)] do
Append(edges_to_not_include, List(neighbours[t],
transformations_to_old_edges[t]));
od;
# Find edges that should be included, but remain the same
Sort(edges_to_not_include);
Append(existing_edges, ShallowCopy(DigraphEdges(D)));
Sort(existing_edges);
SubtractSet(existing_edges, edges_to_not_include);
# Add translated new edges, and setup edge labels
for t in [1 .. Length(transformations_to_edge)] do
for neighbour in neighbours[t] do
new_edge := transformations_to_edge[t](neighbour, w);
# old_edge is what the new transformed edge was previously
old_edge := transformations_to_old_edges[t](neighbour);
edge_label := DigraphEdgeLabel(D, old_edge[1], old_edge[2]);
new_digraph := DigraphAddEdge(new_digraph, new_edge);
SetDigraphEdgeLabel(new_digraph, new_edge[1], new_edge[2], edge_label);
od;
od;
# Add the existing edges that have not changed,
# and set their edge labels to that of the previous digraph
for new_edge in existing_edges do
new_digraph := DigraphAddEdge(new_digraph, new_edge);
SetDigraphEdgeLabel(new_digraph, new_edge[1], new_edge[2],
DigraphEdgeLabel(D, new_edge[1], new_edge[2]));
od;
# remove the vertices of the contracted edge
return MakeImmutable(DigraphRemoveVertices(new_digraph, [u, v]));
end);
InstallMethod(DigraphContractEdge,
"for a digraph and a dense list",
[IsDigraph, IsDenseList],
function(D, edge)
if Length(edge) <> 2 then
ErrorNoReturn("the 2nd argument <edge> must be a list of length 2");
fi;
return DigraphContractEdge(D, edge[1], edge[2]);
end);
#############################################################################
# 3. Ways of combining digraphs
#############################################################################
InstallGlobalFunction(DIGRAPHS_CombinationOperProcessArgs,
function(arg...)
local copy, i;
arg := ShallowCopy(arg[1]);
if IsMutableDigraph(arg[1]) then
for i in [2 .. Length(arg)] do
if IsIdenticalObj(arg[1], arg[i]) then
if not IsBound(copy) then
copy := OutNeighboursMutableCopy(arg[1]);
fi;
arg[i] := copy;
else
arg[i] := OutNeighbours(arg[i]);
fi;
od;
arg[1] := arg[1]!.OutNeighbours;
else
arg[1] := OutNeighboursMutableCopy(arg[1]);
for i in [2 .. Length(arg)] do
arg[i] := OutNeighbours(arg[i]);
od;
fi;
return arg;
end);
InstallGlobalFunction(DigraphDisjointUnion,
function(arg...)
local D, offset, n, i, j;
# Allow the possibility of supplying arguments in a list.
if Length(arg) = 1 and IsList(arg[1]) then
arg := arg[1];
fi;
if not IsList(arg) or IsEmpty(arg)
or not ForAll(arg, IsDigraphByOutNeighboursRep) then
ErrorNoReturn("the arguments must be digraphs by out-neighbours, or a ",
"single non-empty list of digraphs by out-neighbours,");
fi;
D := arg[1];
arg := DIGRAPHS_CombinationOperProcessArgs(arg);
offset := DigraphNrVertices(D);
for i in [2 .. Length(arg)] do
n := Length(arg[i]);
for j in [1 .. n] do
arg[1][offset + j] := ShallowCopy(arg[i][j]) + offset;
od;
offset := offset + n;
od;
if IsMutableDigraph(D) then
SetDigraphVertexLabels(D, DigraphVertices(D));
# This above stops D keeping its old vertex labels after being changed
ClearDigraphEdgeLabels(D);
return D;
fi;
return ConvertToImmutableDigraphNC(arg[1]);
end);
InstallGlobalFunction(DigraphJoin,
function(arg...)
local D, tot, offset, n, list, i, v;
# Allow the possibility of supplying arguments in a list.
if Length(arg) = 1 and IsList(arg[1]) then
arg := arg[1];
fi;
if not IsList(arg) or IsEmpty(arg)
or not ForAll(arg, IsDigraphByOutNeighboursRep) then
ErrorNoReturn("the arguments must be digraphs by out-neighbours, or a ",
"single list of digraphs by out-neighbours,");
fi;
D := arg[1];
tot := Sum(arg, DigraphNrVertices);
offset := DigraphNrVertices(D);
arg := DIGRAPHS_CombinationOperProcessArgs(arg);
for list in arg[1] do
Append(list, [offset + 1 .. tot]);
od;
for i in [2 .. Length(arg)] do
n := Length(arg[i]);
for v in [1 .. n] do
arg[1][v + offset] := Concatenation([1 .. offset],
arg[i][v] + offset,
[offset + n + 1 .. tot]);
od;
offset := offset + n;
od;
if IsMutableDigraph(D) then
ClearDigraphEdgeLabels(D);
return D;
fi;
return ConvertToImmutableDigraphNC(arg[1]);
end);
InstallGlobalFunction(DigraphEdgeUnion,
function(arg...)
local D, n, i, v;
# Allow the possibility of supplying arguments in a list.
if Length(arg) = 1 and IsList(arg[1]) then
arg := arg[1];
fi;
if not IsList(arg) or IsEmpty(arg)
or not ForAll(arg, IsDigraphByOutNeighboursRep) then
ErrorNoReturn("the arguments must be digraphs by out-neighbours, or a ",
"single list of digraphs by out-neighbours,");
fi;
D := arg[1];
n := Maximum(List(arg, DigraphNrVertices));
arg := DIGRAPHS_CombinationOperProcessArgs(arg);
if IsMutableDigraph(D) then
DigraphAddVertices(D, n - DigraphNrVertices(D));
else
Append(arg[1], List([1 .. n - Length(arg[1])], x -> []));
fi;
for i in [2 .. Length(arg)] do
for v in [1 .. Length(arg[i])] do
if not IsEmpty(arg[i][v]) then
Append(arg[1][v], arg[i][v]);
fi;
od;
od;
if IsMutableDigraph(D) then
ClearDigraphEdgeLabels(D);
ClearDigraphVertexLabels(D);
return D;
fi;
return ConvertToImmutableDigraphNC(arg[1]);
end);
InstallGlobalFunction(DigraphCartesianProduct,
function(arg...)
local D, n, i, j, proj, m, labs;
# Allow the possibility of supplying arguments in a list.
if Length(arg) = 1 and IsList(arg[1]) then
arg := arg[1];
fi;
if not IsList(arg) or IsEmpty(arg)
or not ForAll(arg, IsDigraphByOutNeighboursRep) then
ErrorNoReturn("the arguments must be digraphs by out-neighbours, or a ",
"single list of digraphs by out-neighbours,");
fi;
labs := List(Cartesian(Reversed(List(arg, DigraphVertexLabels))), Reversed);
D := arg[1];
arg := DIGRAPHS_CombinationOperProcessArgs(arg);
m := Product(List(arg, Length));
proj := [Transformation([1 .. m], x -> RemInt(x - 1, Length(arg[1])) + 1)];
for i in [2 .. Length(arg)] do
n := Length(arg[1]);
Add(proj, Transformation([1 .. m],
x -> RemInt(QuoInt(x - 1, n), Length(arg[i])) * n + 1));
for j in [2 .. Length(arg[i])] do
arg[1]{[1 + n * (j - 1) .. n * j]} := List([1 .. n],
x -> Concatenation(arg[1][x] + n * (j - 1),
x + n * (arg[i][j] - 1)));
od;
for j in [1 .. n] do
Append(arg[1][j], j + n * (arg[i][1] - 1));
od;
od;
if IsMutableDigraph(D) then
ClearDigraphEdgeLabels(D);
else
D := DigraphNC(arg[1]);
fi;
SetDigraphCartesianProductProjections(D, proj);
SetDigraphVertexLabels(D, labs);
return D;
end);
InstallGlobalFunction(DigraphDirectProduct,
function(arg...)
local D, n, i, j, proj, m, labs;
# Allow the possibility of supplying arguments in a list.
if Length(arg) = 1 and IsList(arg[1]) then
arg := arg[1];
fi;
if not IsList(arg) or IsEmpty(arg)
or not ForAll(arg, IsDigraphByOutNeighboursRep) then
ErrorNoReturn("the arguments must be digraphs by out-neighbours, or a ",
"single list of digraphs by out-neighbours,");
fi;
labs := List(Cartesian(Reversed(List(arg, DigraphVertexLabels))), Reversed);
D := arg[1];
arg := DIGRAPHS_CombinationOperProcessArgs(arg);
m := Product(List(arg, Length));
proj := [Transformation([1 .. m], x -> RemInt(x - 1, Length(arg[1])) + 1)];
for i in [2 .. Length(arg)] do
n := Length(arg[1]);
Add(proj, Transformation([1 .. m],
x -> RemInt(QuoInt(x - 1, n), Length(arg[i])) * n + 1));
for j in [2 .. Length(arg[i])] do
arg[1]{[1 + n * (j - 1) .. n * j]} := List([1 .. n],
x -> List(Cartesian(arg[1][x], n * (arg[i][j] - 1)), Sum));
od;
for j in [1 .. n] do
arg[1][j] := List(Cartesian(arg[1][j], n * (arg[i][1] - 1)), Sum);
od;
od;
if IsMutableDigraph(D) then
ClearDigraphEdgeLabels(D);
else
D := DigraphNC(arg[1]);
fi;
SetDigraphDirectProductProjections(D, proj);
SetDigraphVertexLabels(D, labs);
return D;
end);
InstallMethod(ModularProduct, "for a digraph and digraph",
[IsDigraph, IsDigraph],
function(D1, D2)
local edge_function;
edge_function := function(u, v, m, n, map) # gaplint: disable=W046
# neither m nor n is used, but can't replace them both with _
local w, x, connections;
connections := [];
for w in OutNeighbours(D1)[u] do
for x in OutNeighbours(D2)[v] do
if (u = w) = (v = x) then
Add(connections, map(w, x));
fi;
od;
od;
for w in OutNeighbours(DigraphDual(D1))[u] do
for x in OutNeighbours(DigraphDual(D2))[v] do
if (u = w) = (v = x) then
Add(connections, map(w, x));
fi;
od;
od;
return connections;
end;
return DIGRAPHS_GraphProduct(D1, D2, edge_function);
end);
InstallMethod(StrongProduct, "for a digraph and digraph",
[IsDigraph, IsDigraph],
function(D1, D2)
local edge_function;
edge_function := function(u, v, m, n, map) # gaplint: disable=W046
# neither m nor n is used, but can't replace them both with _
local w, x, connections;
connections := [];
for x in OutNeighbours(D2)[v] do
AddSet(connections, map(u, x));
for w in OutNeighbours(D1)[u] do
AddSet(connections, map(w, x));
od;
od;
for w in OutNeighbours(D1)[u] do
AddSet(connections, map(w, v));
od;
return connections;
end;
return DIGRAPHS_GraphProduct(D1, D2, edge_function);
end);
InstallMethod(ConormalProduct, "for a digraph and digraph",
[IsDigraph, IsDigraph],
function(D1, D2)
local edge_function;
edge_function := function(u, v, m, n, map)
local w, x, connections;
connections := [];
for w in OutNeighbours(D1)[u] do
for x in [1 .. n] do
AddSet(connections, map(w, x));
od;
od;
for x in OutNeighbours(D2)[v] do
for w in [1 .. m] do
AddSet(connections, map(w, x));
od;
od;
return connections;
end;
return DIGRAPHS_GraphProduct(D1, D2, edge_function);
end);
InstallMethod(HomomorphicProduct, "for a digraph and digraph",
[IsDigraph, IsDigraph],
function(D1, D2)
local edge_function;
edge_function := function(u, v, _, n, map)
local w, x, connections;
connections := [];
for x in [1 .. n] do
AddSet(connections, map(u, x));
od;
for w in OutNeighbours(D1)[u] do
for x in OutNeighbours(DigraphDual(D2))[v] do
AddSet(connections, map(w, x));
od;
od;
return connections;
end;
return DIGRAPHS_GraphProduct(D1, D2, edge_function);
end);
InstallMethod(LexicographicProduct, "for a digraph and digraph",
[IsDigraph, IsDigraph],
function(D1, D2)
local edge_function;
edge_function := function(u, v, _, n, map)
local w, x, connections;
connections := [];
for w in OutNeighbours(D1)[u] do
for x in [1 .. n] do
AddSet(connections, map(w, x));
od;
od;
for x in OutNeighbours(D2)[v] do
AddSet(connections, map(u, x));
od;
return connections;
end;
return DIGRAPHS_GraphProduct(D1, D2, edge_function);
end);
InstallMethod(DIGRAPHS_GraphProduct,
"for a digraph, a digraph, and a function",
[IsDigraph, IsDigraph, IsFunction],
function(D1, D2, edge_function)
local m, n, edges, u, v, map;
if IsMultiDigraph(D1) then
ErrorNoReturn(
"the 1st argument (a digraph) must not satisfy IsMultiDigraph");
elif IsMultiDigraph(D2) then
ErrorNoReturn(
"the 2nd argument (a digraph) must not satisfy IsMultiDigraph");
fi;
m := DigraphNrVertices(D1);
n := DigraphNrVertices(D2);
edges := EmptyPlist(m * n);
map := {a, b} -> (a - 1) * n + b;
for u in [1 .. m] do
for v in [1 .. n] do
edges[map(u, v)] := edge_function(u, v, m, n, map);
od;
od;
return Digraph(edges);
end);
###############################################################################
# 4. Actions
###############################################################################
InstallMethod(OnDigraphs, "for a digraph and a perm",
[IsDigraph, IsPerm],
function(D, p)
if ForAll(DigraphVertices(D), i -> i ^ p = i) then
return D;
elif ForAny(DigraphVertices(D), i -> i ^ p > DigraphNrVertices(D)) then
ErrorNoReturn("the 2nd argument <p> must be a permutation that permutes ",
"the vertices of the digraph <D> that is the 1st argument");
fi;
return OnDigraphsNC(D, p);
end);
InstallMethod(OnDigraphsNC,
"for a mutable digraph by out-neighbours and a perm",
[IsMutableDigraph and IsDigraphByOutNeighboursRep, IsPerm],
function(D, p)
local out;
if p = () then
return D;
fi;
out := D!.OutNeighbours;
out{DigraphVertices(D)} := Permuted(out, p);
Apply(out, x -> OnTuples(x, p));
ClearDigraphEdgeLabels(D);
return D;
end);
InstallMethod(OnDigraphsNC, "for a immutable digraph and a perm",
[IsImmutableDigraph, IsPerm],
function(D, p)
local out, permed;
if p = () then
return D;
fi;
out := D!.OutNeighbours;
permed := Permuted(out, p);
Apply(permed, x -> OnTuples(x, p));
return DigraphNC(IsImmutableDigraph, permed);
end);
InstallMethod(OnDigraphs,
"for a digraph and a transformation",
[IsDigraph, IsTransformation],
function(D, t)
if ForAll(DigraphVertices(D), i -> i ^ t = i) then
return D;
elif ForAny(DigraphVertices(D), i -> i ^ t > DigraphNrVertices(D)) then
ErrorNoReturn("the 2nd argument <t> must be a transformation that ",
"maps every vertex of the digraph <D> that is the 1st ",
"argument, to another vertex");
fi;
return OnDigraphsNC(D, t);
end);
InstallMethod(OnDigraphsNC,
"for a mutable digraph by out-neighbours and a transformation",
[IsMutableDigraph and IsDigraphByOutNeighboursRep, IsTransformation],
function(D, t)
local old, new, v;
if t = IdentityTransformation then
return D;
fi;
old := D!.OutNeighbours;
new := List(DigraphVertices(D), x -> []);
for v in DigraphVertices(D) do
Append(new[v ^ t], OnTuples(old[v], t));
od;
old{DigraphVertices(D)} := new;
ClearDigraphEdgeLabels(D);
return D;
end);
InstallMethod(OnDigraphsNC, "for a immutable digraph and a transformation",
[IsImmutableDigraph, IsTransformation],
function(D, t)
local old, new, v;
if t = IdentityTransformation then
return D;
fi;
old := D!.OutNeighbours;
new := List(DigraphVertices(D), x -> []);
for v in DigraphVertices(D) do
Append(new[v ^ t], OnTuples(old[v], t));
od;
return DigraphNC(IsImmutableDigraph, new);
end);
InstallMethod(OnTuplesDigraphs,
"for list of digraphs and a perm",
[IsDigraphCollection and IsHomogeneousList, IsPerm],
{L, p} -> List(L, D -> OnDigraphs(DigraphMutableCopyIfMutable(D), p)));
InstallMethod(OnSetsDigraphs,
"for a list of digraphs and a perm",
[IsDigraphCollection and IsHomogeneousList, IsPerm],
function(S, p)
if not IsSet(S) then
ErrorNoReturn("the first argument must be a set (a strictly sorted list)");
fi;
return Set(S, D -> OnDigraphs(DigraphMutableCopyIfMutable(D), p));
end);
# Not revising the following because multi-digraphs are being withdrawn in the
# near future.
InstallMethod(OnMultiDigraphs, "for a digraph, perm and perm",
[IsDigraph, IsPerm, IsPerm],
{D, perm1, perm2} -> OnMultiDigraphs(D, [perm1, perm2]));
InstallMethod(OnMultiDigraphs, "for a digraph and perm coll",
[IsDigraph, IsPermCollection],
function(D, perms)
if Length(perms) <> 2 then
ErrorNoReturn("the 2nd argument <perms> must be a pair of permutations,");
elif ForAny([1 .. DigraphNrEdges(D)],
i -> i ^ perms[2] > DigraphNrEdges(D)) then
ErrorNoReturn("the 2nd entry of the 2nd argument <perms> must ",
"permute the edges of the digraph <D> that is the 1st ",
"argument");
fi;
return OnDigraphs(D, perms[1]);
end);
# DomainForAction returns `true` instead of a proper domain here as a stopgap
# measure to ensure that the Orbit method of GAP uses a SparseHashTable instead
# of a DictionaryByPosition.
# As SparseIntKey for digraphs does not depend on the domain, and always
# returns DigraphHash, the actual returned value of DomainForAction does not
# matter as long as it returns something other than `fail`.
InstallMethod(DomainForAction, "for a digraph, list or collection and function",
[IsDigraph, IsListOrCollection, IsFunction],
ReturnTrue);
#############################################################################
# 5. Substructures and quotients
#############################################################################
InstallMethod(InducedSubdigraph,
"for a mutable digraph by out-neighbours and a homogeneous list",
[IsDigraphByOutNeighboursRep and IsMutableDigraph, IsHomogeneousList],
function(D, list)
local M, N, old, old_edl, new_edl, lookup, next, vv, w, old_labels, v, i;
M := Length(list);
N := DigraphNrVertices(D);
if M = 0 then
D!.OutNeighbours := [];
return D;
elif M = DigraphVertices(D) then
return D;
elif not IsDuplicateFree(list)
or ForAny(list, x -> not IsPosInt(x) or x > N) then
ErrorNoReturn("the 2nd argument <list> must be a duplicate-free ",
"subset of the vertices of the digraph <D> that is ",
"the 1st argument,");
fi;
old := D!.OutNeighbours;
old_edl := DigraphEdgeLabelsNC(D);
new_edl := List([1 .. M], x -> []);
lookup := ListWithIdenticalEntries(N, 0);
lookup{list} := [1 .. M];
for v in [1 .. M] do
next := [];
vv := list[v]; # old vertex corresponding to vertex v in new subdigraph
for i in [1 .. Length(old[vv])] do
w := old[vv][i];
if lookup[w] <> 0 then
Add(next, lookup[w]);
Add(new_edl[v], old_edl[vv][i]);
fi;
od;
old[vv] := next;
od;
old_labels := DigraphVertexLabels(D);
D!.OutNeighbours := old{list};
# Note that the following line means multidigraphs have wrong edge labels set.
SetDigraphEdgeLabelsNC(D, new_edl);
SetDigraphVertexLabels(D, old_labels{list});
return D;
end);
InstallMethod(InducedSubdigraph,
"for an immutable digraph and a homogeneous list",
[IsImmutableDigraph, IsHomogeneousList],
function(D, list)
if Length(list) = 0 then
return EmptyDigraph(0);
elif list = DigraphVertices(D) then
return D;
fi;
return MakeImmutable(InducedSubdigraph(DigraphMutableCopy(D), list));
end);
InstallMethod(QuotientDigraph,
"for a mutable digraph by out-neighbours and a homogeneous list",
[IsDigraphByOutNeighboursRep and IsMutableDigraph, IsHomogeneousList],
function(D, partition)
local N, M, check, lookup, new, new_vl, old, old_vl, x, i, u, v;
N := DigraphNrVertices(D);
M := Length(partition);
if N = 0 then
if IsEmpty(partition) then
return D;
fi;
ErrorNoReturn("the 2nd argument <partition> should be an empty list, which",
" is the only valid partition of the vertices of 1st",
" argument <D> because it has no vertices,");
elif M = 0 or not IsList(partition[1])
or IsEmpty(partition[1]) or not IsPosInt(partition[1][1]) then
ErrorNoReturn("the 2nd argument <partition> is not a valid ",
"partition of the vertices [1 .. ", N, "] of the 1st ",
"argument <D>,");
fi;
check := ListWithIdenticalEntries(DigraphNrVertices(D), false);
lookup := EmptyPlist(N);
for x in [1 .. Length(partition)] do
for i in partition[x] do
if i < 1 or i > N or check[i] then
ErrorNoReturn("the 2nd argument <partition> is not a valid ",
"partition of the vertices [1 .. ", N, "] of the 1st ",
"argument <D>,");
fi;
check[i] := true;
lookup[i] := x;
od;
od;
if not ForAll(check, IdFunc) then
ErrorNoReturn("the 2nd argument <partition> is not a valid ",
"partition of the vertices [1 .. ", N, "] of the 1st ",
"argument <D>,");
fi;
new := List([1 .. M], x -> []);
new_vl := List([1 .. M], x -> []);
old := D!.OutNeighbours;
old_vl := DigraphVertexLabels(D);
for u in DigraphVertices(D) do
Add(new_vl[lookup[u]], old_vl[u]);
for v in old[u] do
AddSet(new[lookup[u]], lookup[v]);
od;
od;
D!.OutNeighbours := new;
SetDigraphVertexLabels(D, new_vl);
ClearDigraphEdgeLabels(D);
return D;
end);
InstallMethod(QuotientDigraph,
"for an immutable digraph and a homogeneous list",
[IsImmutableDigraph, IsHomogeneousList],
{D, partition} ->
MakeImmutable(QuotientDigraph(DigraphMutableCopy(D), partition)));
#############################################################################
# 6. In and out degrees, neighbours, and edges of vertices
#############################################################################
InstallMethod(InNeighboursOfVertex, "for a digraph and a positive integer",
[IsDigraph, IsPosInt],
function(D, v)
if not v in DigraphVertices(D) then
ErrorNoReturn("the 2nd argument <v> is not a vertex of the ",
"1st argument <D>,");
fi;
return InNeighboursOfVertexNC(D, v);
end);
InstallMethod(InNeighboursOfVertexNC,
"for a digraph with in-neighbours and a positive integer",
[IsDigraph and HasInNeighbours, IsPosInt],
2, # to beat the next method for IsDigraphByOutNeighboursRep
{D, v} -> InNeighbours(D)[v]);
InstallMethod(InNeighboursOfVertexNC,
"for a digraph by out-neighbours and a positive integer",
[IsDigraphByOutNeighboursRep, IsPosInt],
function(D, v)
local inn, out, i, j;
inn := [];
out := OutNeighbours(D);
for i in [1 .. Length(out)] do
for j in [1 .. Length(out[i])] do
if out[i][j] = v then
Add(inn, i);
fi;
od;
od;
return inn;
end);
InstallMethod(OutNeighboursOfVertex,
"for a digraph by out-neighbours and a positive integer",
[IsDigraphByOutNeighboursRep, IsPosInt],
function(D, v)
if not v in DigraphVertices(D) then
ErrorNoReturn("the 2nd argument <v> is not a vertex of the ",
"1st argument <D>,");
fi;
return OutNeighboursOfVertexNC(D, v);
end);
InstallMethod(OutNeighboursOfVertexNC,
"for a digraph by out-neighbours and a positive integer",
[IsDigraphByOutNeighboursRep, IsPosInt],
{D, v} -> OutNeighbours(D)[v]);
InstallMethod(InDegreeOfVertex, "for a digraph and a positive integer",
[IsDigraph, IsPosInt],
function(D, v)
if not v in DigraphVertices(D) then
ErrorNoReturn("the 2nd argument <v> is not a vertex of the ",
"1st argument <D>,");
fi;
return InDegreeOfVertexNC(D, v);
end);
InstallMethod(InDegreeOfVertexNC,
"for a digraph with in-degrees and a positive integer",
[IsDigraph and HasInDegrees, IsPosInt], 4,
{D, v} -> InDegrees(D)[v]);
InstallMethod(InDegreeOfVertexNC,
"for a digraph with in-neighbours and a positive integer",
[IsDigraph and HasInNeighbours, IsPosInt],
2, # to beat the next method for IsDigraphByOutNeighboursRep
{D, v} -> Length(InNeighbours(D)[v]));
InstallMethod(InDegreeOfVertexNC, "for a digraph and a positive integer",
[IsDigraphByOutNeighboursRep, IsPosInt],
function(D, v)
local count, out, x, i;
count := 0;
out := OutNeighbours(D);
for x in out do
for i in x do
if i = v then
count := count + 1;
fi;
od;
od;
return count;
end);
InstallMethod(OutDegreeOfVertex, "for a digraph and a positive integer",
[IsDigraph, IsPosInt],
function(D, v)
if not v in DigraphVertices(D) then
ErrorNoReturn("the 2nd argument <v> is not a vertex of the ",
"1st argument <D>,");
fi;
return OutDegreeOfVertexNC(D, v);
end);
InstallMethod(OutDegreeOfVertexNC,
"for a digraph with out-degrees and a positive integer",
[IsDigraph and HasOutDegrees, IsPosInt],
2, # to beat the next method for IsDigraphByOutNeighboursRep
{D, v} -> OutDegrees(D)[v]);
InstallMethod(OutDegreeOfVertexNC,
"for a digraph by out-neighbours and a positive integer",
[IsDigraphByOutNeighboursRep, IsPosInt],
{D, v} -> Length(OutNeighbours(D)[v]));
InstallMethod(DigraphOutEdges,
"for a digraph by out-neighbours and a positive integer",
[IsDigraphByOutNeighboursRep, IsPosInt],
function(D, v)
if not v in DigraphVertices(D) then
ErrorNoReturn("the 2nd argument <v> is not a vertex of the ",
"1st argument <D>,");
fi;
return List(OutNeighboursOfVertex(D, v), x -> [v, x]);
end);
InstallMethod(DigraphInEdges, "for a digraph and a positive integer",
[IsDigraph, IsPosInt],
function(D, v)
if not v in DigraphVertices(D) then
ErrorNoReturn("the 2nd argument <v> is not a vertex of the ",
"1st argument <D>,");
fi;
return List(InNeighboursOfVertex(D, v), x -> [x, v]);
end);
#############################################################################
# 7. Copies of out/in-neighbours
#############################################################################
InstallMethod(OutNeighboursMutableCopy, "for a digraph by out-neighbours",
[IsDigraphByOutNeighboursRep],
D -> List(OutNeighbours(D), ShallowCopy));
InstallMethod(InNeighboursMutableCopy, "for a digraph", [IsDigraph],
D -> List(InNeighbours(D), ShallowCopy));
InstallMethod(AdjacencyMatrixMutableCopy, "for a digraph", [IsDigraph],
D -> List(AdjacencyMatrix(D), ShallowCopy));
InstallMethod(BooleanAdjacencyMatrixMutableCopy, "for a digraph", [IsDigraph],
D -> List(BooleanAdjacencyMatrix(D), ShallowCopy));
#############################################################################
# 8. IsSomething
#############################################################################
InstallMethod(IsDigraphEdge, "for a digraph and a list",
[IsDigraph, IsList],
function(D, edge)
if Length(edge) <> 2 or not IsPosInt(edge[1]) or not IsPosInt(edge[2]) then
return false;
fi;
return IsDigraphEdge(D, edge[1], edge[2]);
end);
InstallMethod(IsDigraphEdge, "for a digraph by out-neighbours, int, int",
[IsDigraphByOutNeighboursRep, IsInt, IsInt],
function(D, u, v)
local n;
n := DigraphNrVertices(D);
if u > n or v > n or u <= 0 or v <= 0 then
return false;
elif HasAdjacencyMatrix(D) then
return AdjacencyMatrix(D)[u][v] <> 0;
elif IsDigraphWithAdjacencyFunction(D) then
return DigraphAdjacencyFunction(D)(u, v);
fi;
return v in OutNeighboursOfVertex(D, u);
end);
InstallMethod(IsSubdigraph,
"for two digraphs by out-neighbours",
[IsDigraphByOutNeighboursRep, IsDigraphByOutNeighboursRep],
function(super, sub)
local n, x, y, i, j;
n := DigraphNrVertices(super);
if n <> DigraphNrVertices(sub)
or DigraphNrEdges(super) < DigraphNrEdges(sub) then
return false;
elif not IsMultiDigraph(sub) then
return ForAll(DigraphVertices(super), i ->
IsSubset(OutNeighboursOfVertex(super, i),
OutNeighboursOfVertex(sub, i)));
elif not IsMultiDigraph(super) then
return false;
fi;
x := [1 .. n];
y := [1 .. n];
for i in DigraphVertices(super) do
if OutDegreeOfVertex(super, i) < OutDegreeOfVertex(sub, i) then
return false;
fi;
x := x * 0;
y := y * 0;
for j in OutNeighboursOfVertex(super, i) do
x[j] := x[j] + 1;
od;
for j in OutNeighboursOfVertex(sub, i) do
y[j] := y[j] + 1;
od;
if not ForAll(DigraphVertices(super), k -> y[k] <= x[k]) then
return false;
fi;
od;
return true;
end);
InstallMethod(IsUndirectedSpanningForest, "for two digraphs",
[IsDigraph, IsDigraph],
function(super, sub)
local sym, comps1, comps2;
if not IsUndirectedForest(sub) then
return false;
fi;
sym := MaximalSymmetricSubdigraph(DigraphMutableCopyIfMutable(super));
if not IsSubdigraph(sym, sub) then
return false;
fi;
comps1 := DigraphConnectedComponents(sym).comps;
comps2 := DigraphConnectedComponents(sub).comps;
if Length(comps1) <> Length(comps2) then
return false;
fi;
return Set(comps1, SortedList) = Set(comps2, SortedList);
end);
InstallMethod(IsUndirectedSpanningTree, "for a digraph and a digraph",
[IsDigraph, IsDigraph],
function(super, sub)
super := DigraphMutableCopyIfMutable(super);
return IsConnectedDigraph(MaximalSymmetricSubdigraph(super))
and IsUndirectedSpanningForest(super, sub);
end);
# The following function performs almost all of the calculations necessary for
# IsMatching, IsPerfectMatching, and IsMaximalMatching, without duplicating work
BindGlobal("DIGRAPHS_Matching",
function(D, edges)
local seen, e;
Assert(1, IsDigraph(D));
Assert(1, IsHomogeneousList(edges));
if not IsDuplicateFreeList(edges)
or not ForAll(edges, e -> IsDigraphEdge(D, e)) then
return false;
fi;
seen := BlistList(DigraphVertices(D), []);
for e in edges do
if seen[e[1]] or seen[e[2]] then
return false;
fi;
seen[e[1]] := true;
seen[e[2]] := true;
od;
return seen;
end);
InstallMethod(IsMatching, "for a digraph and a list",
[IsDigraph, IsHomogeneousList],
{D, edges} -> DIGRAPHS_Matching(D, edges) <> false);
InstallMethod(IsPerfectMatching, "for a digraph and a list",
[IsDigraph, IsHomogeneousList],
function(D, edges)
local seen;
seen := DIGRAPHS_Matching(D, edges);
if seen = false then
return false;
fi;
return SizeBlist(seen) = DigraphNrVertices(D);
end);
InstallMethod(IsMaximumMatching, "for a digraph and a list",
[IsDigraph, IsHomogeneousList],
function(D, edges)
return IsMatching(D, edges)
and Length(edges) = Length(DigraphMaximumMatching(D));
end);
InstallMethod(IsMaximalMatching, "for a digraph and a list",
[IsDigraphByOutNeighboursRep, IsHomogeneousList],
function(D, edges)
local seen, nbs, i, j;
seen := DIGRAPHS_Matching(D, edges);
if seen = false then
return false;
fi;
nbs := OutNeighbours(D);
for i in DigraphVertices(D) do
if not seen[i] then
for j in nbs[i] do
if not seen[j] then
return false;
fi;
od;
fi;
od;
return true;
end);
#############################################################################
# 9. Connectivity
#############################################################################
InstallMethod(DigraphIsKing,
"for a digraph and two positive integers",
[IsDigraph, IsPosInt, IsPosInt],
function(D, v, k)
local layers;
if not v in DigraphVertices(D) then
ErrorNoReturn("the 2nd argument <v> is not a vertex of the ",
"1st argument <D>,");
elif not IsTournament(D) then
ErrorNoReturn("the 1st argument <D> must be a tournament,");
fi;
layers := DigraphLayers(D, v);
return ((Length(layers) <= k + 1) and (Union(layers) = DigraphVertices(D)));
end);
InstallMethod(DigraphFloydWarshall,
"for a digraph by out-neighbours, function, object, and object",
[IsDigraphByOutNeighboursRep, IsFunction, IsObject, IsObject],
function(D, func, nopath, edge)
local vertices, n, mat, out, i, j, k;
vertices := DigraphVertices(D);
n := DigraphNrVertices(D);
mat := EmptyPlist(n);
for i in vertices do
mat[i] := EmptyPlist(n);
for j in vertices do
mat[i][j] := nopath;
od;
od;
out := OutNeighbours(D);
for i in vertices do
for j in out[i] do
mat[i][j] := edge;
od;
od;
for k in vertices do
for i in vertices do
for j in vertices do
func(mat, i, j, k);
od;
od;
od;
return mat;
end);
InstallMethod(DigraphStronglyConnectedComponent,
"for a digraph and a positive integer",
[IsDigraph, IsPosInt],
function(D, v)
local scc;
if not v in DigraphVertices(D) then
ErrorNoReturn("the 2nd argument <v> is not a vertex of the ",
"1st argument <D>,");
fi;
# TODO check if strongly connected components are known and use them if they
# are and don't use them if they are not.
scc := DigraphStronglyConnectedComponents(D);
return scc.comps[scc.id[v]];
end);
InstallMethod(DigraphConnectedComponent, "for a digraph and a positive integer",
[IsDigraph, IsPosInt],
function(D, v)
local wcc;
if not v in DigraphVertices(D) then
ErrorNoReturn("the 2nd argument <v> is not a vertex of the ",
"1st argument <D>,");
fi;
wcc := DigraphConnectedComponents(D);
return wcc.comps[wcc.id[v]];
end);
InstallMethod(IsReachable, "for a digraph and two pos ints",
[IsDigraph, IsPosInt, IsPosInt],
function(D, u, v)
local verts, scc;
verts := DigraphVertices(D);
if not (u in verts and v in verts) then
ErrorNoReturn("the 2nd and 3rd arguments <u> and <v> must be ",
"vertices of the 1st argument <D>,");
elif IsDigraphEdge(D, u, v) then
return true;
elif HasDigraphStronglyConnectedComponents(D) then
# Glean information from SCC if we have it
scc := DigraphStronglyConnectedComponents(D);
return (u <> v and scc.id[u] = scc.id[v])
or (u = v and Length(scc.comps[scc.id[u]]) > 1);
fi;
return DigraphPath(D, u, v) <> fail;
end);
InstallMethod(DigraphPath, "for a digraph by out-neighbours and two pos ints",
[IsDigraphByOutNeighboursRep, IsPosInt, IsPosInt],
function(D, u, v)
local verts;
verts := DigraphVertices(D);
if not (u in verts and v in verts) then
ErrorNoReturn("the 2nd and 3rd arguments <u> and <v> must be ",
"vertices of the 1st argument <D>,");
elif IsDigraphEdge(D, u, v) then
return [[u, v], [Position(OutNeighboursOfVertex(D, u), v)]];
elif HasIsTransitiveDigraph(D) and IsTransitiveDigraph(D) then
# If it's a known transitive digraph, just check whether the edge exists
return fail;
# Glean information from WCC if we have it
elif HasDigraphConnectedComponents(D)
and DigraphConnectedComponents(D).id[u] <>
DigraphConnectedComponents(D).id[v] then
return fail;
fi;
return DIGRAPH_PATH(OutNeighbours(D), u, v);
end);
InstallMethod(IsDigraphPath, "for a digraph and list",
[IsDigraph, IsList],
function(D, digraph_path_output)
if Length(digraph_path_output) <> 2 then
DError(["the 2nd argument (a list) must have length 2, ",
"but found length {}"],
Length(digraph_path_output));
fi;
return IsDigraphPath(D, digraph_path_output[1], digraph_path_output[2]);
end);
InstallMethod(IsDigraphPath, "for a digraph, homog. list, and homog. list",
[IsDigraph, IsHomogeneousList, IsHomogeneousList],
function(D, nodes, edges)
local a, i;
if Length(nodes) <> Length(edges) + 1 then
DError(["the 2nd and 3rd arguments (lists) are incompatible, ",
"expected 3rd argument of length {}, got {}"],
Length(nodes) - 1,
Length(edges));
fi;
a := OutNeighbours(D);
for i in [1 .. Length(edges)] do
if nodes[i] > Length(a) or edges[i] > Length(a[nodes[i]])
or a[nodes[i]][edges[i]] <> nodes[i + 1] then
return false;
fi;
od;
return true;
end);
InstallMethod(DigraphShortestPath,
"for a digraph by out-neighbours and two pos ints",
[IsDigraphByOutNeighboursRep, IsPosInt, IsPosInt],
function(D, u, v)
local current, next, parent, distance, falselist, verts, nbs, path, edge,
n, a, b, i;
verts := DigraphVertices(D);
if not (u in verts and v in verts) then
ErrorNoReturn("the 2nd and 3rd arguments <u> and <v> must be ",
"vertices of the 1st argument <D>,");
fi;
if IsDigraphEdge(D, u, v) then
return [[u, v], [Position(OutNeighboursOfVertex(D, u), v)]];
elif HasIsTransitiveDigraph(D) and IsTransitiveDigraph(D) then
# If it's a known transitive digraph, just check whether the edge exists
return fail;
# Glean information from WCC if we have it
elif HasDigraphConnectedComponents(D)
and DigraphConnectedComponents(D).id[u] <>
DigraphConnectedComponents(D).id[v] then
return fail;
fi;
nbs := OutNeighbours(D);
distance := ListWithIdenticalEntries(Length(verts), -1);
# Setting up objects useful in the function.
parent := [];
current := [u];
edge := [];
next := BlistList([1 .. Length(verts)], []);
falselist := BlistList([1 .. Length(verts)], []);
n := 0;
while current <> [] do
n := n + 1;
for a in current do
for i in [1 .. Length(nbs[a])] do
b := nbs[a][i];
if distance[b] = -1 then
distance[b] := n;
next[b] := true;
parent[b] := a;
edge[b] := i;
fi;
if b = v then
path := [[], []];
# Finds the path
for i in [1 .. n] do
Add(path[1], b);
Add(path[2], edge[b]);
b := parent[b];
od;
Add(path[1], u); # Adds the starting vertex to the list of vertices
return [Reversed(path[1]), Reversed(path[2])];
fi;
od;
od;
current := ListBlist(verts, next);
IntersectBlist(next, falselist);
od;
return fail;
end);
BindGlobal("DIGRAPHS_DijkstraST",
function(digraph, source, target)
local dist, prev, queue, u, v, alt;
if not source in DigraphVertices(digraph) then
ErrorNoReturn("the 2nd argument <source> must be a vertex of the ",
"1st argument <digraph>");
elif target <> fail and not target in DigraphVertices(digraph) then
ErrorNoReturn("the 3rd argument <target> must be a vertex of the ",
"1st argument <digraph>");
fi;
dist := [];
prev := [];
queue := BinaryHeap({x, y} -> x[1] < y[1]);
for v in DigraphVertices(digraph) do
dist[v] := infinity;
prev[v] := -1;
od;
dist[source] := 0;
Push(queue, [0, source]);
while not IsEmpty(queue) do
u := Pop(queue);
u := u[2];
# TODO: this has a small performance impact for DigraphDijkstraS,
# but do we care?
if u = target then
return [dist, prev];
fi;
for v in OutNeighbours(digraph)[u] do
alt := dist[u] + DigraphEdgeLabel(digraph, u, v);
if alt < dist[v] then
dist[v] := alt;
prev[v] := u;
Push(queue, [dist[v], v]);
fi;
od;
od;
return [dist, prev];
end);
InstallMethod(DigraphDijkstra, "for a digraph, a vertex, and a vertex",
[IsDigraph, IsPosInt, IsPosInt], DIGRAPHS_DijkstraST);
InstallMethod(DigraphDijkstra, "for a digraph, and a vertex",
[IsDigraph, IsPosInt],
{digraph, source} -> DIGRAPHS_DijkstraST(digraph, source, fail));
InstallMethod(IteratorOfPaths,
"for a digraph by out-neighbours and two pos ints",
[IsDigraphByOutNeighboursRep, IsPosInt, IsPosInt],
function(D, u, v)
if not (u in DigraphVertices(D) and v in DigraphVertices(D)) then
ErrorNoReturn("the 2nd and 3rd arguments <u> and <v> must be ",
"vertices of the 1st argument <D>,");
fi;
return IteratorOfPathsNC(OutNeighbours(D), u, v);
end);
InstallMethod(IteratorOfPaths, "for a list and two pos ints",
[IsList, IsPosInt, IsPosInt],
function(out, u, v)
local n;
n := Length(out);
if not ForAll(out, x -> IsHomogeneousList(x)
and ForAll(x, y -> IsPosInt(y) and y <= n)) then
ErrorNoReturn("the 1st argument <out> must be a list of out-neighbours",
" of a digraph,");
elif not (u <= n and v <= n) then
ErrorNoReturn("the 2nd and 3rd arguments <u> and <v> must be vertices ",
"of the digraph defined by the 1st argument <out>,");
fi;
return IteratorOfPathsNC(out, u, v);
end);
InstallMethod(IteratorOfPathsNC, "for a list and two pos ints",
[IsList, IsPosInt, IsPosInt],
function(D, u, v)
local n, record;
n := Length(D);
# can assume that n > 0 since u and v are extant vertices of digraph
Assert(1, n > 0);
record := rec(adj := D,
start := u,
stop := v,
onpath := BlistList([1 .. n], []),
nbs := ListWithIdenticalEntries(n, 1));
record.NextIterator := function(iter)
local adj, path, ptr, nbs, level, stop, onpath, backtracked, j, k, current,
new, next, x;
adj := iter!.adj;
path := [iter!.start];
ptr := ListWithIdenticalEntries(n, 0);
nbs := iter!.nbs;
level := 1;
stop := iter!.stop;
onpath := iter!.onpath;
backtracked := false;
while true do
j := path[level];
k := nbs[j];
# Backtrack if vertex j is already in path, or it has no k^th neighbour
if (not ptr[j] = 0 or k > Length(adj[j])) then
if k > Length(adj[j]) then
nbs[j] := 1;
fi;
if k > Length(adj[j]) and onpath[j] then
ptr[j] := 0;
else
ptr[j] := 1;
fi;
level := level - 1;
backtracked := true;
if level = 0 then
# No more paths to be found
current := fail;
break;
fi;
# Backtrack and choose next available branch
Remove(path);
ptr[path[level]] := 0;
nbs[path[level]] := nbs[path[level]] + 1;
continue;
fi;
# Otherwise move into next available branch
# Check if new branch is a valid complete path
if adj[j][k] = stop then
current := [Concatenation(path, [adj[j][k]]), List(path, x -> nbs[x])];
nbs[j] := nbs[j] + 1;
# Everything in the path should keep its nbs
# but everything else should be back to 1
new := ListWithIdenticalEntries(n, 1);
for x in path do
onpath[x] := true;
new[x] := nbs[x];
od;
iter!.nbs := new;
iter!.onpath := onpath;
break;
fi;
ptr[j] := 2;
level := level + 1;
path[level] := adj[j][k];
# this is the troublesome line
if ptr[path[level]] = 0 and backtracked then
nbs[path[level]] := 1;
fi;
od;
if not IsBound(iter!.current) then
return current;
fi;
next := iter!.current;
iter!.current := current;
return next;
end;
record.current := record.NextIterator(record);
record.IsDoneIterator := function(iter)
if iter!.current = fail then
return true;
fi;
return false;
end;
record.ShallowCopy := function(iter)
return rec(adj := iter!.adj,
start := iter!.start,
stop := iter!.stop,
nbs := ShallowCopy(iter!.nbs),
onpath := ShallowCopy(iter!.onpath),
current := ShallowCopy(iter!.current));
end;
return IteratorByFunctions(record);
end);
InstallMethod(DigraphLongestDistanceFromVertex, "for a digraph and a pos int",
[IsDigraphByOutNeighboursRep, IsPosInt],
function(D, v)
local dist;
if not v in DigraphVertices(D) then
ErrorNoReturn("the 2nd argument <v> must be a vertex of the 1st ",
"argument <D>,");
fi;
dist := DIGRAPH_LONGEST_DIST_VERTEX(OutNeighbours(D), v);
if dist = -2 then
return infinity;
fi;
return dist;
end);
InstallMethod(DigraphRandomWalk,
"for a digraph, a pos int and a non-negative int",
[IsDigraph, IsPosInt, IsInt],
function(D, v, t)
local vertices, edge_indices, i, neighbours, index;
# Check input
if v > DigraphNrVertices(D) then
ErrorNoReturn("the 2nd argument <v> must be ",
"a vertex of the 1st argument <D>,");
elif t < 0 then
ErrorNoReturn("the 3rd argument <t> must be a non-negative int,");
fi;
# Prepare output lists
vertices := [v];
edge_indices := [];
# Iterate to desired length
for i in [1 .. t] do
neighbours := OutNeighboursOfVertex(D, v);
if IsEmpty(neighbours) then
break; # Sink: path ends here
fi;
# Follow a random edge
index := Random(1, Length(neighbours));
v := neighbours[index];
vertices[i + 1] := v;
edge_indices[i] := index;
od;
# Format matches that of DigraphPath
return [vertices, edge_indices];
end);
InstallMethod(DigraphLayers, "for a digraph, and a positive integer",
[IsDigraph, IsPosInt],
function(D, v)
local layers, gens, sch, trace, rep, word, orbs, layers_with_orbnums,
layers_of_v, i, x;
# TODO: make use of known distances matrix
if v > DigraphNrVertices(D) then
ErrorNoReturn("the 2nd argument <v> must be a vertex of the 1st ",
"argument <D>,");
fi;
layers := DIGRAPHS_Layers(D);
if IsBound(layers[v]) then
return layers[v];
elif HasDigraphGroup(D) then
gens := GeneratorsOfGroup(DigraphGroup(D));
sch := DigraphSchreierVector(D);
trace := DIGRAPHS_TraceSchreierVector(gens, sch, v);
rep := DigraphOrbitReps(D)[trace.representative];
word := DIGRAPHS_EvaluateWord(gens, trace.word);
if rep <> v then
layers[v] := List(DigraphLayers(D, rep),
x -> OnTuples(x, word));
return layers[v];
fi;
orbs := DIGRAPHS_Orbits(DigraphStabilizer(D, v),
DigraphVertices(D)).orbits;
else
rep := v;
orbs := List(DigraphVertices(D), x -> [x]);
fi;
# from now on rep = v
layers_with_orbnums := DIGRAPH_ConnectivityDataForVertex(D, v).layers;
layers_of_v := [[v]];
for i in [2 .. Length(layers_with_orbnums)] do
Add(layers_of_v, []);
for x in layers_with_orbnums[i] do
Append(layers_of_v[i], orbs[x]);
od;
od;
layers[v] := layers_of_v;
return layers[v];
end);
InstallMethod(DIGRAPHS_Layers, "for a digraph", [IsDigraph],
D -> EmptyPlist(0));
InstallMethod(DigraphDistanceSet,
"for a digraph, a vertex, and a non-negative integers",
[IsDigraph, IsPosInt, IsInt],
function(D, vertex, distance)
if vertex > DigraphNrVertices(D) then
ErrorNoReturn("the 2nd argument <vertex> must be a vertex of the ",
"digraph,");
elif distance < 0 then
ErrorNoReturn("the 3rd argument <distance> must be a non-negative ",
"integer,");
fi;
return DigraphDistanceSet(D, vertex, [distance]);
end);
InstallMethod(DigraphDistanceSet,
"for a digraph, a vertex, and a list of non-negative integers",
[IsDigraph, IsPosInt, IsList],
function(D, vertex, distances)
local layers;
if vertex > DigraphNrVertices(D) then
ErrorNoReturn("the 2nd argument <vertex> must be a vertex of ",
"the digraph,");
elif not ForAll(distances, x -> IsInt(x) and x >= 0) then
ErrorNoReturn("the 3rd argument <distances> must be a list of ",
"non-negative integers,");
fi;
--> --------------------
--> maximum size reached
--> --------------------
[ Dauer der Verarbeitung: 0.52 Sekunden
(vorverarbeitet)
]
|
2026-03-28
|
