Quelle digraph.gi Sprache: unbekannt

#############################################################################
##
##  digraph.gi
##  Copyright (C) 2014-21                                James D. Mitchell
##
##  Licensing information can be found in the README file of this package.
##
#############################################################################
##

########################################################################
# This file is organised as follows:
#
# 1.  Digraph types
# 2.  Digraph no-check constructors
# 3.  Digraph copies
# 4.  PostMakeImmutable
# 5.  Digraph constructors
# 6.  Printing, viewing, strings
# 7.  Operators
# 8.  Digraph by-something constructors
# 9.  Converters to/from other types -> digraph
# 10. Random digraphs
#
########################################################################

BindGlobal("DIGRAPHS_NamedDigraphs", fail);
BindGlobal("DIGRAPHS_NamedDigraphsTests", fail);

BindGlobal("DIGRAPHS_LoadNamedDigraphs", function()
  # Check if the database has already been loaded
  if DIGRAPHS_NamedDigraphs = fail then
    MakeReadWriteGlobal("DIGRAPHS_NamedDigraphs");
    UnbindGlobal("DIGRAPHS_NamedDigraphs");

    # Initialise empty record
    BindGlobal("DIGRAPHS_NamedDigraphs", rec());

    # Populate record with entries from the named digraphs main database
    Read(Concatenation(DIGRAPHS_Dir(), "/data/named-digraphs-main-database.g"));
  fi;
end);

BindGlobal("DIGRAPHS_LoadNamedDigraphsTests", function()
  # INTENDED ONLY FOR TESTING PURPOSES
  # Check if the database has already been loaded
  if DIGRAPHS_NamedDigraphsTests = fail then
    MakeReadWriteGlobal("DIGRAPHS_NamedDigraphsTests");
    UnbindGlobal("DIGRAPHS_NamedDigraphsTests");

    # Initialise empty record
    BindGlobal("DIGRAPHS_NamedDigraphsTests", rec());

    # Populate record with entries from the named digraphs test database
    Read(Concatenation(DIGRAPHS_Dir(), "/data/named-digraphs-test-database.g"));
  fi;
end);

InstallMethod(DigraphMutabilityFilter, "for a digraph", [IsDigraph],
function(D)
  if IsMutableDigraph(D) then
    return IsMutableDigraph;
  else
    return IsImmutableDigraph;
  fi;
end);

########################################################################
# 1. Digraph types
########################################################################

BindGlobal("DigraphByOutNeighboursType", NewType(DigraphFamily,
                                         IsDigraphByOutNeighboursRep));

########################################################################
# 2. Digraph no-check constructors
########################################################################

InstallMethod(ConvertToMutableDigraphNC, "for a record", [IsRecord],
function(record)
  local D;
  Assert(1, IsBound(record.OutNeighbours));
  Assert(1, Length(NamesOfComponents(record)) = 1);
  D := Objectify(DigraphByOutNeighboursType, record);
  SetFilterObj(D, IsMutable);
  return D;
end);

InstallMethod(ConvertToMutableDigraphNC, "for a dense list of out-neighbours",
[IsDenseList],
function(list)
  local record;
  record := rec(OutNeighbours := list);
  Perform(record.OutNeighbours, IsSet);
  return ConvertToMutableDigraphNC(record);
end);

InstallMethod(ConvertToImmutableDigraphNC, "for a record", [IsRecord],
record -> MakeImmutable(ConvertToMutableDigraphNC(record)));

InstallMethod(ConvertToImmutableDigraphNC,
"for a dense list of out-neighbours",
[IsDenseList],
list -> MakeImmutable(ConvertToMutableDigraphNC(list)));

InstallMethod(DigraphConsNC, "for IsMutableDigraph and a record",
[IsMutableDigraph, IsRecord],
function(_, record)
  local required, out, name;
  required := ["DigraphRange", "DigraphSource", "DigraphNrVertices"];
  for name in required do
    Assert(1, IsBound(record.(name)));
  od;
  for name in Difference(RecNames(record), required) do
    Info(InfoWarning, 1, "ignoring record component \"", name, "\"!");
  od;
  out := DIGRAPH_OUT_NEIGHBOURS_FROM_SOURCE_RANGE(record.DigraphNrVertices,
                                                  record.DigraphSource,
                                                  record.DigraphRange);
  return ConvertToMutableDigraphNC(out);
end);

InstallMethod(DigraphConsNC,
"for IsMutableDigraph and a dense list of out-neighbours",
[IsMutableDigraph, IsDenseList],
function(_, list)
  Assert(1, not IsMutable(list));
  return ConvertToMutableDigraphNC(List(list, ShallowCopy));
end);

InstallMethod(DigraphConsNC,
"for IsMutableDigraph and a dense mutable list of out-neighbours",
[IsMutableDigraph, IsDenseList and IsMutable],
{_, list} -> ConvertToMutableDigraphNC(StructuralCopy(list)));

InstallMethod(DigraphConsNC, "for IsImmutableDigraph and a record",
[IsImmutableDigraph, IsRecord],
function(_, record)
  local D;
  D := MakeImmutable(DigraphConsNC(IsMutableDigraph, record));
  SetDigraphSource(D, StructuralCopy(record.DigraphSource));
  SetDigraphRange(D, StructuralCopy(record.DigraphRange));
  return D;
end);

InstallMethod(DigraphConsNC, "for IsImmutableDigraph and a dense list",
[IsImmutableDigraph, IsDenseList],
{_, list} -> MakeImmutable(DigraphConsNC(IsMutableDigraph, list)));

InstallMethod(DigraphNC, "for a function and a dense list",
[IsFunction, IsDenseList], DigraphConsNC);

InstallMethod(DigraphNC, "for a dense list", [IsDenseList],
list -> DigraphConsNC(IsImmutableDigraph, list));

InstallMethod(DigraphNC, "for a function and a record",
[IsFunction, IsRecord], DigraphConsNC);

InstallMethod(DigraphNC, "for a record", [IsRecord],
record -> DigraphConsNC(IsImmutableDigraph, record));

########################################################################
# 3. Digraph copies
########################################################################

InstallMethod(DigraphMutableCopy, "for a digraph by out-neighbours",
[IsDigraphByOutNeighboursRep],
function(D)
  local copy;
  copy := ConvertToMutableDigraphNC(OutNeighboursMutableCopy(D));
  SetDigraphVertexLabels(copy, StructuralCopy(DigraphVertexLabels(D)));
  if HaveEdgeLabelsBeenAssigned(D) then
    SetDigraphEdgeLabelsNC(copy, StructuralCopy(DigraphEdgeLabelsNC(D)));
  fi;
  return copy;
end);

InstallMethod(DigraphImmutableCopy, "for a digraph by out-neighbours",
[IsDigraphByOutNeighboursRep],
function(D)
  local copy;
  copy := ConvertToImmutableDigraphNC(OutNeighboursMutableCopy(D));
  SetDigraphVertexLabels(copy, StructuralCopy(DigraphVertexLabels(D)));
  if HaveEdgeLabelsBeenAssigned(D) then
    SetDigraphEdgeLabelsNC(copy, StructuralCopy(DigraphEdgeLabelsNC(D)));
  fi;
  return copy;
end);

InstallMethod(DigraphCopySameMutability, "for a mutable digraph",
[IsMutableDigraph], DigraphMutableCopy);

InstallMethod(DigraphCopySameMutability, "for an immutable digraph",
[IsImmutableDigraph], DigraphImmutableCopy);

InstallMethod(DigraphImmutableCopyIfMutable, "for a mutable digraph",
[IsMutableDigraph], DigraphImmutableCopy);

InstallMethod(DigraphImmutableCopyIfMutable, "for an immutable digraph",
[IsImmutableDigraph], IdFunc);

InstallMethod(DigraphImmutableCopyIfImmutable, "for a mutable digraph",
[IsMutableDigraph], IdFunc);

InstallMethod(DigraphImmutableCopyIfImmutable, "for an immutable digraph",
[IsImmutableDigraph], DigraphImmutableCopy);

InstallMethod(DigraphMutableCopyIfImmutable, "for a mutable digraph",
[IsMutableDigraph], IdFunc);

InstallMethod(DigraphMutableCopyIfImmutable, "for an immutable digraph",
[IsImmutableDigraph], DigraphMutableCopy);

InstallMethod(DigraphMutableCopyIfMutable, "for a mutable digraph",
[IsMutableDigraph], DigraphMutableCopy);

InstallMethod(DigraphMutableCopyIfMutable, "for an immutable digraph",
[IsImmutableDigraph], IdFunc);

########################################################################
# 4. PostMakeImmutable
########################################################################

InstallMethod(PostMakeImmutable, "for a digraph",
[IsDigraph and IsDigraphByOutNeighboursRep],
function(D)
  MakeImmutable(D!.OutNeighbours);
  SetFilterObj(D, IsImmutableDigraph);
  SetFilterObj(D, IsAttributeStoringRep);
end);

########################################################################
# 5. Digraph constructors
########################################################################

