== Notes on computing the transitive reduction of a graph ==

1) First attempt; actually compute it, as follows:

   1) Vertices not pointed at are rank 0.
   2) Set current rank c=0.
   3a) Vertices pointed at by rank c vertices are rank c+1.
   3b) Remove rank c vertices from consideration.
   3c) Increase current rank by one.
   3d) Repeat until no vertices are left.
   4) Remove edges where difference in rank >1.

   This does not work, because it may be that all successors of a node v of
   rank a get assigned a rank of (at least) a+2 because they're ALSO the
   children of rank a+1 nodes elsewhere, and in that case we'd wrongly
   delete all the edges between v and its successors.

2) Second attempt; don't insert superfluous edges, as follows:

   * Don't insert edge (u, v) if path already exists. (That is if v \in
     distant(u).  We know v \notin succ(u), because (u, v) has not been
     added yet.)

   * How to determine reachability?

     - Keep a cache of succ/distant nodes for each node.
     - When (u, v) is added:

       distant(u) = distant(u) \cup succ(v) \cup distant(v) \ {v}
       succ(u) = succ(u) \cup {v}

     - Use a module implementing sets for this. Or just use hashes.

   -> Doesn't work, because you might add (u, v) *before* the path that
      would make it obsolete.

   -> Or do it twice. Compute reachability once; then readd edges.

   -> But you'd have to avoid caching (u, v) itself.

   -> So: compute succ/distant for each node, as above, then add edges only
      if v\notin distant(u).

   -> But this still doesn't work, for the rather asinine reason that we're
      considering all transitive edges (u, v), and therefore everything ends
      up in succ(u), with distant(u) being empty (assuming no bugs).

3) Third attempt (not coded): BFS-ish compution of path lengths.

   0) Compute (full) graph.
   1) For each vertex v...
      1a) BFS-traverse graph from v. Add distance from v (i.e. current
          depth) to a list attached to each visited vertex u.
      1b) Now each (reachable) vertex has an associated list of distances.
          Use that to remove edges:
          1b1) If 1 \notin list, skip. (No edge to delete.)
          1b2) If list == {1}, skip. (Edge kept.)
          1b3) Otherwise, delete edge.
      1c) Repeat (for the next v). Obviously lists are cleared for each new
          v.  It's OK to remove edges from the "live" graph; if anything
          this might make subsequent BFS traversals faster.

   -> Is there a module for BFS? Yes, Graph::Traversal::BFS. But it doesn't
      allow you to specify where to start, and doesn't give access to the
      current depth.

   -> Normal BFS where nodes are only visited once would not work anyway,
      since we'd just visit all nodes in the graph immediately and never
      reach any traversal depth >1.

   -> But the graph is cycle-free, so if we just kept on searching we'd
      still finish (though time complexity would be higher).

4) Fourth attempt:

   * Actually, wouldn't it be enough to find all length 2 paths (u, v, w),
     and then remove the direct edge (u, w)?

   * In the general case this wouldn't work because the might be graphs like
     this:

       u ---> v ---> w ---> x
       |                    ^
       +--------------------+

     But in the specific case of rule graphs, the edges (u, w) and (v, x)
     would exist as well.

   * We'd have to remove edges from a a (deep) copy of the graph, since
     otherwise by removing an edge we might *create* the kind of situation
     described above.

...


ω) Last attempt: external tools.

   * Don't compute transitive reduction at all, simply write out the full
     graph in a suitable format (Graphviz/DOT or other) and use an external
     tool to compute it instead.

   * Graphviz has a "-x" option that is described as "reduce graph".
     Unfortunately it appears to do precisely nothing.

== Notes on totalistic difference/distance ==

Edge A->B

1. Compute tot_red(A)=:A', tot_comp(B)=:B'.
2. Consider conds(A')=:c_A, conds(B')=:c_B.
3. Compute c_A \ c_B =: \Delta_{A,B}.
4. Totalistic distance (edge weight): |\Delta_{A,B}|=:w_{A,B}
5. # of rules: 2^{w_{A,B}}...
   ... -1 if A'=A
   ... -1 if B'=B

A := B368iS23->B3-aS23 =: B
A' = B36S23
B' = B3S23
\Delta_{A,B} = B6
w_{A,B} = 1
# rules = 2^1 = 2 (B36S23 and B3S23)

Totalistic reduction: strike all partial conditions:

   B34-a/S236i => B3/S23
     ---    --
      ^      ^
      |      +- removed
      +- removed

Totalistic completion: fill in all partial conditions:

   B34-a/S236i => B34/S236
     ---    --
      ^      ^
      |      +- filled in
      +- filled in