#include <lemon/unionfind.h>
The union operation uses rank heuristic, while the find operation uses path compression.
Definition at line 228 of file unionfind.h.
Public Member Functions | |
void | insert (const T &a) |
Insert the given element into a new component. | |
void | insert (const T &a, const T &comp) |
Insert the given element into the component of the others. | |
T | find (const T &a) const |
Find the leader of the component of the given element. | |
bool | join (T a, T b) |
Joining the component of element a and element b. | |
int | size (const T &a) const |
Returns the size of the component of element a. | |
void | split (const T &a) |
Split up the component of the element. | |
void | makeRep (const T &a) |
Set the given element to the leader element of its component. | |
bool | move (const T &a, const T &comp) |
Move the given element to an other component. | |
void | erase (const T &a) |
Remove the given element from the structure. | |
void | eraseClass (const T &a) |
Removes the component of the given element from the structure. | |
ClassIt & | first (ClassIt &it) const |
Sets the iterator to point to the first component. | |
bool | valid (ClassIt const &it) const |
Returns whether the iterator is valid. | |
ClassIt & | next (ClassIt &it) const |
Steps the iterator to the next component. | |
ItemIt & | first (ItemIt &it, const T &a) const |
Sets the iterator to point to the first element of the component. | |
bool | valid (ItemIt const &it) const |
Returns whether the iterator is valid. | |
ItemIt & | next (ItemIt &it) const |
Steps the iterator to the next component. |
|
This method creates a new component consisting only of the given element. Definition at line 272 of file unionfind.h. |
|
This methods insert the element a into the component of the element comp. Definition at line 296 of file unionfind.h. |
|
The method returns the leader of the component of the given element. Definition at line 315 of file unionfind.h. |
|
This is the union operation of the Union-Find structure. Joins the component of elemenent a and component of element b. If a and b are in the same component then returns false else returns true. Definition at line 329 of file unionfind.h. |
|
Returns the size of the component of element a. Definition at line 371 of file unionfind.h. |
|
Splitting the component of the element into sigleton components (component of size one). Definition at line 383 of file unionfind.h. |
|
Set the given element to the leader element of its component. Definition at line 413 of file unionfind.h. |
|
This method moves the element a from its component to the component of comp. If a and comp are in the same component then it returns false otherwise it returns true. Definition at line 440 of file unionfind.h. |
|
Remove the given element from the structure. Removes the element from its component and if the component becomes empty then removes that component from the component list. Definition at line 493 of file unionfind.h. |
Here is the call graph for this function:
|
Removes the component of the given element from the structure. Definition at line 525 of file unionfind.h. |
|
Sets the iterator to point to the first component. With the first, valid and next methods you can iterate through the components. For example: UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G); UnionFindEnum<Graph::Node, Graph::NodeMap> U(map); UnionFindEnum<Graph::Node, Graph::NodeMap>::ClassIt iter; for (U.first(iter); U.valid(iter); U.next(iter)) { // iter is convertible to Graph::Node cout << iter << endl; } Definition at line 589 of file unionfind.h. |
|
Returns whether the iterator is valid. With the first, valid and next methods you can iterate through the components. See the example here: first. Definition at line 603 of file unionfind.h. |
|
Steps the iterator to the next component. With the first, valid and next methods you can iterate through the components. See the example here: first. Definition at line 616 of file unionfind.h. |
|
Sets the iterator to point to the first element of the component. With the first, valid and next methods you can iterate through the elements of a component. For example (iterating through the component of the node node): Graph::Node node = ...; UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G); UnionFindEnum<Graph::Node, Graph::NodeMap> U(map); UnionFindEnum<Graph::Node, Graph::NodeMap>::ItemIt iiter; for (U.first(iiter, node); U.valid(iiter); U.next(iiter)) { // iiter is convertible to Graph::Node cout << iiter << endl; } Definition at line 679 of file unionfind.h. |
|
Returns whether the iterator is valid. With the first, valid and next methods you can iterate through the elements of a component. See the example here: first. Definition at line 696 of file unionfind.h. |
|
Steps the iterator to the next component. With the first, valid and next methods you can iterate through the elements of a component. See the example here: first. Definition at line 712 of file unionfind.h. |