InstallMethod(DigraphCons, "for IsMutableDigraph and a record",
[IsMutableDigraph, IsRecord],
function(_, record)
  local D, cmp, labels, i;

  if IsGraph(record) then
    # IsGraph is a function not a filter, so we cannot have a separate method
    D := DigraphNC(IsMutableDigraph,
                   List(Vertices(record), x -> Adjacency(record, x)));
    if IsBound(record.names) then
      SetDigraphVertexLabels(D, StructuralCopy(record.names));
    fi;
    return D;
  fi;

  if not (IsBound(record.DigraphSource)
          and IsBound(record.DigraphRange)
          and (IsBound(record.DigraphVertices) or
               IsBound(record.DigraphNrVertices))) then
    ErrorNoReturn("the argument <record> must be a record with components ",
                  "'DigraphSource', 'DigraphRange', and either ",
                  "'DigraphVertices' or 'DigraphNrVertices' (but not both),");
  elif not IsList(record.DigraphSource)
      or not IsList(record.DigraphRange) then
    ErrorNoReturn("the record components 'DigraphSource' and 'DigraphRange' ",
                  "must be lists,");
  elif Length(record.DigraphSource) <> Length(record.DigraphRange) then
    ErrorNoReturn("the record components 'DigraphSource' and 'DigraphRange' ",
                  "must have equal length,");
  elif IsBound(record.DigraphVertices)
      and IsBound(record.DigraphNrVertices) then
    ErrorNoReturn("the record must only have one of the components ",
                  "'DigraphVertices' and 'DigraphNrVertices', not both,");
  fi;

  if IsBound(record.DigraphNrVertices) then
    if (not IsInt(record.DigraphNrVertices))
        or record.DigraphNrVertices < 0 then
      ErrorNoReturn("the record component 'DigraphNrVertices' ",
                    "must be a non-negative integer,");
    fi;
    cmp := x -> IsPosInt(x) and x < record.DigraphNrVertices + 1;
  else
    Assert(1, IsBound(record.DigraphVertices));
    if not IsList(record.DigraphVertices) then
      ErrorNoReturn("the record component 'DigraphVertices' must be a list,");
    elif not IsDuplicateFreeList(record.DigraphVertices) then
      ErrorNoReturn("the record component 'DigraphVertices' must be ",
                    "duplicate-free,");
    fi;
    cmp := x -> x in record.DigraphVertices;
    record.DigraphNrVertices := Length(record.DigraphVertices);
  fi;

  if not ForAll(record.DigraphSource, cmp) then
    ErrorNoReturn("the record component 'DigraphSource' is invalid,");
  elif not ForAll(record.DigraphRange, cmp) then
    ErrorNoReturn("the record component 'DigraphRange' is invalid,");
  fi;

  record := StructuralCopy(record);

  # Rewrite the vertices to numbers
  if IsBound(record.DigraphVertices) then
    if record.DigraphVertices <> [1 .. record.DigraphNrVertices] then
      for i in [1 .. Length(record.DigraphSource)] do
        record.DigraphRange[i]  := Position(record.DigraphVertices,
                                            record.DigraphRange[i]);
        record.DigraphSource[i] := Position(record.DigraphVertices,
                                            record.DigraphSource[i]);
      od;
      labels := record.DigraphVertices;
      Unbind(record.DigraphVertices);
    fi;
  fi;

  record.DigraphRange := Permuted(record.DigraphRange,
                                  Sortex(record.DigraphSource));
  D := DigraphNC(IsMutableDigraph, record);
  if IsBound(labels) then
    SetDigraphVertexLabels(D, labels);
  fi;
  return D;
end);

InstallMethod(DigraphCons,
"for IsMutableDigraph and a dense list of out-neighbours",
[IsMutableDigraph, IsDenseList],
function(_, list)
  local sublist, v;
  for sublist in list do
    if not IsHomogeneousList(sublist) then
      ErrorNoReturn("the argument <list> must be a list of lists of positive ",
                    "integers not exceeding the length of the argument,");
    fi;
    for v in sublist do
      if not IsPosInt(v) or v > Length(list) then
        ErrorNoReturn("the argument <list> must be a list of lists of ",
                      "positive integers not exceeding the length of ",
                      "the argument,");
      fi;
    od;
  od;
  return DigraphNC(IsMutableDigraph, list);
end);

InstallMethod(DigraphCons, "for IsMutableDigraph, a list, and function",
[IsMutableDigraph, IsList, IsFunction],
function(_, list, func)
  local N, out, x, i, j;
  N    := Size(list);  # number of vertices
  out := List([1 .. N], x -> []);
  for i in [1 .. N] do
    x := list[i];
    for j in [1 .. N] do
      if func(x, list[j]) then
        Add(out[i], j);
      fi;
    od;
  od;
  return ConvertToMutableDigraphNC(out);
end);

InstallMethod(DigraphCons,
"for IsMutableDigraph, a number of vertices, source, and range",
[IsMutableDigraph, IsInt, IsList, IsList],
function(_, N, src, ran)
  return DigraphCons(IsMutableDigraph, rec(DigraphNrVertices := N,
                                           DigraphSource     := src,
                                           DigraphRange      := ran));
end);

InstallMethod(DigraphCons,
"for IsMutableDigraph, a list of vertices, source, and range",
[IsMutableDigraph, IsList, IsList, IsList],
function(_, domain, src, ran)
  local D;
  D := DigraphCons(IsMutableDigraph, rec(DigraphVertices := domain,
                                         DigraphSource   := src,
                                         DigraphRange    := ran));
  SetDigraphVertexLabels(D, domain);
  return D;
end);

InstallMethod(DigraphCons, "for IsImmutableDigraph and a record",
[IsImmutableDigraph, IsRecord],
function(_, record)
  local D;
  D := MakeImmutable(DigraphCons(IsMutableDigraph, record));
  if IsGraph(record) then
    # IsGraph is a function not a filter, so we cannot have a separate method
    # for this.
    if not IsTrivial(record.group) then
      Assert(1, IsPermGroup(record.group));
      SetDigraphGroup(D, record.group);
      SetDigraphSchreierVector(D, record.schreierVector);
      SetRepresentativeOutNeighbours(D, record.adjacencies);
    fi;
  else
    SetDigraphNrEdges(D, Length(record.DigraphSource));
  fi;
  return D;
end);

InstallMethod(DigraphCons,
"for IsImmutableDigraph and a dense list of out-neighbours",
[IsImmutableDigraph, IsDenseList],
{_, list} -> MakeImmutable(DigraphCons(IsMutableDigraph, list)));

InstallMethod(DigraphCons, "for IsImmutableDigraph, a list, and function",
[IsImmutableDigraph, IsList, IsFunction],
function(_, list, func)
  local D;
  D := MakeImmutable(DigraphCons(IsMutableDigraph, list, func));
  SetDigraphAdjacencyFunction(D, {u, v} -> func(list[u], list[v]));
  SetFilterObj(D, IsDigraphWithAdjacencyFunction);
  SetDigraphVertexLabels(D, list);
  return D;
end);

InstallMethod(DigraphCons,
"for IsImmutableDigraph, a number of vertices, source, and range",
[IsImmutableDigraph, IsInt, IsList, IsList],
{_, N, src, ran}
-> MakeImmutable(DigraphCons(IsMutableDigraph, N, src, ran)));

InstallMethod(DigraphCons,
"for IsImmutableDigraph, a list of vertices, source, and range",
[IsImmutableDigraph, IsList, IsList, IsList],
{_, domain, src, ran} ->
MakeImmutable(DigraphCons(IsMutableDigraph, domain, src, ran)));

InstallMethod(Digraph, "for a filter and a record", [IsFunction, IsRecord],
DigraphCons);

InstallMethod(Digraph, "for a record", [IsRecord],
record -> DigraphCons(IsImmutableDigraph, record));

InstallMethod(Digraph, "for a filter and a list", [IsFunction, IsList],
DigraphCons);

InstallMethod(Digraph, "for a list", [IsList],
list -> DigraphCons(IsImmutableDigraph, list));

InstallMethod(Digraph, "for a filter, a list, and a function",
[IsFunction, IsList, IsFunction],
DigraphCons);

InstallMethod(Digraph, "for a list and a function", [IsList, IsFunction],
{list, func} -> DigraphCons(IsImmutableDigraph, list, func));

InstallMethod(Digraph, "for a filter, integer, list, and list",
[IsFunction, IsInt, IsList, IsList],
DigraphCons);

InstallMethod(Digraph, "for an integer, list, and list",
[IsInt, IsList, IsList],
{n, src, ran} -> DigraphCons(IsImmutableDigraph, n, src, ran));

InstallMethod(Digraph, "for a filter, list, list, and list",
[IsFunction, IsList, IsList, IsList],
DigraphCons);

InstallMethod(Digraph, "for a list, list, and list", [IsList, IsList, IsList],
{dom, src, ran} -> DigraphCons(IsImmutableDigraph, dom, src, ran));

