#include <lemon/unionfind.h>
The union operation uses rank heuristic, while the find operation uses path compression.
Public Member Functions | |
void | insert (const T &a) |
Inserts the given element into a new component. | |
void | insert (const T &a, const T &comp) |
Inserts the given element into the component of the others. | |
T | find (const T &a) const |
Finds 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) |
Splits up the component of the element. | |
void | makeRep (const T &a) |
Sets the given element to the leader element of its component. | |
bool | move (const T &a, const T &comp) |
Moves the given element to an other component. | |
void | erase (const T &a) |
Removes 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. |
|
This methods inserts the element a into the component of the element comp. |
|
The method returns the leader of the component of the given element. |
|
This is the union operation of the Union-Find structure. Joins the component of element a and component of element b. If a and b are in the same component then returns false else returns true. |
|
Returns the size of the component of element a. |
|
Splitting the component of the element into sigleton components (component of size one). |
|
Sets the given element to the leader element of its component. |
|
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. |
|
Removes 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. |
|
Removes the component of the given element from the structure. |
|
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; } |
|
Returns whether the iterator is valid. With the first, valid and next methods you can iterate through the components. See the example here: first. |
|
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. |
|
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; } |
|
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. |
|
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. |