In computing and graph theory, a dynamic connectivity structure is a data structure that dynamically maintains information about the connected components of a graph.
The set V of vertices of the graph is fixed, but the set E of edges can change. The three cases, in order of difficulty, are:
After each addition/deletion of an edge, the dynamic connectivity structure should adapt itself such that it can give quick answers to queries of the form "is there a path between x and y?" (equivalently: "do vertices x and y belong to the same connected component?").
If edges can only be added, then the dynamic connectivity problem can be solved by a disjoint-set data structure. Each set represents a connected component; there is a path between x and y if and only if they belong to the same set. The amortized time per operation is
\Theta(\alpha(n))
The case in which edges can only be deleted was solved by Shimon Even and Yossi Shiloach.[3]
The structure uses a table that specifies, for each vertex, the name of the component to which it belongs. Thus a connectivity query takes constant time. The challenge is to update the table when an edge is deleted.
When edge u-v is deleted in a forest, the tree containing that edge is broken to two trees: one of them contains u and the other contains v. The table is updated in the following way.
Since we always rename the smaller sub-component, the amortized time for a delete operation is
O(log(n))
When an edge is deleted in a general graph, we don't know whether its component remains a single component (connected by other edges) or broken to two components. So we use two processes which run in parallel (or in an interleaved way). Process A checks whether the edge deletion breaks a component, and if it does, both processes halt. Process B checks whether the edge deletion does not break the component to which it belongs, and if it does not, again both processes halt.
O(log(n))
The structure has the following properties. A vertex v in level i, i>0, has only three types of edges: backward edges which connect it to level i-1 (there is at least one such edge, which may be artificial), local edges which connect it to other edges in level i (there are zero or more such edges), or forward edges which connect it to edges in level i+1 (there are zero or more such edges). So for each vertex v, we maintain three sets of edges (backward, local and forward).
When an edge u-v is deleted, there are two options: either u and v are in the same level, or they are in levels whose number differs by 1.
While Q is not empty:
If the edge deletion does not break any component and we are in case 2.2, then eventually the procedure will halt. In this case it is easy to see that the BFS structure is maintained correctly. If its deletion does break a component, then the procedure will not halt by itself. However, process A, recognizing the break, will halt, and both processes will halt. In this case all the changes made in the BFS structure are ignored, and we go back to the BFS structure we had just before the deletion, except that the deleted edge is now replaced by an artificial edge. Clearly, in this case v is now the root of a tree which includes the new component, and perhaps additional components, through some other artificial edges. Also, there are no edges connecting the descendants of with any vertices which are not 's descendants, except the artificial edge .[4]
whenever an edge is processed in the procedure, one of its endpoints drops by one level. Since the lowest level a vertex can reach in runs which are terminated by process B is
|V|-1
2|V|
O(n)
A forest can be represented using a collection of either Link-cut trees or Euler tour trees. Then the dynamic connectivity problem can be solved easily, as for every two nodes x,y, x is connected to y if and only if FindRoot(x)=FindRoot(y). The amortized update time and query time are both O(log(n)).
A general graph can be represented by its spanning forest - a forest which contains a tree for every connected component of the graph. We call this spanning forest F. F itself can be represented by a forest of Euler tour trees.
The Query and Insert operations are implemented using the corresponding operations on the ET trees representing F. The challenging operation is Delete, and in particular, deleting an edge which is contained in one of the spanning trees of F. This breaks the spanning tree into two trees, but, it is possible that there is another edge which connects them. The challenge is to quickly find such a replacement edge, if it exists. This requires a more complex data structure. Several such structures are described below.
Each edge in the graph is assigned a level. Let L=lg n. The level of each edge inserted to the graph is initialized to L, and may decrease towards 0 during delete operations.
For each i between 0 and L, define Gi as the subgraph consisting of edges that are at level i or less, and Fi a spanning forest of Gi. Our forest F from before is now called FL. We will keep a decreasing sequence of forests FL ⊇ ... ⊇ F0. [5] [6]
The Query and Insert operations use only the largest forest FL. The smaller subgraphs are consulted only during a Delete operation, and in particular, deleting an edge which is contained in one of the spanning trees of FL.
When such an edge e = x-y is deleted, it is first removed from FL and from all smaller spanning forests to which it belongs, i.e. from every Fi with i ≥ level(e). Then we look for a replacement edge.
Start with the smallest spanning forest which contained e, namely, Fi with i = level(e). The edge e belongs to a certain tree T⊆Fi. After the deletion of e, the tree T is broken to two smaller trees: Tx which contains the node x and Ty which contains the node y. An edge of Gi is a replacement edge, if and only if it connects a node in Tx with a node in Ty. Suppose wlog that Tx is the smaller tree (i.e. contains at most half the nodes of T; we can tell the size of each subtree by an annotation added to the Euler trees).
We first decrease the level of each edge of Tx by 1. Then we loop over all the edges ε with level i and at least one node in Tx:
The level of each edge will be decreased at most lg n times. Why? Because with each decrease, it falls into a tree whose size is at most half the size of its tree in the previous level. So in each level i, the number of nodes in each connected component is at most 2i. Hence the level of an edge is always at least 0.
Each edge whose level is decreased, takes
O(lgn)
O(lg2n)
O(lg2n)
O(lg2n)
O(lgn)
O(lgn)
In total, the amortized time per update is
O(lg2n)
O(lgn/lglgn)
However, the worst-case time per update might be
O(n)
Given a graph G(V,E) and a subset T⊆V, define cutset(T) as the set of edges that connect T with V\T. The cutset structure is a data structure that, without keeping the entire graph in memory, can quickly find an edge in the cutset, if such an edge exists. [7]
Start by giving a number to each vertex. Suppose there are n vertices; then each vertex can be represented by a number with lg(n) bits. Next, give a number to each edge, which is a concatenation of the numbers of its vertices - a number with 2 lg(n) bits.
For each vertex v, calculate and keep xor(v), which is the xor of the numbers of all edges adjacent to it.
Now for each subset T⊆V, it is possible to calculate xor(T) = the xor of the values of all vertices in T. Consider an edge e = u-v which is an internal edge of T (i.e. both u and v are in T). The number of e is included twice in xor(T) - once for u and once for v. Since the xor of every number with itself is 0, e vanishes and does not affect xor(T). Thus, xor(T) is actually the xor of all edges in cutset(T). There are several options:
Our goal now is to handle this third option.
First, create a sequence of lg(n) levels of the cutset structures, each of which contains about half the edges from the upper level (i.e., for each level, pick each edge from the upper level with probability 1/2). If in the first level xor(T) returns an illegal value, meaning that cutset(T) has two or more edges, then there is a chance that in the next level, which contains fewer edges, xor(T) will return a legal value since cutset(T) will contain a single edge. If xor(T) still returns an illegal value, continue to the next level, etc. Since the number of edges is decreasing, there are two cases:
It is possible to prove that the probability of success is at least 1/9.
Next, create a collection of C lg(n) independent versions of the level structure, where C is a constant. In each versions, do an independent random reduction of edges from level to level. Try each query on each of the versions until one of them succeeds. The probability that all versions fail is at most:
(1-1/9)C
We can add a cutset structure to a dynamic connectivity structure.
The Insert and Delete operations on the cutset structure are done in exactly the same way: the edge inserted/deleted is XORed into both its endpoints.
When an edge is deleted from the spanning forest used for the dynamic connectivity structure, the cutset structure is used to find a replacement edge.
A single cutset structure requires only O(n lg n) memory - only a single number, with 2 lg n bits, for each of the n vertices. We don't have to keep the edges themselves. For dense graphs, this is much cheaper than keeping the entire graph in memory.
We have to keep lg(n) versions, each of which contains lg(n) levels. Hence, the total memory requirement is .
The query time is O(polylog(n)) in the worst case. This is in contrast to The Level structure, in which the query time is O(polylog(n)) amortized, but the worst-case time is O(n).
If the order in which edges will be deleted is known ahead of time, then we can solve the dynamic connectivity problem in time
O(logn)
Adding an edge is slightly more complicated. If we add an edge edge e from u to v, then if u and v are not connected, then this edge will be part of the maximum spanning forest. If they are connected, we want to add u->v to our forest if it can improve our maximum spanning forest. To do this, we need to quickly check what edge has the smallest removal time on the path from u to v. If this edge's removal time comes after e's removal time, then e cannot improve our maximum spanning forest. Otherwise, the other edge should be deleted and replaced with e.
This requires us to do the following operations: add an edge, cut an edge, and query the minimum edge on a path which can be done rather easily with a link-cut tree in log(n) per operation.