InstallMethod(Digraph, "for a string naming a digraph", [IsString],
function(name)
  # edge case to avoid interfering with Digraph([])
  if name = "" then
    TryNextMethod();
  fi;

  # standardise string format to search database
  name := LowercaseString(name);
  RemoveCharacters(name, " \n\t\r");

  # load database if not already done
  DIGRAPHS_LoadNamedDigraphs();

  if not name in RecNames(DIGRAPHS_NamedDigraphs) then
    ErrorNoReturn("named digraph <name> not found; see ListNamedDigraphs,");
  fi;
  return DigraphFromDiSparse6String(DIGRAPHS_NamedDigraphs.(name));
end);

InstallMethod(ListNamedDigraphs,
"for a string and a pos int",
[IsString, IsPosInt],
function(s, level)
  local l, cands, func;
  # standardise request
  s := LowercaseString(s);
  RemoveCharacters(s, " \n\t\r");
  l := Length(s);

  # load database if not already done
  DIGRAPHS_LoadNamedDigraphs();

  # retrieve candidates
  cands := RecNames(DIGRAPHS_NamedDigraphs);
  if l = 0 then
    return cands;
  fi;

  # print warning if level higher than ones here that have methods
  if level > 3 then
    Info(InfoWarning, 1, "ListNamedDigraphs: second argument <level> is");
    Info(InfoWarning, 1, "greater than level of greatest flexibility.");
    Info(InfoWarning, 1, "Using <level> = 3 instead.");
    level := 3;
  fi;

  if level = 1 then
    func := c -> Length(c) >= l and c{[1 .. l]} = s;
  elif level = 2 then
    func := c -> PositionSublist(c, s) <> fail;
  else
    s := Filtered(s, x -> IsDigitChar(x) or IsAlphaChar(x));
    func := c -> PositionSublist(Filtered(c, x -> IsDigitChar(x) or
                                                  IsAlphaChar(x)), s) <> fail;
  fi;
  return Filtered(cands, func);
end);

# if search function called with no level, assume a substring search with
# special chars
InstallMethod(ListNamedDigraphs, "for a string", [IsString],
x -> ListNamedDigraphs(x, 2));

########################################################################
# 6. Printing, viewing, strings
########################################################################

InstallMethod(ViewString, "for a digraph", [IsDigraph],
function(D)
  local n, m, suffix, display_nredges, display_digraph, displayed_bipartite,
  str, x;

  n := DigraphNrVertices(D);
  m := DigraphNrEdges(D);
  suffix := "";
  display_nredges := true;
  display_digraph := true;
  displayed_bipartite := false;

  str := "<";
  if IsMutableDigraph(D) then
    Append(str, "mutable ");
  elif IsImmutableDigraph(D) then
    Append(str, "immutable ");
  fi;

  Assert(1, IsMutableDigraph(D) or IsImmutableDigraph(D));

  if m = 0 then
    if IsImmutableDigraph(D) then
      SetIsEmptyDigraph(D, true);
    fi;
    Append(str, "empty ");
    display_nredges := false;
  elif n > 1 then
    if HasIsCycleDigraph(D) and IsCycleDigraph(D) then
      Append(str, "cycle ");
      display_nredges := false;
    elif HasIsChainDigraph(D) and IsChainDigraph(D) then
      Append(str, "chain ");
      display_nredges := false;
    elif HasIsCompleteDigraph(D) and IsCompleteDigraph(D) then
      Append(str, "complete ");
      display_nredges := false;
    elif HasIsCompleteBipartiteDigraph(D) and IsCompleteBipartiteDigraph(D) then
      Append(str, "complete bipartite ");
      displayed_bipartite := true;
    elif HasIsCompleteMultipartiteDigraph(D)
        and IsCompleteMultipartiteDigraph(D) then
      Append(str, "complete multipartite ");
    elif (HasIsJoinSemilatticeDigraph(D) and IsJoinSemilatticeDigraph(D))
        or (HasIsMeetSemilatticeDigraph(D) and IsMeetSemilatticeDigraph(D)) then
      if HasIsPlanarDigraph(D) and IsPlanarDigraph(D) then
        Append(str, "planar ");
      fi;
      if HasIsLatticeDigraph(D) and IsLatticeDigraph(D) then
        Append(str, "lattice ");
      elif HasIsJoinSemilatticeDigraph(D) and IsJoinSemilatticeDigraph(D) then
        Append(str, "join semilattice ");
      elif HasIsMeetSemilatticeDigraph(D) and IsMeetSemilatticeDigraph(D) then
        Append(str, "meet semilattice ");
      fi;
    elif (HasIsUndirectedTree(D) and IsUndirectedTree(D))
        or (HasIsDirectedTree(D) and IsDirectedTree(D)) then
      if HasIsUndirectedTree(D) and IsUndirectedTree(D) then
        Append(str, "un");
      fi;
      Append(str, "directed tree ");
      display_nredges := false;
      display_digraph := false;
    elif (HasIsUndirectedForest(D) and IsUndirectedForest(D))
        or (HasIsDirectedForest(D) and IsDirectedForest(D)) then
      if HasIsUndirectedForest(D) and IsUndirectedForest(D) then
        Append(str, "un");
      fi;
      Append(str, "directed forest ");
      display_nredges := false;
      display_digraph := false;
      if HasDigraphNrConnectedComponents(D) then
        suffix := Concatenation(String(DigraphNrConnectedComponents(D)),
                                " components");
      fi;
    elif HasIsTournament(D) and IsTournament(D) then
      Append(str, "tournament ");
      display_nredges := false;
      display_digraph := false;
    else
      if HasIsPlanarDigraph(D) and IsPlanarDigraph(D) then
        Append(str, "planar ");
      fi;
      if HasIsEulerianDigraph(D) and IsEulerianDigraph(D) then
        Append(str, "Eulerian ");
        if HasIsHamiltonianDigraph(D) and IsHamiltonianDigraph(D) then
          Append(str, "and ");
        fi;
      fi;
      if HasIsHamiltonianDigraph(D) and IsHamiltonianDigraph(D) then
        Append(str, "Hamiltonian ");
      fi;
      if HasIsStronglyConnectedDigraph(D) and IsStronglyConnectedDigraph(D)
          and not (HasIsEulerianDigraph(D) and IsEulerianDigraph(D))
          and not (HasIsHamiltonianDigraph(D) and IsHamiltonianDigraph(D))
          and not (HasIsSymmetricDigraph(D) and IsSymmetricDigraph(D)) then
        Append(str, "strongly connected ");
      fi;
      if HasIsBiconnectedDigraph(D) and IsBiconnectedDigraph(D) then
        Append(str, "biconnected ");
      elif ((HasIsSymmetricDigraph(D) and IsSymmetricDigraph(D))
            or not (HasIsStronglyConnectedDigraph(D)
                    and IsStronglyConnectedDigraph(D)))
          and not (HasIsTournament(D) and IsTournament(D))
          and not (HasIsHamiltonianDigraph(D) and IsHamiltonianDigraph(D))
          and not (HasIsEulerianDigraph(D) and IsEulerianDigraph(D))
          and HasIsConnectedDigraph(D) and IsConnectedDigraph(D) then
        Append(str, "connected ");
      fi;
      if HasIsBipartiteDigraph(D) and IsBipartiteDigraph(D) then
        Append(str, "bipartite ");
        displayed_bipartite := true;
      fi;
      if HasIsEdgeTransitive(D) and IsEdgeTransitive(D) and
          HasIsVertexTransitive(D) and IsVertexTransitive(D) then
        Append(str, "edge- and vertex-transitive ");
      elif HasIsEdgeTransitive(D) and IsEdgeTransitive(D) then
        Append(str, "edge-transitive ");
      elif HasIsVertexTransitive(D) and IsVertexTransitive(D) then
        Append(str, "vertex-transitive ");
      elif HasIsRegularDigraph(D) and IsRegularDigraph(D) then
        Append(str, "regular ");
      elif HasIsOutRegularDigraph(D) and IsOutRegularDigraph(D) then
        Append(str, "out-regular ");
      elif HasIsInRegularDigraph(D) and IsInRegularDigraph(D) then
        Append(str, "in-regular ");
      fi;
      if HasIsAcyclicDigraph(D) and IsAcyclicDigraph(D) then
        Append(str, "acyclic ");
      elif HasIsPartialOrderDigraph(D) and IsPartialOrderDigraph(D) then
        Append(str, "partial order ");
      elif HasIsEquivalenceDigraph(D) and IsEquivalenceDigraph(D) then
        Append(str, "equivalence ");
      elif HasIsFunctionalDigraph(D) and IsFunctionalDigraph(D) then
        Append(str, "functional ");
        display_nredges := false;
      elif HasIsPreorderDigraph(D) and IsPreorderDigraph(D) then
        Append(str, "preorder ");
      else
        if HasIsReflexiveDigraph(D) and IsReflexiveDigraph(D) then
          Append(str, "reflexive ");
        fi;
        if HasIsSymmetricDigraph(D) and IsSymmetricDigraph(D) then
          Append(str, "symmetric ");
        elif HasIsAntisymmetricDigraph(D) and IsAntisymmetricDigraph(D)
            and not (HasIsTournament(D) and IsTournament(D)) then
          Append(str, "antisymmetric ");
        fi;
        if HasIsTransitiveDigraph(D) and IsTransitiveDigraph(D) then
          Append(str, "transitive ");
        fi;
      fi;
    fi;
  fi;

  if IsMultiDigraph(D) then
    Append(str, "multi");
  fi;

  if display_digraph then
    Append(str, "digraph ");
  fi;
  Append(str, "with ");

  if displayed_bipartite then
    x := List(DigraphBicomponents(D), Length);
    Append(str, "bicomponent");
    if x[1] = x[2] then
      Append(str, "s of size ");
    else
      Append(str, " sizes ");
      Append(str, String(x[1]));
      Append(str, " and ");
    fi;
    Append(str, String(x[2]));
    Append(str, ">");
    return str;
  fi;

  Append(str, String(n));
  if n = 1 then
    Append(str, " vertex");
  else
    Append(str, " vertices");
  fi;
  if display_nredges then
    Append(str, ", ");
    Append(str, String(m));
    if m = 1 then
      Append(str, " edge");
    else
      Append(str, " edges");
    fi;
  fi;
  if not IsEmpty(suffix) then
    Append(str, ", ");
    Append(str, suffix);
  fi;
  Append(str, ">");
  return str;
end);

