Skip to content

Mutable digraphs

James Mitchell edited this page Sep 25, 2019 · 1 revision

This note is a version of the project description used when preparing v1.0.0, when we introduced mutable digraphs.

Principles:

  1. If the argument to a function is a mutable digraph and its output is a digraph, then the output should be mutable too.
  2. If the argument of a function is an immutable digraph, then the output should be immutable. Exception: XMutableCopy.
  3. Mutable digraphs can be converted into immutable ones in-place, but the other way around is not possible, make a copy instead DigraphMutableCopy.
  4. If the argument of a function is a mutable digraph, and the function modifies its argument, then the argument should be changed in-place.
  5. IsDigraphByOutNeighboursRep means that the digraph has its out-neighbours. The only thing a mutable digraph knows is its out-neighbours (if it belongs in IsDigraphByOutNeighboursRep), everything else must be computed from the out-neighbours (the number of vertices, and edges, for example), and changes to the digraph in-place must be changes to the OutNeighbours.
  6. A typical method:
InstallMethod(DoSomething, "for a digraph", [IsDigraph]
function(D)
   return Digraph(Something(OutNeighbours(D)));
end);

should become two methods:

InstallMethod(DoSomething, "for a dense mutable digraph", [IsDigraphByOutNeighboursRep and IsMutableDigraph]
function(D)
   Something(OutNeighbours(D));
  return D;
end);

InstallMethod(DoSomething, "for an immutable digraph", [IsImmutableDigraph]
function(D)
  return MakeImmutable(DoSomething(DigraphMutableCopy(D)));
end);
  1. Only use IsDigraphByOutNeighboursRep in the filter list for a method if OutNeighbours appears in the body of the method (see the previous point).
  2. Functions like DigraphSymmetricClosure which were previously attributes returning a digraph cannot be attributes now (since then a mutable digraph returned would be made immutable) and also should not be only operations (since then they are recalculated). The pattern used to get around this is:
DeclareAttributeReturnsDigraph("GiveSomething", IsSubcategoryOfDigraph);
----
InstallAttributeReturnsDigraph(GiveSomething, "for a digraph",
[IsSubcategoryOfDigraph]
function(D)
  # do something
  return D;
end);
Clone this wiki locally