September 24, 2010 at 10:33The system of disjoint sets and its application
Good afternoon, Habrahabr. This is another post in the framework of my program to enrich the database of the largest IT resource with information on algorithms and data structures. As practice shows, this information is not enough for many, and the need is found in a wide variety of areas of programming life.
I continue to predominantly choose those algorithms / structures that are easy to understand and that do not require a lot of code - but the practical value is difficult to underestimate. Last time it was a Cartesian tree . This time, a system of disjoint sets . It is also known as disjoint set union (DSU) or Union-Find .
We set ourselves the following task. Let us operate on elements of N types (for simplicity, hereinafter - numbers from 0 to N-1). Some groups of numbers are combined into sets. We can also add a new element to the structure, it thereby forms a set of size 1 from itself. And finally, periodically we need to merge some two sets into one.
We formalize the task: create a fast structure that supports the following operations:
MakeSet (X) - introduce a new element X into the structure, create for it a set of size 1 from itself.
Find (X) - return identifierof the set to which the element X belongs. As an identifier, we will choose one element from this set - the representative of the set. It is guaranteed that for the same set the representative will return the same one, otherwise it will not be possible to work with the structure: even checking whether two elements belong to the same set will not be correct
Unite (X, Y) - combine the two sets in which the elements X and Y lie in one new one.
In the figure I will demonstrate the operation of such a hypothetical structure.
The classic DSU implementation was proposed by Bernard Galler and Michael Fischer in 1964, however, it was investigated (including a temporary assessment of complexity) by Robert Tarjan already in 1975. Tarjan also has some results, improvements and applications that we will talk about today.
We will store the data structure in the form of a forest, that is, we will turn the DSU into a system of disjoint trees. All elements of one set lie in one corresponding tree, the representative of the tree is its root, the merging of sets is simply the union of two trees into one. As we will see, such an idea, coupled with two small heuristics, leads to a surprisingly high speed of the resulting structure.
First we need the p array, storing for each vertex of the tree its immediate ancestor (and for the root of the tree X - itself). Using this array alone, you can effectively implement the first two DSU operations:
To create a new tree from an element X, it is enough to indicate that it is the root of its own tree, and has no ancestor.
Representative of a tree is its root. Then, to find this representative, it is enough to go up the parent links until we stumble upon the root.
But this is not all: such a naive implementation in the case of a degenerate (extended in line) tree can work for O (N), which is unacceptable. One could try to speed up the search. For example, to store not only the immediate ancestor, but large tables of logarithmic rise up, but this requires a lot of memory. Or, instead of linking to the ancestor, storing a link to the root itself - however, then when merging trees (Unite), all the elements of one of the trees will have to change these links, and this again is time-consuming O (N) order.
We will go the other way: instead of speeding up the implementation, we will simply try to prevent excessively long branches in the tree. This is the first heuristics DSU, it is called path compression (path compression). The essence of the heuristic: after a representative is found, for each vertex along the path from X to the root we will change the ancestor to this very representative. That is, in fact, we re-suspend all these vertices instead of a long branch directly to the root. Thus, the implementation of the Find operation becomes a two-pass.
The figure shows the tree before and after the Find (3) operation. Red ribs are the ones along which we walked along the path to the root. Now they are redirected. Notice how after that the height of the tree drastically decreased.
Writing source code in recursive form is quite simple:
With the merger of the two trees have a little tinker. First, we find the roots of both merging trees using the already written Find function. Now, remembering that our implementation stores only references to immediate parents, to merge the trees it would be enough just to suspend one of the roots (and with it the whole tree) by the son to the other. Thus, all the elements of this tree will automatically belong to another - and the search procedure for the representative will return the root of the new tree.
The question arises: which tree to which to hang? It’s not good to always choose one, say, a tree X: it’s easy to find an example where, after N unions, we get a degenerate tree — one branch of N elements. And here comes the second DSU heuristic, aimed at reducing the height of trees.
In addition to our ancestors, we will store another Rank array . In it, for each tree, the upper limit of its height will be stored - that is, the longest branch in it. Note that it is not the height itself - during the execution of Find, the longest branch can self-destruct, and spending even more iterations to find a new longest branch is too expensive. Therefore, for each root in the Rank array, a number will be written that is guaranteed to be greater than or equal to the height of its tree.
Now it’s easy to make a merge decision: to prevent branches that are too long in the DSU, we will hang a lower tree from a higher one. If their heights are equal - it does not matter who to hang from whom. But in the latter case, the newly made root must not forget to increase the Rank.
This is how a typical Unite is produced (for example, with parameters 8 and 19):
However, in practice, it turns out that you can not spend additional O (N) memory on frauds with ranks. It is enough to choose a root for resuspension in a random way - surprisingly, this solution gives in practice a speed that is quite comparable to the original ranking implementation. The author of this article has been using a randomized DSU all his life, and there has never been a case where he would have failed.
C # implementation:
Due to the use of two heuristics, the speed of each operation depends strongly on the structure of the tree, and the structure of the tree on the list of operations performed before. The only exception is MakeSet - its operating time is obviously O (1) :-) For the other two, the speed is very unobvious.
Robert Taryan proved a remarkable fact in 1975: the operating time of both Find and Unite on a forest of size N is O (α (N)).
Under α (N) in mathematics is the inverse Ackerman function, that is, the function inverse forf (N) = A (N, N) . Ackerman's function A (N, M) is known for having a colossal growth rate. For example, A (4, 4) = 2 2 2 65536 -3 , this number is truly huge. In general, for all conceivable practical values of N, the inverse Ackerman function of it does not exceed 5. Therefore, we can take it as a constant and assume O (α (N)) ≅ O (1) .
So, we have:
MakeSet (X) - O (1).
Find (X) - O (1) is amortized.
Unite (X, Y) - O (1) amortized.
Memory Consumption - O (N).
Not bad at all :-)
A wide variety of different uses are known for DSUs. Most of them are related to solving some problem offline - that is, when the list of queries regarding the structure that the program receives is known in advance. I will give here a few of these tasks along with brief ideas for solutions.
An undirected connected graph with weighted edges is given. Throw out some edges from it so that as a result we get a tree, and the total weight of the edges of this tree should be the smallest.
One of the well-known places where this task arises (although it is solved differently) is to block redundant connections in an Ethernet network to avoid possible packet cycles. The protocols created for this purpose are widely known, with half of the major modifications made to them by Cisco. See the Spanning Tree Protocol for more details .
The figure shows a weighted graph with a highlighted minimum skeleton.
Kruskal's algorithm for solving this problem: we sort all the edges in ascending order of weight and we will support the current forest of minimum weight with the help of DSU. Initially, a DSU consists of N trees, one vertex in each. We go along the ribs in ascending order; if the current edge combines different components, merge them into one and remember the edge as an element of the core. As soon as the number of components reaches unity - we built the desired tree.
Given a tree and a set of queries of the form: for given vertices u and v, return their nearest common ancestor (least common ancestor, LCA). The entire set of queries is known in advance, i.e. the task is formulated offline.
Let's start by searching in depth in a tree. Consider some query. Let the search in depth come to such a state that one of the request vertices (say u) has already been visited by the search earlier, and now the current vertex in the search is v, the entire subtree v has just been examined. Obviously, the response to the request will be either the vertex v itself, or some of its ancestors. Moreover, each of the ancestors v along the path to the root generates a certain class of vertices u for which it is the answer: this class is exactly equal to the already viewed tree branch “to the left” of such an ancestor.
In the figure, you can see a tree with the division of vertices into classes, while the white vertices are not yet viewed.
The classes of such vertices do not intersect, which means that they can be supported in the DSU. As soon as the depth search returns from the subtree, merge the class of this subtree with the class of the current vertex. And to search for an answer, support the Ancestor array - for each vertex, the ancestor proper, who generated the class of this vertex. The cell value of this array for the representative must not be forgotten to rewrite when merging trees. But now, in the process of searching in depth for each fully processed vertex v, we can find everything in the list of queriesWhere u - has already been processed, and deduce the answer:
A multigraph is given (a graph in which a pair of vertices can be connected by more than one direct edge), to which requests of the form “remove some edge” and “how many connected components are in the graph now?” The entire list of requests is known in advance.
The solution is trite. First, we will execute all removal requests, calculate the number of components in the final graph, and remember it. We will push the resulting graph into the DSU. Now we will go to the removal requests in the reverse order: each removal of an edge from the old graph means a possible merging of the two components in our “flashback graph” stored in the DSU; in this case, the current number of connected components decreases by one.
Let's consider some image - a rectangular array of pixels. It can be represented as a grid graph: each vertex-pixel is directly connected by edges with its four nearest neighbors. The task is to highlight the same semantic zones in the image, for example, of a similar color, and be able to quickly determine for two pixels whether they are in the same zone. So, for example, old black-and-white films are painted: first you need to select areas with approximately the same shades of gray.
There are two approaches to solving this problem, both end up using DSUs. In the first version, we draw an edge not between each pair of neighboring pixels, but only between those that are close enough in color. After that, the usual rectangular traversal of the graph will fill in the DSU, and we will get a set of connected components - they are the same color regions of the image.
The second option is more flexible. We will not completely remove the ribs, but assign to each of them a weight calculated on the basis of the color difference and some other additional factors - specific for each particular segmentation task. In the graph obtained, it is enough to find some forest of minimal weight, for example, using the same Kruskal algorithm. In practice, not any current connecting edge is recorded in the DSU, but only those for which at the moment the two components are not very different by the standards of another special weight function.
Task: generate a maze with one input and one output.
Solution Algorithm:
Let's start with the state when all the walls are installed, with the exception of the entrance and exit.
At each step of the algorithm, we choose a random wall. If the cells between which it stands are not connected in any way (they are in different components of the DSU), then we destroy it (merge the components).
We continue the process to a certain state of convergence: for example, when the input and output are connected; or when one component remains.
There are implementation options for Find (X) that require one pass to the root, not two, but retain the same or almost the same degree of performance. They implement other strategies for reducing tree height, as opposed to path compression.
Option # 1: path splitting . On the way from top X to the root, redirect the parent connection of each vertex from its ancestor to the ancestor of the ancestor (grandfather).
Option number 2: path halving . Take the idea of path splitting, but redirect connections not of all the vertices along the path, but only those on which we redirect - that is, "grandfathers".
The same tree is taken in the figure; the Find (3) query is executed in it. In the center, the result is shown using path splitting, on the right - path halving.
The system of disjoint sets has one big drawback: it does not support the Undo operation in any form, because it is implemented through in an imperative style. It would be much more convenient to implement a functional-style DSU, when each operation does not change the structure in place, but returns a slightly modified new structure in which the required changes are made (while most of the memory of the old and new structures is common). Such data structures are called persistent in English terminology ; they are widely used in pure functional programming, where the idea of data immutability dominates.
Due to the purely imperative idea of DSU algorithms, its functional implementation, while maintaining performance, for a long time seemed unthinkable. However, in 2007, Sylvain Conchon and Jean-Christophe Filliâtre presented in their work the desired functional version, in which the Unite operation returns a changed structure. To be honest, it is not entirely functional, it uses imperative assignments, however, they are securely hidden inside the implementation, and the persistent DSU interface is purely functional.
The main idea of the implementation is the use of data structures that implement “persistent arrays”: they support the same operations as arrays, but they still do not modify the memory, but return the changed structure. Such an array can be easily implemented using some tree, however, in this case, operations with it will take O (log 2 N) time, and for DSU this estimate is already excessively large.
For further technical details, send readers to the original article .
The systems of disjoint sets in the scope of this article are discussed in the famous book - Cormen, Leiserson, Rivest, Stein "Algorithms: construction and analysis." There you can find evidence that the operation takes about α (N) time.
On the site of Maxim Ivanov, you can find the full implementation of DSU in C ++.
The Wait-free Parallel Algorithms for the Union-Find Problem article discusses the parallel version of the DSU implementation. It does not have thread locks.
Thank you all for your attention :-)
I continue to predominantly choose those algorithms / structures that are easy to understand and that do not require a lot of code - but the practical value is difficult to underestimate. Last time it was a Cartesian tree . This time, a system of disjoint sets . It is also known as disjoint set union (DSU) or Union-Find .
Condition
We set ourselves the following task. Let us operate on elements of N types (for simplicity, hereinafter - numbers from 0 to N-1). Some groups of numbers are combined into sets. We can also add a new element to the structure, it thereby forms a set of size 1 from itself. And finally, periodically we need to merge some two sets into one.
We formalize the task: create a fast structure that supports the following operations:
MakeSet (X) - introduce a new element X into the structure, create for it a set of size 1 from itself.
Find (X) - return identifierof the set to which the element X belongs. As an identifier, we will choose one element from this set - the representative of the set. It is guaranteed that for the same set the representative will return the same one, otherwise it will not be possible to work with the structure: even checking whether two elements belong to the same set will not be correct
if (Find(X) == Find(Y)). Unite (X, Y) - combine the two sets in which the elements X and Y lie in one new one.
In the figure I will demonstrate the operation of such a hypothetical structure.
Implementation
The classic DSU implementation was proposed by Bernard Galler and Michael Fischer in 1964, however, it was investigated (including a temporary assessment of complexity) by Robert Tarjan already in 1975. Tarjan also has some results, improvements and applications that we will talk about today.
We will store the data structure in the form of a forest, that is, we will turn the DSU into a system of disjoint trees. All elements of one set lie in one corresponding tree, the representative of the tree is its root, the merging of sets is simply the union of two trees into one. As we will see, such an idea, coupled with two small heuristics, leads to a surprisingly high speed of the resulting structure.
First we need the p array, storing for each vertex of the tree its immediate ancestor (and for the root of the tree X - itself). Using this array alone, you can effectively implement the first two DSU operations:
MakeSet (X)
To create a new tree from an element X, it is enough to indicate that it is the root of its own tree, and has no ancestor.
public void MakeSet(int x)
{
p[x] = x;
}Find (X)
Representative of a tree is its root. Then, to find this representative, it is enough to go up the parent links until we stumble upon the root.
But this is not all: such a naive implementation in the case of a degenerate (extended in line) tree can work for O (N), which is unacceptable. One could try to speed up the search. For example, to store not only the immediate ancestor, but large tables of logarithmic rise up, but this requires a lot of memory. Or, instead of linking to the ancestor, storing a link to the root itself - however, then when merging trees (Unite), all the elements of one of the trees will have to change these links, and this again is time-consuming O (N) order.
We will go the other way: instead of speeding up the implementation, we will simply try to prevent excessively long branches in the tree. This is the first heuristics DSU, it is called path compression (path compression). The essence of the heuristic: after a representative is found, for each vertex along the path from X to the root we will change the ancestor to this very representative. That is, in fact, we re-suspend all these vertices instead of a long branch directly to the root. Thus, the implementation of the Find operation becomes a two-pass.
The figure shows the tree before and after the Find (3) operation. Red ribs are the ones along which we walked along the path to the root. Now they are redirected. Notice how after that the height of the tree drastically decreased.
Writing source code in recursive form is quite simple:
public int Find(int x)
{
if (p[x] == x) return x;
return p[x] = Find(p[x]);
}Unite (X, Y)
With the merger of the two trees have a little tinker. First, we find the roots of both merging trees using the already written Find function. Now, remembering that our implementation stores only references to immediate parents, to merge the trees it would be enough just to suspend one of the roots (and with it the whole tree) by the son to the other. Thus, all the elements of this tree will automatically belong to another - and the search procedure for the representative will return the root of the new tree.
The question arises: which tree to which to hang? It’s not good to always choose one, say, a tree X: it’s easy to find an example where, after N unions, we get a degenerate tree — one branch of N elements. And here comes the second DSU heuristic, aimed at reducing the height of trees.
In addition to our ancestors, we will store another Rank array . In it, for each tree, the upper limit of its height will be stored - that is, the longest branch in it. Note that it is not the height itself - during the execution of Find, the longest branch can self-destruct, and spending even more iterations to find a new longest branch is too expensive. Therefore, for each root in the Rank array, a number will be written that is guaranteed to be greater than or equal to the height of its tree.
Now it’s easy to make a merge decision: to prevent branches that are too long in the DSU, we will hang a lower tree from a higher one. If their heights are equal - it does not matter who to hang from whom. But in the latter case, the newly made root must not forget to increase the Rank.
This is how a typical Unite is produced (for example, with parameters 8 and 19):
public void Unite(int x, int y)
{
x = Find(x);
y = Find(y);
if (rank[x] < rank[y])
p[x] = y;
else
{
p[y] = x;
if (rank[x] == rank[y])
++rank[x];
}
}However, in practice, it turns out that you can not spend additional O (N) memory on frauds with ranks. It is enough to choose a root for resuspension in a random way - surprisingly, this solution gives in practice a speed that is quite comparable to the original ranking implementation. The author of this article has been using a randomized DSU all his life, and there has never been a case where he would have failed.
C # implementation:
public void Unite(int x, int y)
{
x = Find(x);
y = Find(y);
if (rand.Next() % 2 == 0)
Swap(ref x, ref y);
p[x] = y;
}Performance
Due to the use of two heuristics, the speed of each operation depends strongly on the structure of the tree, and the structure of the tree on the list of operations performed before. The only exception is MakeSet - its operating time is obviously O (1) :-) For the other two, the speed is very unobvious.
Robert Taryan proved a remarkable fact in 1975: the operating time of both Find and Unite on a forest of size N is O (α (N)).
Under α (N) in mathematics is the inverse Ackerman function, that is, the function inverse for
So, we have:
MakeSet (X) - O (1).
Find (X) - O (1) is amortized.
Unite (X, Y) - O (1) amortized.
Memory Consumption - O (N).
Not bad at all :-)
Practical applications
A wide variety of different uses are known for DSUs. Most of them are related to solving some problem offline - that is, when the list of queries regarding the structure that the program receives is known in advance. I will give here a few of these tasks along with brief ideas for solutions.
Skeleton of minimum weight
An undirected connected graph with weighted edges is given. Throw out some edges from it so that as a result we get a tree, and the total weight of the edges of this tree should be the smallest.
One of the well-known places where this task arises (although it is solved differently) is to block redundant connections in an Ethernet network to avoid possible packet cycles. The protocols created for this purpose are widely known, with half of the major modifications made to them by Cisco. See the Spanning Tree Protocol for more details .
The figure shows a weighted graph with a highlighted minimum skeleton.
Kruskal's algorithm for solving this problem: we sort all the edges in ascending order of weight and we will support the current forest of minimum weight with the help of DSU. Initially, a DSU consists of N trees, one vertex in each. We go along the ribs in ascending order; if the current edge combines different components, merge them into one and remember the edge as an element of the core. As soon as the number of components reaches unity - we built the desired tree.
Tarjan's LCA offline search algorithm
Given a tree and a set of queries of the form: for given vertices u and v, return their nearest common ancestor (least common ancestor, LCA). The entire set of queries is known in advance, i.e. the task is formulated offline.
Let's start by searching in depth in a tree. Consider some query
In the figure, you can see a tree with the division of vertices into classes, while the white vertices are not yet viewed.
The classes of such vertices do not intersect, which means that they can be supported in the DSU. As soon as the depth search returns from the subtree, merge the class of this subtree with the class of the current vertex. And to search for an answer, support the Ancestor array - for each vertex, the ancestor proper, who generated the class of this vertex. The cell value of this array for the representative must not be forgotten to rewrite when merging trees. But now, in the process of searching in depth for each fully processed vertex v, we can find everything in the list of queries
Ancestor[Find(u)].Connectivity Components in a Multigraph
A multigraph is given (a graph in which a pair of vertices can be connected by more than one direct edge), to which requests of the form “remove some edge” and “how many connected components are in the graph now?” The entire list of requests is known in advance.
The solution is trite. First, we will execute all removal requests, calculate the number of components in the final graph, and remember it. We will push the resulting graph into the DSU. Now we will go to the removal requests in the reverse order: each removal of an edge from the old graph means a possible merging of the two components in our “flashback graph” stored in the DSU; in this case, the current number of connected components decreases by one.
Image segmentation
Let's consider some image - a rectangular array of pixels. It can be represented as a grid graph: each vertex-pixel is directly connected by edges with its four nearest neighbors. The task is to highlight the same semantic zones in the image, for example, of a similar color, and be able to quickly determine for two pixels whether they are in the same zone. So, for example, old black-and-white films are painted: first you need to select areas with approximately the same shades of gray.
There are two approaches to solving this problem, both end up using DSUs. In the first version, we draw an edge not between each pair of neighboring pixels, but only between those that are close enough in color. After that, the usual rectangular traversal of the graph will fill in the DSU, and we will get a set of connected components - they are the same color regions of the image.
The second option is more flexible. We will not completely remove the ribs, but assign to each of them a weight calculated on the basis of the color difference and some other additional factors - specific for each particular segmentation task. In the graph obtained, it is enough to find some forest of minimal weight, for example, using the same Kruskal algorithm. In practice, not any current connecting edge is recorded in the DSU, but only those for which at the moment the two components are not very different by the standards of another special weight function.
Labyrinth Generation
Task: generate a maze with one input and one output.
Solution Algorithm:
Let's start with the state when all the walls are installed, with the exception of the entrance and exit.
At each step of the algorithm, we choose a random wall. If the cells between which it stands are not connected in any way (they are in different components of the DSU), then we destroy it (merge the components).
We continue the process to a certain state of convergence: for example, when the input and output are connected; or when one component remains.
Single pass algorithms
There are implementation options for Find (X) that require one pass to the root, not two, but retain the same or almost the same degree of performance. They implement other strategies for reducing tree height, as opposed to path compression.
Option # 1: path splitting . On the way from top X to the root, redirect the parent connection of each vertex from its ancestor to the ancestor of the ancestor (grandfather).
Option number 2: path halving . Take the idea of path splitting, but redirect connections not of all the vertices along the path, but only those on which we redirect - that is, "grandfathers".
The same tree is taken in the figure; the Find (3) query is executed in it. In the center, the result is shown using path splitting, on the right - path halving.
Functional implementation
The system of disjoint sets has one big drawback: it does not support the Undo operation in any form, because it is implemented through in an imperative style. It would be much more convenient to implement a functional-style DSU, when each operation does not change the structure in place, but returns a slightly modified new structure in which the required changes are made (while most of the memory of the old and new structures is common). Such data structures are called persistent in English terminology ; they are widely used in pure functional programming, where the idea of data immutability dominates.
Due to the purely imperative idea of DSU algorithms, its functional implementation, while maintaining performance, for a long time seemed unthinkable. However, in 2007, Sylvain Conchon and Jean-Christophe Filliâtre presented in their work the desired functional version, in which the Unite operation returns a changed structure. To be honest, it is not entirely functional, it uses imperative assignments, however, they are securely hidden inside the implementation, and the persistent DSU interface is purely functional.
The main idea of the implementation is the use of data structures that implement “persistent arrays”: they support the same operations as arrays, but they still do not modify the memory, but return the changed structure. Such an array can be easily implemented using some tree, however, in this case, operations with it will take O (log 2 N) time, and for DSU this estimate is already excessively large.
For further technical details, send readers to the original article .
Literature
The systems of disjoint sets in the scope of this article are discussed in the famous book - Cormen, Leiserson, Rivest, Stein "Algorithms: construction and analysis." There you can find evidence that the operation takes about α (N) time.
On the site of Maxim Ivanov, you can find the full implementation of DSU in C ++.
The Wait-free Parallel Algorithms for the Union-Find Problem article discusses the parallel version of the DSU implementation. It does not have thread locks.
Thank you all for your attention :-)