InstallMethod(PrintString, "for a digraph", [IsDigraph], String);

InstallMethod(String, "for a digraph",
[IsDigraph],
function(D)
  local n, N, i, mut, streps, outnbs_rep, lengths, strings,
        out_neighbours_string, creators_streps, creators_props, props;
  if IsMutableDigraph(D) then
    mut := "IsMutableDigraph, ";
  else
    mut := "";
  fi;
  if IsSymmetricDigraph(D) and not DigraphHasLoops(D) then
    streps := [Graph6String, Sparse6String];
    creators_streps := ["DigraphFromGraph6String",
                        "DigraphFromSparse6String"];
  else
    streps := [Digraph6String, DiSparse6String];
    creators_streps := ["DigraphFromDigraph6String",
                        "DigraphFromDiSparse6String"];
  fi;
  streps  := List(streps, f -> f(D));
  strings := [];
  for n in [1 .. Length(streps)] do
    Add(strings, Concatenation(creators_streps[n], "(", mut, "\"",
                 ReplacedString(streps[n], "\\", "\\\\"), "\"", ")"));
  od;

  out_neighbours_string := String(OutNeighbours(D));
  # print empty lists with two spaces for consistency
  # see https://github.com/gap-system/gap/pull/5418
  out_neighbours_string := ReplacedString(out_neighbours_string, "[ ]", "[  ]");
  outnbs_rep := Concatenation("Digraph(", mut, out_neighbours_string, ")");
  Add(strings, String(outnbs_rep));

  N              := DigraphNrVertices(D);
  props          := [x -> IsCycleDigraph(x)
                          and x = CycleDigraph(DigraphNrVertices(x)),
                     IsCompleteDigraph,
                     x -> IsChainDigraph(x)
                          and x = ChainDigraph(DigraphNrVertices(x)),
                     IsEmptyDigraph];
  creators_props := ["CycleDigraph",
                     "CompleteDigraph",
                     "ChainDigraph",
                     "EmptyDigraph"];
  for i in [1 .. Length(props)] do
    if props[i](D) then
      Add(strings, Concatenation(creators_props[i], "(", mut, String(N), ")"));
    fi;
  od;

  lengths := List(strings, Length);
  return strings[Position(lengths, Minimum(lengths))];
end);

########################################################################
# 7. Operators
########################################################################

InstallMethod(\=, "for two digraphs", [IsDigraph, IsDigraph], DIGRAPH_EQUALS);

InstallMethod(\<, "for two digraphs", [IsDigraph, IsDigraph], DIGRAPH_LT);

########################################################################
# 8. Digraph by-something constructors
########################################################################

InstallMethod(DigraphByAdjacencyMatrixConsNC,
"for IsMutableDigraph and a homogeneous list",
[IsMutableDigraph, IsHomogeneousList],
function(_, mat)
  local add_edge, n, list, i, j;

  if IsInt(mat[1][1]) then
    add_edge := function(i, j)
      local k;
      for k in [1 .. mat[i][j]] do
        Add(list[i], j);
      od;
    end;
  else  # boolean matrix
    add_edge := function(i, j)
      if mat[i][j] then
        Add(list[i], j);
      fi;
    end;
  fi;

  n := Length(mat);
  list := EmptyPlist(n);
  for i in [1 .. n] do
    list[i] := [];
    for j in [1 .. n] do
      add_edge(i, j);
    od;
  od;
  return DigraphNC(IsMutableDigraph, list);
end);

InstallMethod(DigraphByAdjacencyMatrixCons,
"for IsMutableDigraph and a homogeneous list",
[IsMutableDigraph, IsHomogeneousList],
function(_, mat)
  local n, i, j;
  n := Length(mat);
  if not IsRectangularTable(mat) or Length(mat[1]) <> n then
    ErrorNoReturn("the argument <mat> must be a square matrix,");
  elif not IsBool(mat[1][1]) then
    for i in [1 .. n] do
      for j in [1 .. n] do
        if not (IsInt(mat[i][j]) and mat[i][j] >= 0) then
          ErrorNoReturn("the argument <mat> must be a matrix of ",
                        "non-negative integers,");
        fi;
      od;
    od;
  fi;
  return DigraphByAdjacencyMatrixConsNC(IsMutableDigraph, mat);
end);

InstallMethod(DigraphByAdjacencyMatrixCons,
"for IsMutableDigraph and an empty list",
[IsMutableDigraph, IsList and IsEmpty], DigraphByAdjacencyMatrixConsNC);

InstallMethod(DigraphByAdjacencyMatrixConsNC,
"for IsMutableDigraph and an empty list",
[IsMutableDigraph, IsList and IsEmpty],
{_, dummy} -> EmptyDigraph(IsMutableDigraph, 0));

InstallMethod(DigraphByAdjacencyMatrixCons,
"for IsImmutableDigraph and a homogeneous list",
[IsImmutableDigraph, IsHomogeneousList],
function(_, mat)
  local D;
  D := MakeImmutable(DigraphByAdjacencyMatrixCons(IsMutableDigraph, mat));
  if IsEmpty(mat) or IsInt(mat[1][1]) then
    SetAdjacencyMatrix(D, mat);
  else
    Assert(1, IsBool(mat[1][1]));
    SetBooleanAdjacencyMatrix(D, mat);
  fi;
  return D;
end);

InstallMethod(DigraphByAdjacencyMatrix, "for a function and a homogeneous list",
[IsFunction, IsHomogeneousList],
DigraphByAdjacencyMatrixCons);

InstallMethod(DigraphByAdjacencyMatrix, "for a homogeneous list",
[IsHomogeneousList],
mat -> DigraphByAdjacencyMatrixCons(IsImmutableDigraph, mat));

InstallMethod(DigraphByEdgesCons,
"for IsMutableDigraph, a list, and an integer",
[IsMutableDigraph, IsList, IsInt],
function(_, edges, n)
  local pos, list, edge;
  if IsEmpty(edges) then
    return NullDigraph(IsMutableDigraph, n);
  fi;
  pos := 0;
  for edge in edges do
    pos := pos + 1;
    if not IsList(edge) then
      ErrorNoReturn("the 1st argument (list of edges) must be a list of ",
                    "lists, but found ",
                    TNAM_OBJ(edge),
                    " in position ",
                    pos);
    elif Length(edge) <> 2 then
      ErrorNoReturn("the 1st argument (list of edges) must be a list of lists ",
                    "of length 2, found ", edge, " (length ", Length(edge),
                    " in position ", pos, ")");
    elif not IsPosInt(edge[1]) or not IsPosInt(edge[2]) then
      ErrorNoReturn("the 1st argument (list of edges) must be pairs of ",
                    "positive integers but found ", edge, " in position ", pos);
    elif edge[1] > n or edge[2] > n then
      ErrorNoReturn("the 1st argument (list of edges) must be pairs of ",
                    "positive integers <= ", n, " but found ", edge,
                    " in position ", pos);
    fi;
  od;
  list := List([1 .. n], x -> []);
  for edge in edges do
    Add(list[edge[1]], edge[2]);
  od;
  return DigraphNC(IsMutableDigraph, list);
end);

InstallMethod(DigraphByEdgesCons, "for IsMutableDigraph and a list",
[IsMutableDigraph, IsList],
function(_, edges)
  local n;
  if IsEmpty(edges) then
    n := 0;
  else
    n := Maximum(List(edges, Maximum));
  fi;
  return DigraphByEdgesCons(IsMutableDigraph, edges, n);
end);

InstallMethod(DigraphByEdgesCons, "for an ImmutableDigraph and a list",
[IsImmutableDigraph, IsList],
function(_, edges)
  local D;
  D := MakeImmutable(DigraphByEdges(IsMutableDigraph, edges));
  SetDigraphEdges(D, edges);
  SetDigraphNrEdges(D, Length(edges));
  return D;
end);

