Directed union-find

Question

Consider a directed graph $G$ on which one can dynamically add edges and make some specific queries.

Example: disjoint-set forest

Consider the following set of queries:

arrow(u, v)
equiv(u, v)
find(u)

the first one adds an arrow $u→v$ to the graph, the second one decides if $u↔^*v$, the last one finds a canonical representative of the equivalence class of $↔^*$, i.e. a $r(u)$ such that $u↔^*v$ implies $r(v)=r(u)$.

There is a well-known algorithm using the disjoint-set forest data structure implementing these queries in quasi-constant amortized complexity, namely $O(α(n))$. Note that in this case equiv is implemented using find.

More complex variant

Now I'm interested in a more complex problem where the directions do matter:

arrow(u, v)
confl(u, v)
find(u)

the first adds an arrow $u→v$, the seconds decides if there is a node $w$ reachable from both $u$ and $v$, i.e. $u→^*←^*v$. The last one should return an object $r(u)$ such that $u→^*←^*v$ implies $r(u) \bullet r(v)$ where $\bullet$ should be easily computable. (In order to, say, computes confl). The goal is to find a good data structure such that these operations are fast.

Cycles

The graph can contain cycles.

I don't know if there is a way to efficiently and incrementally compute the strongly connected components, in order to only consider DAGs for the main problem.

Of course I would appreciate a solution for DAGs, too. It would correspond to an incremental computation of the least common ancestor.

Naive approach

The disjoint-set forest data structure is not helpful here, since it disregards the direction of the edges. Note that $r(u)$ cannot be a single node, in the case the graph is not confluent.

One can define $r(u)=\{v ∣ u→^*v\}$ and to define $\bullet$ as $S_1\bullet S_2$ when $S_1 ∩ S_2≠∅$. But how to compute this incrementally?

Probably that computing such a big set is not useful, a smaller set should be more interesting, as in the usual union-find algorithm.

Answer 1

(Edit: completely rewrote my answer now that my understanding of the problem is (I hope) clearer.)

It sounds like this problem can be reduced to incrementally constructing and improving an approximation of the transitive closure of the graph, as the graph is built and searched.

$r(u)$ is, abstractly, the set of all nodes which are reachable from both $u$ and $v$ for every $v \ne u$ in the graph. (Of course, not all $u, v$ pairs will necessarily have a node that can be reached from both of them.) Unlike the case in union-find, this set can't be represented as a canonical representative node in the graph, because there may be nodes that are reachable from both $u$ and $v$, and from both $u$ and $w$, that are nonetheless not reachable from both $v$ and $w$.

Say you maintain, for every $u$, a set of nodes reachable from $u$ (I'll call this $R(u)$). These sets would of necessity be an extra data structure for each node, or at least, a set of extra "shortcut" edges in the graph. If you don't care about retaining the specified structure of the graph, there would be no need to distinguish between these edges and the specified edges.

I don't have any ideas offhand for a data structure that captures this that is more efficient than the general case (e.g. a bit vector or hash table,) but you can update these sets incrementally:

Each time you add an edge from $u$ to some other node $v$, you set $R(u) = R(u) \cup R(v)$.

Implement confl by first trying $R(u) \cap R(v)$; if that's non-empty, return true. But if it is empty, do two parallel breadth-first searches from $R(u)$ and $R(v)$ until you either exhaust both reachable sets or find a node in common. While you do this, also update $R(u)$ and $R(v)$ (and the $R$'s of all the intermediate nodes you find) to include the reachable nodes that you found. and if you do find a node in common, set R(u) = R(v) = R(u) \cup R(v).

find(u) just returns $R(u)$. The problem is that confl is not implemented purely in terms of find. I don't see how it could possibly be unless the algorithm was non-incremental (i.e. pre-compute all the $R$ sets of all nodes with the transitive closure of the graph.) However, the incremental approach should still give you fairly good amortized cost, although I have no idea if it approaches $O(\alpha(n))$ offhand. (It probably doesn't. A false answer from confl requires that you start up two BFS'es even when your $R$ sets are saturated; this also seems unavoidable unless the algorithm is made non-incremental.)

This sounds a lot like it might be a special case of La Poutré and van Leeuwen's methods for maintaining transitive closure of a graph.

I realize this doesn't fully answer the question, but perhaps it serves to clarify it, and someone who has more experience with graph algorithms can give a better data structure for encoding the $R$ sets.