[Solved]: What is the most efficient algorithm and data structure for maintaining connected component information on a dynamic graph?

ignougroup
Problem Detail: 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)

Asked By : immibis

Answered By : A.Schulz

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 / loglog 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.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33595

Leave a Reply