InstallMethod(DigraphByEdgesCons,
"for IsImmutableDigraph, a list, and an integer",
[IsImmutableDigraph, IsList, IsInt],
function(_, edges, n)
  local D;
  D := MakeImmutable(DigraphByEdges(IsMutableDigraph, edges, n));
  SetDigraphEdges(D, edges);
  SetDigraphNrEdges(D, Length(edges));
  return D;
end);

InstallMethod(DigraphByEdges, "for a list and an integer",
[IsList, IsInt],
{edges, n} -> DigraphByEdgesCons(IsImmutableDigraph, edges, n));

InstallMethod(DigraphByEdges, "for a list", [IsList],
edges -> DigraphByEdgesCons(IsImmutableDigraph, edges));

InstallMethod(DigraphByEdges, "for a function, a list, and an integer",
[IsFunction, IsList, IsInt], DigraphByEdgesCons);

InstallMethod(DigraphByEdges, "for a function and a list",
[IsFunction, IsList], DigraphByEdgesCons);

InstallMethod(DigraphByInNeighboursCons, "for IsMutableDigraph, and a list",
[IsMutableDigraph, IsList],
function(_, list)
  local n, x;
  n := Length(list);  # number of vertices
  for x in list do
    if not ForAll(x, i -> IsPosInt(i) and i <= n) then
      ErrorNoReturn("the argument <list> must be a list of lists of positive ",
                    "integers not exceeding the length of the argument,");
    fi;
  od;
  return DigraphByInNeighboursConsNC(IsMutableDigraph, list);
end);

InstallMethod(DigraphByInNeighboursCons, "for IsImmutableDigraph and a list",
[IsImmutableDigraph, IsList],
function(_, list)
  local D;
  D := MakeImmutable(DigraphByInNeighboursCons(IsMutableDigraph, list));
  SetInNeighbours(D, list);
  return D;
end);

InstallMethod(DigraphByInNeighboursConsNC, "for IsMutableDigraph and a list",
[IsMutableDigraph, IsList],
{_, list} -> DigraphNC(IsMutableDigraph, DIGRAPH_IN_OUT_NBS(list)));

InstallMethod(DigraphByInNeighboursConsNC, "for IsImmutableDigraph and a list",
[IsImmutableDigraph, IsList],
function(_, list)
  local D;
  D := MakeImmutable(DigraphByInNeighboursConsNC(IsMutableDigraph, list));
  SetInNeighbours(D, list);
  return D;
end);

InstallMethod(DigraphByInNeighbours, "for a list", [IsList],
list -> DigraphByInNeighboursCons(IsImmutableDigraph, list));

InstallMethod(DigraphByInNeighbours, "for a function and a list",
[IsFunction, IsList],
DigraphByInNeighboursCons);

########################################################################
# 9. Converters to/from other types -> digraph . . .
########################################################################

InstallMethod(AsDigraphCons, "for IsMutableDigraph and a binary relation",
[IsMutableDigraph, IsBinaryRelation],
function(_, rel)
  local dom, list, i;
  dom := GeneratorsOfDomain(UnderlyingDomainOfBinaryRelation(rel));
  if not IsRange(dom) or dom[1] <> 1 then
    ErrorNoReturn("the argument <rel> must be a binary relation ",
                  "on the domain [1 .. n] for some positive integer n,");
  fi;
  list := EmptyPlist(Length(dom));
  for i in dom do
    list[i] := ImagesElm(rel, i);
  od;
  return Digraph(IsMutableDigraph, list);
end);

InstallMethod(AsDigraphCons, "for IsImmutableDigraph and a binary relation",
[IsImmutableDigraph, IsBinaryRelation],
function(_, rel)
  local D;
  D := MakeImmutable(AsDigraph(IsMutableDigraph, rel));
  SetIsMultiDigraph(D, false);
  if HasIsReflexiveBinaryRelation(rel) then
    SetIsReflexiveDigraph(D, IsReflexiveBinaryRelation(rel));
  fi;
  if HasIsSymmetricBinaryRelation(rel) then
    SetIsSymmetricDigraph(D, IsSymmetricBinaryRelation(rel));
  fi;
  if HasIsTransitiveBinaryRelation(rel) then
    SetIsTransitiveDigraph(D, IsTransitiveBinaryRelation(rel));
  fi;
  if HasIsAntisymmetricBinaryRelation(rel) then
    SetIsAntisymmetricDigraph(D, IsAntisymmetricBinaryRelation(rel));
  fi;
  return D;
end);

InstallMethod(AsDigraph, "for a binary relation", [IsBinaryRelation],
rel -> AsDigraphCons(IsImmutableDigraph, rel));

InstallMethod(AsDigraph, "for a function and a binary relation",
[IsFunction, IsBinaryRelation], AsDigraphCons);

InstallMethod(AsDigraphCons,
"for IsMutableDigraph, a transformation, and an integer",
[IsMutableDigraph, IsTransformation, IsInt],
function(_, f, n)
  local list, x, i;
  if n < 0 then
    ErrorNoReturn("the 2nd argument <n> should be a non-negative integer,");
  fi;

  list := EmptyPlist(n);
  for i in [1 .. n] do
    x := i ^ f;
    if x > n then
      return fail;
    fi;
    list[i] := [x];
  od;
  return DigraphNC(IsMutableDigraph, list);
end);

InstallMethod(AsDigraphCons,
"for IsImmutableDigraph, a transformation, and an integer",
[IsImmutableDigraph, IsTransformation, IsInt],
function(_, f, n)
  local D;
  D := AsDigraph(IsMutableDigraph, f, n);
  if D <> fail then
    D := MakeImmutable(D);
    SetDigraphNrEdges(D, n);
    SetIsMultiDigraph(D, false);
    SetIsFunctionalDigraph(D, true);
  fi;
  return D;
end);

InstallMethod(AsDigraph, "for a function, a transformation, and an integer",
[IsFunction, IsTransformation, IsInt], AsDigraphCons);

InstallMethod(AsDigraph, "for a transformation and an integer",
[IsTransformation, IsInt],
{t, n} -> AsDigraphCons(IsImmutableDigraph, t, n));

InstallMethod(AsDigraph, "for a function and a transformation",
[IsFunction, IsTransformation],
{func, t} -> AsDigraphCons(func, t, DegreeOfTransformation(t)));

InstallMethod(AsDigraph, "for a transformation", [IsTransformation],
t -> AsDigraphCons(IsImmutableDigraph, t, DegreeOfTransformation(t)));

InstallMethod(AsDigraph, "for a function, a perm, and an integer",
[IsFunction, IsPerm, IsInt],
{func, p, n} -> AsDigraphCons(func, AsTransformation(p), n));

InstallMethod(AsDigraph, "for a perm and an integer",
[IsPerm, IsInt],
{p, n} -> AsDigraph(AsTransformation(p), n));

InstallMethod(AsDigraph, "for a function and a perm",
[IsFunction, IsPerm],
{func, p} -> AsDigraph(func, AsTransformation(p)));

InstallMethod(AsDigraph, "for a perm", [IsPerm],
p -> AsDigraph(AsTransformation(p)));

InstallMethod(AsDigraphCons,
"for IsMutableDigraph, a partial perm, and an integer",
[IsMutableDigraph, IsPartialPerm, IsInt],
function(_, f, n)
  local list, x, i;
  if n < 0 then
    ErrorNoReturn("the 2nd argument <n> should be a non-negative integer,");
  fi;

  list := EmptyPlist(n);
  for i in [1 .. n] do
    x := i ^ f;
    if x > n then
      return fail;
    elif x <> 0 then
      list[i] := [x];
    else
      list[i] := [];
    fi;
  od;
  return DigraphNC(IsMutableDigraph, list);
end);

InstallMethod(AsDigraphCons,
"for IsImmutableDigraph, a partial perm, and an integer",
[IsImmutableDigraph, IsPartialPerm, IsInt],
function(_, f, n)
  local D;
  D := AsDigraph(IsMutableDigraph, f, n);
  if D <> fail then
    D := MakeImmutable(D);
    SetIsMultiDigraph(D, false);
  fi;
  return D;
end);

InstallMethod(AsDigraph, "for a function, a partial perm, and an integer",
[IsFunction, IsPartialPerm, IsInt], AsDigraphCons);

InstallMethod(AsDigraph, "for a partial perm and an integer",
[IsPartialPerm, IsInt],
{t, n} -> AsDigraphCons(IsImmutableDigraph, t, n));

InstallMethod(AsDigraph, "for a function and a partial perm",
[IsFunction, IsPartialPerm],
{func, t} -> AsDigraphCons(func, t, Maximum(DegreeOfPartialPerm(t),
                                            CodegreeOfPartialPerm(t))));

InstallMethod(AsDigraph, "for a partial perm", [IsPartialPerm],
t -> AsDigraphCons(IsImmutableDigraph, t, Maximum(DegreeOfPartialPerm(t),
                                                  CodegreeOfPartialPerm(t))));

