9
$\begingroup$

Say I have an undirected finite sparse graph, and need to be able to run the following queries efficiently:

  • $IsConnected(N_1, N_2)$ - returns $T$ if there is a path between $N_1$ and $N_2$, otherwise $F$
  • $ConnectedNodes(N)$ - returns the set of nodes which are reachable from $N$

This is easily done by pre-computing the connected components of the graph. Both queries can run in $O(1)$ time.

If I also need to be able to add edges arbitrarily - $AddEdge(N_1, N_2)$ - then I can store the components in a disjoint-set data structure. Whenever an edge is added, if it connects two nodes in different components, I would merge those components. This adds $O(1)$ cost to $AddEdge$ and $O(InverseAckermann(|Nodes|))$ cost to $IsConnected$ and $ConnectedNodes$ (which might as well be $O(1)$).

If I also need to be able to remove edges arbitrarily, what is the best data structure to handle this situation? Is one known? To summarize, it should support the following operations efficiently:

  • $IsConnected(N_1, N_2)$ - returns $T$ if there is a path between $N_1$ and $N_2$, otherwise $F$.
  • $ConnectedNodes(N)$ - returns the set of nodes which are reachable from $N$.
  • $AddEdge(N_1, N_2)$ - adds an edge between two nodes. Note that $N_1$, $N_2$ or both might not have existed before.
  • $RemoveEdge(N_1, N_2)$ - removes an existing edge between two nodes.

(I am interested in this from the perspective of game development - this problem seems to occur in quite a few situations. Maybe the player can build power lines and we need to know whether a generator is connected to a building. Maybe the player can lock and unlock doors, and we need to know whether an enemy can reach the player. But it's a very general problem, so I've phrased it as such)

$\endgroup$
  • $\begingroup$ $ConnectedNodes$ couldn't possibly run in $O(1)$, because if it returns a list of $n$ nodes, it would need $\Omega(n)$ time. Implementing $ConnectedNodes$ with a BFS is optimal, so a potential data structure would only need to support IsConnected, AddEdge and RemoveEdge. This seems relevant to your question: stackoverflow.com/questions/7241151/… $\endgroup$ – Tom van der Zanden Nov 28 '14 at 11:02
  • $\begingroup$ @TomvanderZanden Returning a set that is already built (in programming, a pointer or reference) is $O(1)$... although there's not much the user of $ConnectedNodes$ could do that $O(1)$ and not covered by $IsConnected$. $\endgroup$ – immibis Nov 28 '14 at 11:18
11
$\begingroup$

This problem is known as dynamic connectivity and it is an active area of research in the theoretical computer science community. Still some important problems are still open here.

To get the terminology clear, you ask for fully-dynamic connectivity since you want to add and delete edges. There is a result of Holm, de Lichtenberg and Thorup (J.ACM 2001) that achieves $O(\log^2 n)$ update time and $O(\log n / \log\log n)$ query time. From my understanding it seems to be implementable. Simply speaking the data structure maintains a hierarchy of spanning trees - and dynamic connectivity in trees is easier to cover. I can recommend Erik D. Demaine's notes for a good explanation see here for a video. Erik's note also contain pointers to other relevant results. As a note: all these results are theoretical results.

These data structures might not provide ConnectedNodes queries per se, but its easy to achieve this. Just maintain as an additional data structure the graph (say as doubly connected edge list) and the do the depth-first-search to get the nodes that can be reached from a certain node.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.