InstallMethod(AsBinaryRelation, "for a digraph", [IsDigraphByOutNeighboursRep],
function(D)
  local rel;
  if DigraphHasNoVertices(D) then
    ErrorNoReturn("the argument <D> must be a digraph with at least 1 ",
                  "vertex,");
  elif IsMultiDigraph(D) then
    ErrorNoReturn("the argument <D> must be a digraph with no multiple edges");
  fi;
  # Can translate known attributes of <D> to the relation, e.g. symmetry
  rel := BinaryRelationOnPointsNC(OutNeighbours(D));
  if HasIsReflexiveDigraph(D) then
    SetIsReflexiveBinaryRelation(rel, IsReflexiveDigraph(D));
  fi;
  if HasIsSymmetricDigraph(D) then
    SetIsSymmetricBinaryRelation(rel, IsSymmetricDigraph(D));
  fi;
  if HasIsTransitiveDigraph(D) then
    SetIsTransitiveBinaryRelation(rel, IsTransitiveDigraph(D));
  fi;
  if HasIsAntisymmetricDigraph(D) then
    SetIsAntisymmetricBinaryRelation(rel, IsAntisymmetricDigraph(D));
  fi;
  return rel;
end);

InstallMethod(AsSemigroup, "for a function and a digraph",
[IsFunction, IsDigraph],
function(filt, D)
  local red, top, im, max, n, gens, i;

  if filt <> IsPartialPermSemigroup then
    TryNextMethod();
  elif not IsJoinSemilatticeDigraph(D) then
    if IsMeetSemilatticeDigraph(D) then
      return AsSemigroup(IsPartialPermSemigroup,
                         DigraphReverse(DigraphMutableCopyIfMutable(D)));
    fi;
    ErrorNoReturn("the 2nd argument <D> must be digraph that is a join or ",
                  "meet semilattice,");
  fi;

  D   := DigraphMutableCopyIfMutable(D);
  red := DigraphReflexiveTransitiveReduction(D);
  top := DigraphTopologicalSort(D);
  # im[i] will store the image of the idempotent partial perm corresponding to
  # vertex i of the argument <D>
  im         := [];
  im[top[1]] := [];
  max        := 1;

  n := DigraphNrVertices(D);
  # For each vertex, the corresponding idempotent has an image
  # containing all images of idempotents below it.
  for i in [2 .. n] do
    im[top[i]] := Union(List(OutNeighboursOfVertex(red, top[i]), j -> im[j]));
    # When there is only one neighbour, we must add a point to the image to
    # distinguish the two idempotent partial perms.
    if Length(OutNeighboursOfVertex(red, top[i])) = 1 then
      Add(im[top[i]], max);
      max := max + 1;
    fi;
  od;

  # Determine a small generating set
  gens := Filtered([1 .. n], j -> Size(InNeighboursOfVertex(red, j)) < 2);
  return Semigroup(List(gens, g -> PartialPerm(im[g], im[g])));
end);

InstallMethod(AsMonoid, "for a function and a digraph",
[IsFunction, IsDigraph],
function(filt, D)
  if not (filt = IsPartialPermMonoid or filt = IsPartialPermSemigroup) then
    ErrorNoReturn("the 1st argument <filt> must be IsPartialPermMonoid or ",
                  "IsPartialPermSemigroup,");
  elif not IsLatticeDigraph(D) then
    ErrorNoReturn("the 2nd argument <D> must be a lattice digraph,");
  fi;
  return AsSemigroup(IsPartialPermSemigroup, D);
end);

InstallMethod(AsSemigroup,
"for a function, a digraph, and a dense list",
[IsFunction, IsDigraph, IsDenseList, IsDenseList],
function(filt, digraph, gps, homs)
  local red, n, hom_table, reps, rep, top, doms, starts, degs, max, gens, img,
  start, deg, x, queue, j, k, g, y, hom, edge, i, gen;

  if filt <> IsPartialPermSemigroup then
    TryNextMethod();
  elif not IsJoinSemilatticeDigraph(digraph) then
    if IsMeetSemilatticeDigraph(digraph) then
      return AsSemigroup(IsPartialPermSemigroup,
                         DigraphReverse(DigraphMutableCopyIfMutable(digraph)),
                         gps,
                         homs);
    else
      ErrorNoReturn("the second argument must be a join semilattice ",
                    "digraph or a meet semilattice digraph,");
    fi;
  elif not ForAll(gps, IsGroup) then
    ErrorNoReturn("the third argument must be a list of groups,");
  elif not Length(gps) = DigraphNrVertices(digraph) then
    ErrorNoReturn("the third argument must have length equal to the number ",
                  "of vertices in the second argument,");
  fi;

  digraph := DigraphMutableCopyIfMutable(digraph);
  red := DigraphReflexiveTransitiveReduction(digraph);
  MakeImmutable(digraph);
  if not Length(homs) = DigraphNrEdges(red) or
       not ForAll(homs, x -> Length(x) = 3 and
                             IsPosInt(x[1]) and
                             IsPosInt(x[2]) and
                             IsDigraphEdge(red, [x[1], x[2]]) and
                             IsGroupHomomorphism(x[3]) and
                             Source(x[3]) = gps[x[1]] and
                             Range(x[3]) = gps[x[2]]) then
    ErrorNoReturn("the third argument must be a list of triples [i, j, hom] ",
                  "of length equal to the number of edges in the reflexive ",
                  "transitive reduction of the second argument, where [i, j] ",
                  "is an edge in the reflex transitive reduction and hom is ",
                  "a group homomorphism from group i to group j,");
  fi;

  n := DigraphNrVertices(digraph);

  hom_table := List([1 .. n], x -> []);
  for hom in homs do
    hom_table[hom[1]][hom[2]] := hom[3];
  od;

  for edge in DigraphEdges(red) do
    if not IsBound(hom_table[edge[1]][edge[2]]) then
      ErrorNoReturn("the fourth argument must contain a triple [i, j, hom] ",
                    "for each edge [i, j] in the reflexive transitive ",
                    "reduction of the second argument,");
    fi;
  od;

  reps := [];
  for i in [1 .. n] do
    rep := IsomorphismPermGroup(gps[i]);
    rep := rep * SmallerDegreePermutationRepresentation(Image(rep));
    Add(reps, rep);
  od;

  top     := DigraphTopologicalSort(digraph);
  doms    := [];
  starts  := [];
  degs    := List([1 .. n], i -> NrMovedPoints(Image(reps[i])));
  for i in [1 .. n] do
    if degs[i] = 0 then
      degs[i] := 1;
    fi;
  od;
  max             := degs[top[1]] + 1;
  doms[top[1]]    := [1 .. max - 1];
  starts[top[1]]  := 1;

  for i in [2 .. n] do
    doms[top[i]] := Union(List(OutNeighboursOfVertex(red, top[i]),
                               j -> doms[j]));
    Append(doms[top[i]], [max .. max + degs[top[i]] - 1]);
    starts[top[i]] := max;
    max := max + degs[top[i]];
  od;

  gens := [];
  for i in [1 .. n] do
    for gen in GeneratorsOfGroup(gps[top[i]]) do
      img := [];
      start := starts[top[i]];
      deg := degs[top[i]];
      x := ListPerm(gen ^ reps[top[i]]);

      # make sure the partial permutation is defined on the whole domain
      img{[start .. start + deg - 1]} := [1 .. deg] + start - 1;
      # now the actual representation
      img{[start .. start + Length(x) - 1]} := x + start - 1;

      # travel up all the paths from top[i], applying the homomorphisms
      # and storing the results as permutations on the appropriate set
      # of points
      queue := List(OutNeighboursOfVertex(red, top[i]), y -> [top[i], y, gen]);
      while Length(queue) > 0 do
        j     := queue[1][1];
        k     := queue[1][2];
        g     := queue[1][3];
        start := starts[k];
        deg   := degs[k];
        Remove(queue, 1);
        x := g ^ hom_table[j][k];
        Append(queue, List(OutNeighboursOfVertex(red, k), y -> [k, y, x]));
        x := x ^ reps[k];

        # Check that compositions of homomorphisms commute.
        # If img[start] is bound then we have already found some composition of
        # homomorphisms which takes us into gps[k], so we must ensure that this
        # agrees with the composition we are currently considering.
        if IsBound(img[start]) then
          y := PermList(img{[start .. start + deg - 1]} - start + 1);
          if x <> y then
            ErrorNoReturn("the homomorphisms given must form a commutative",
                          " diagram,");
          fi;
        fi;
        x := ListPerm(x);
        img{[start .. start + deg - 1]} := [1 .. deg] + start - 1;
        img{[start .. start + Length(x) - 1]} := x + start - 1;
      od;
      img := Compacted(img);
      Add(gens, PartialPerm(doms[top[i]], img));
    od;
  od;
  return Semigroup(gens);
end);

########################################################################
# 10. Random digraphs
########################################################################

InstallMethod(RandomDigraphCons, "for IsMutableDigraph and an integer",
[IsMutableDigraph, IsInt],
{_, n}
-> RandomDigraphCons(IsMutableDigraph, n, Float(Random(0, n ^ 2) / n ^ 2)));

InstallMethod(RandomDigraphCons, "for IsMutableDigraph and an integer",
[IsImmutableDigraph, IsInt],
{_, n}
-> RandomDigraphCons(IsImmutableDigraph, n, Float(Random(0, n ^ 2) / n ^ 2)));

InstallMethod(RandomDigraphCons, "for IsHamiltonianDigraph and an integer",
[IsHamiltonianDigraph, IsInt],
{_, n}
-> RandomDigraphCons(IsHamiltonianDigraph, n, Float(Random(0, n ^ 2) / n ^ 2)));

InstallMethod(RandomDigraphCons, "for IsEulerianDigraph and an integer",
[IsEulerianDigraph, IsInt],
{_, n}
-> RandomDigraphCons(IsEulerianDigraph, n, Float(Random(0, n ^ 2) / n ^ 2)));

InstallMethod(RandomDigraphCons, "for IsConnectedDigraph and an integer",
[IsConnectedDigraph, IsInt],
{_, n}
-> RandomDigraphCons(IsConnectedDigraph, n, Float(Random(0, n ^ 2) / n ^ 2)));

InstallMethod(RandomDigraphCons, "for IsAcyclicDigraph and an integer",
[IsAcyclicDigraph, IsInt],
{_, n}
-> RandomDigraphCons(IsAcyclicDigraph, n, Float(Random(0, n ^ 2) / n ^ 2)));

InstallMethod(RandomDigraphCons, "for IsSymmetricDigraph and an integer",
[IsSymmetricDigraph, IsInt],
{_, n}
-> RandomDigraphCons(IsSymmetricDigraph, n, Float(Random(0, n ^ 2) / n ^ 2)));

InstallMethod(RandomDigraphCons,
"for IsMutableDigraph, an integer, and a rational",
[IsMutableDigraph, IsInt, IsRat],
{_, n, p} -> RandomDigraphCons(IsMutableDigraph, n, Float(p)));

InstallMethod(RandomDigraphCons,
"for IsImmutableDigraph, an integer, and a rational",
[IsImmutableDigraph, IsInt, IsRat],
{_, n, p} -> RandomDigraphCons(IsImmutableDigraph, n, Float(p)));

InstallMethod(RandomDigraphCons,
"for IsHamiltonianDigraph, an integer, and a rational",
[IsHamiltonianDigraph, IsInt, IsRat],
{_, n, p} -> RandomDigraphCons(IsHamiltonianDigraph, n, Float(p)));

InstallMethod(RandomDigraphCons,
"for IsEulerianDigraph, an integer, and a rational",
[IsEulerianDigraph, IsInt, IsRat],
{_, n, p} -> RandomDigraphCons(IsEulerianDigraph, n, Float(p)));

InstallMethod(RandomDigraphCons,
"for IsConnectedDigraph, an integer, and a rational",
[IsConnectedDigraph, IsInt, IsRat],
{_, n, p} -> RandomDigraphCons(IsConnectedDigraph, n, Float(p)));

InstallMethod(RandomDigraphCons,
"for IsStronglyConnectedDigraph, an integer, and a rational",
[IsStronglyConnectedDigraph, IsInt, IsRat],
{filt, n, p} -> RandomDigraphCons(IsStronglyConnectedDigraph, n, Float(p)));

InstallMethod(RandomDigraphCons,
"for IsAcyclicDigraph, an integer, and a rational",
[IsAcyclicDigraph, IsInt, IsRat],
{_, n, p} -> RandomDigraphCons(IsAcyclicDigraph, n, Float(p)));

InstallMethod(RandomDigraphCons,
"for IsSymmetricDigraph, an integer, and a rational",
[IsSymmetricDigraph, IsInt, IsRat],
{_, n, p} -> RandomDigraphCons(IsSymmetricDigraph, n, Float(p)));

InstallMethod(RandomDigraphCons,
"for IsMutableDigraph, a positive integer, and a float",
[IsMutableDigraph, IsPosInt, IsFloat],
function(_, n, p)
  if p < 0.0 or 1.0 < p then
    ErrorNoReturn("the 2nd argument <p> must be between 0 and 1,");
  fi;
  return DigraphNC(IsMutableDigraph, RANDOM_DIGRAPH(n, p));
end);

# This function takes an existing adjacency list after solely creating
# a Hamiltonian cycle or tree, and randomly adds edges between all
# remaining vertices in the graph.
BindGlobal("DIGRAPHS_FillOutGraph", function(n, p, adjacencyList)
    local vertices, probability, i, j;

    vertices := [1 .. n];
    probability := [0 .. 99];

    for i in vertices do
        for j in vertices do
            if (not (j in adjacencyList[i])) then
                 if Float(Random(probability) / 100) < p then
                    Add(adjacencyList[i], j);
                 fi;
            fi;
        od;
    od;

    return adjacencyList;
end);

InstallMethod(RandomDigraphCons,
"for IsHamiltonianDigraph, a positive integer, and a float",
[IsHamiltonianDigraph, IsPosInt, IsFloat],
function(_, n, p)
    local adjacencyList, vertices, i, startVertex, hamiltonianCycle, x, j;

    adjacencyList := EmptyPlist(n);

    vertices := [1 .. n];

    for i in vertices do
        Add(adjacencyList, []);
    od;

    # Edge Case
    if n = 1 then
        if Float(Random([0 .. 99]) / 100) < p then
            Add(adjacencyList[1], 1);
        fi;
        return DigraphNC(adjacencyList);
    fi;

    # Starting from a random vertex, we create a Hamiltonian cycle
    startVertex := Remove(vertices, Random(vertices));
    hamiltonianCycle := EmptyPlist(n);
    hamiltonianCycle[1] := startVertex;

    # While there are remaining n-1 vertices to be added to the Hamiltonian
    # cycle
    for x in [1 .. n - 1] do
        # Create a random edge from the last vertex in the cycle
        # to a random vertex not in the cycle
        i := hamiltonianCycle[x];
        j := Remove(vertices, Random([1 .. Length(vertices)]));
        Add(hamiltonianCycle, j);
        Add(adjacencyList[i], j);
    od;

    Add(adjacencyList[hamiltonianCycle[n]], startVertex);

    # Once we have created a Hamiltonian cycle, fill out the rest of the graph
    # with random edges according to p
    adjacencyList := DIGRAPHS_FillOutGraph(n, p, adjacencyList);

    return DigraphNC(adjacencyList);
end);

InstallMethod(RandomDigraphCons,
"for IsEulerianDigraph, a positive integer, and a float",
[IsEulerianDigraph, IsPosInt, IsFloat],
function(_, n, p)
    local adjacencyList, vertices, probability, startVertex, circuitVertex, i,
    continueCircuit, verticesToConsider, connectedVertices, verticesToCheck;

    adjacencyList := EmptyPlist(n);

    vertices := [1 .. n];
    probability := [0 .. 99];

    for i in vertices do
        Add(adjacencyList, []);
    od;

    # Edge Case
    if n = 1 then
        if Float(Random(probability) / 100) < p then
            Add(adjacencyList[1], 1);
        fi;
        return DigraphNC(adjacencyList);
    fi;

    # Starting from a random vertex, we create an Eulerian circuit
    startVertex := Random(vertices);
    circuitVertex := startVertex;
    continueCircuit := true;

    # This will keep track of the vertices left to consider when deciding
    # whether to extend the cycle. For example, if we want to extend from the
    # current circuitVertex, we can check - verticesToConsider[circuitVertex] -
    # to see which vertices it hasn't previously considered.
    verticesToConsider := EmptyPlist(n);
    for i in vertices do
        Add(verticesToConsider, [1 .. n]);
    od;

    # Eulerian graphs must be connected, so we store a list of connected
    # vertices and check if a vertex isn't in the list
    connectedVertices := [startVertex];

    while continueCircuit do
        while Length(verticesToConsider[circuitVertex]) > 0 do
            # From the remaining vertices to check, select a random one to see
            # if an edge will be added
            i := Random(verticesToConsider[circuitVertex]);
            Remove(verticesToConsider[circuitVertex],
            Position(verticesToConsider[circuitVertex], i));

            # Check that the edge doesn't already exist
            if (not (i in adjacencyList[circuitVertex])) then
                # First we guarantee that we get a connected graph by checking
                # if the vertex isn't already connected
                if (not (i in connectedVertices)) then
                    Add(adjacencyList[circuitVertex], i);
                    Add(connectedVertices, i);
                    circuitVertex := i;
                    break;
                elif Float(Random(probability) / 100) < p then
                    Add(adjacencyList[circuitVertex], i);
                    circuitVertex := i;
                    break;
                fi;
            fi;
        od;

        # If there are not more vertices to consider, we can end the circuit
        if Length(verticesToConsider[circuitVertex]) = 0 then
            continueCircuit := false;
        fi;
    od;

    # Finish the circuit by adding an edge back to the start vertex
    # (if it isn't already at the start vertex)
    if circuitVertex <> startVertex then
        # If an edge already exists between the finish vertex and the start
        # vertex, we must find another path to the start vertex to avoid
        # generating a multidigraph.
        while (startVertex in adjacencyList[circuitVertex]) do
            # Here we consider all possible edges again, including previously
            # rejected edges, to guarantee a path back to the start
            verticesToCheck := [1 .. n];
            while Length(verticesToCheck) > 0 do
                i := Remove(verticesToCheck,
                            Random([1 .. Length(verticesToCheck)]));
                if (not (i in adjacencyList[circuitVertex])) then
                    Add(adjacencyList[circuitVertex], i);
                    circuitVertex := i;
                    break;
                fi;
            od;
        od;
        Add(adjacencyList[circuitVertex], startVertex);
    fi;

    return DigraphNC(adjacencyList);
end);

InstallMethod(RandomDigraphCons,
"for IsConnectedDigraph, a positive integer, and a float",
[IsConnectedDigraph, IsPosInt, IsFloat],
function(_, n, p)
    local adjacencyList, vertices, startVertex, tree, x, i, j;

    adjacencyList := EmptyPlist(n);

    vertices := [1 .. n];

    for i in vertices do
        Add(adjacencyList, []);
    od;

    # Starting from a random vertex, we first create a tree to guarantee
    # connectivity
    startVertex := Remove(vertices, Random(vertices));
    tree := [startVertex];

    # While there are n-1 remaining vertices to be added to the tree
    for x in [1 .. n - 1] do
        # Create an edge from a random vertex in the tree, to a random vertex
        # outside of it
        i := Random(tree);
        j := Remove(vertices, Random([1 .. Length(vertices)]));
        Add(tree, j);
        Add(adjacencyList[i], j);
    od;

    # Once the tree has been created, we fill out the rest of the graph with
    # random edges according to p
    adjacencyList := DIGRAPHS_FillOutGraph(n, p, adjacencyList);
    return DigraphNC(adjacencyList);
end);

InstallMethod(RandomDigraphCons,
"for IsStronglyConnectedDigraph, a positive integer, and a float",
[IsStronglyConnectedDigraph, IsPosInt, IsFloat],
function(_, n, p)
  local d, adjMatrix, stronglyConnectedComponents,
  scc_a, scc_b, i, random_u, random_v;

  d := RandomDigraph(n, p);

  stronglyConnectedComponents := DigraphStronglyConnectedComponents(d);

  adjMatrix := AdjacencyMatrixMutableCopy(d);

  for i in [1 .. Size(stronglyConnectedComponents.comps) - 1] do
      scc_a := stronglyConnectedComponents.comps[i];
      scc_b := stronglyConnectedComponents.comps[i + 1];

      # add a connection from u to v
      random_u := Random(scc_a);
      random_v := Random(scc_b);

      adjMatrix[random_u][random_v] := 1;
  od;

  # connect end scc to first scc
  scc_a := stronglyConnectedComponents.comps[
    Size(stronglyConnectedComponents.comps)];
  scc_b := stronglyConnectedComponents.comps[1];

  # add a connection from u to v
  random_u := Random(scc_a);
  random_v := Random(scc_b);

  adjMatrix[random_u][random_v] := 1;

  return DigraphByAdjacencyMatrix(adjMatrix);
end);

InstallMethod(RandomDigraphCons,
"for IsAcyclicDigraph, a positive integer, and a float",
[IsAcyclicDigraph, IsPosInt, IsFloat],
function(_, n, p)
    local adjacencyList, vertices, probability, i, j;

    adjacencyList := EmptyPlist(n);

    vertices := [1 .. n];
    probability := [0 .. 99];

    for i in vertices do
        Add(adjacencyList, []);
    od;

    # We shuffle the vertices and treat the order of the vertices as a
    # hierarchy where all vertices to the right of a vertex in the list are
    # potential edges. This idea is that the edges flow downwards in the
    # hierarchy, avoiding cycles.
    Shuffle(vertices);

    # From position i in the list, we consider all vertices j to the right of i
    for i in vertices do
        for j in [i + 1 .. n] do
            if Float(Random(probability) / 100) < p then
                Add(adjacencyList[vertices[i]], vertices[j]);
            fi;
        od;
    od;

    return DigraphNC(adjacencyList);
end);

InstallMethod(RandomDigraphCons,
"for IsSymmetricDigraph, a positive integer, and a float",
[IsSymmetricDigraph, IsPosInt, IsFloat],
function(_, n, p)
    local adjacencyList, vertices, probability, i, j;

    adjacencyList := EmptyPlist(n);

    vertices := [1 .. n];
    probability := [0 .. 99];

    for i in vertices do
        Add(adjacencyList, []);
    od;

    for i in vertices do
        for j in [i .. n] do
            if Float(Random(probability) / 100) < p then
                # If it's a self-loop, only add one edge otherwise we would
                # have a multi-edge.
                if i = j then
                    Add(adjacencyList[i], j);
                else
                    Add(adjacencyList[i], j);
                    Add(adjacencyList[j], i);
                fi;
            fi;
        od;
    od;

    return DigraphNC(adjacencyList);
end);

InstallMethod(RandomDigraphCons,
"for IsImmutableDigraph, a positive integer, and a float",
[IsImmutableDigraph, IsPosInt, IsFloat],
function(_, n, p)
  local D;
  D := MakeImmutable(RandomDigraphCons(IsMutableDigraph, n, p));
  SetIsMultiDigraph(D, false);
  return D;
end);

InstallMethod(RandomDigraph, "for a pos int", [IsPosInt],
n -> RandomDigraphCons(IsImmutableDigraph, n));

InstallMethod(RandomDigraph, "for a pos int and a rational", [IsPosInt, IsRat],
{n, p} -> RandomDigraphCons(IsImmutableDigraph, n, p));

InstallMethod(RandomDigraph, "for a pos int and a float", [IsPosInt, IsFloat],
{n, p} -> RandomDigraphCons(IsImmutableDigraph, n, p));

InstallMethod(RandomDigraph, "for a func and a pos int", [IsFunction, IsPosInt],
RandomDigraphCons);

InstallMethod(RandomDigraph, "for a func, a pos int, and a rational",
[IsFunction, IsPosInt, IsRat], RandomDigraphCons);

InstallMethod(RandomDigraph, "for a func, a pos int, and a float",
[IsFunction, IsPosInt, IsFloat], RandomDigraphCons);

InstallMethod(RandomMultiDigraph, "for a pos int", [IsPosInt],
n -> RandomMultiDigraph(n, Random([1 .. (n * (n - 1)) / 2])));

InstallMethod(RandomMultiDigraph, "for two pos ints", [IsPosInt, IsPosInt],
{n, m} -> DigraphNC(RANDOM_MULTI_DIGRAPH(n, m)));

InstallMethod(RandomTournamentCons, "for IsMutableDigraph and an integer",
[IsMutableDigraph, IsInt],
function(_, n)
  local choice, nodes, list, v, w;
  if n < 0 then
    ErrorNoReturn("the argument <n> must be a non-negative integer,");
  elif n = 0 then
    return EmptyDigraph(IsMutableDigraph, 0);
  fi;
  choice := [true, false];
  nodes  := [1 .. n];
  list   := List(nodes, x -> []);
  for v in nodes do
    for w in [(v + 1) .. n] do
      if Random(choice) then
        Add(list[v], w);
      else
        Add(list[w], v);
      fi;
    od;
  od;
  return DigraphNC(IsMutableDigraph, list);
end);

InstallMethod(RandomTournamentCons, "for IsImmutableDigraph and an integer",
[IsImmutableDigraph, IsInt],
function(_, n)
  local D;
  D := MakeImmutable(RandomTournamentCons(IsMutableDigraph, n));
  SetIsTournament(D, true);
  SetIsMultiDigraph(D, false);
  SetIsSymmetricDigraph(D, n <= 1);
  SetIsEmptyDigraph(D, n <= 1);
  SetDigraphHasLoops(D, false);
  SetDigraphNrEdges(D, Binomial(n, 2));
  return D;
end);

InstallMethod(RandomTournament, "for an integer", [IsInt],
n -> RandomTournamentCons(IsImmutableDigraph, n));

InstallMethod(RandomTournament, "for a func and an integer",
[IsFunction, IsInt], {func, n} -> RandomTournamentCons(func, n));

InstallMethod(RandomLatticeCons, "for IsMutableDigraph and a pos int",
[IsMutableDigraph, IsPosInt],
function(_, n)
  local fam, rand_blist;

  fam := [BlistList([1 .. n], [])];

  while Length(fam) < n do
    rand_blist := List([1 .. n], x -> Random([true, false]));
    UniteSet(fam, List(fam, x -> UnionBlist(x, rand_blist)));
  od;

  return Digraph(IsMutableDigraph, fam, IsSubsetBlist);
end);

InstallMethod(RandomLatticeCons, "for IsImmutableDigraph and a pos int",
[IsImmutableDigraph, IsPosInt],
function(_, n)
  local D;
  D := MakeImmutable(RandomLatticeCons(IsMutableDigraph, n));
  SetIsLatticeDigraph(D, true);
  return D;
end);

InstallMethod(RandomLattice, "for a pos int", [IsPosInt],
n -> RandomLatticeCons(IsImmutableDigraph, n));

InstallMethod(RandomLattice, "for a func and a pos int", [IsFunction, IsPosInt],
RandomLatticeCons);

Quelle digraph.gi Sprache: unbekannt

[ Dauer der Verarbeitung: 0.48 Sekunden (vorverarbeitet) ]