#include <lemon/unionfind.h>
The union operation uses rank heuristic, while the find operation uses path compression.
Public Member Functions | |
void | insert (const Item &item) |
Inserts the given element into a new component. | |
void | insert (const Item &item, const Item &comp) |
Inserts the given element into the component of the others. | |
const Item & | find (const Item &item) const |
Finds the leader of the component of the given element. | |
bool | join (const Item &a, const Item &b) |
Joining the component of element a and element b. | |
int | size (const Item &item) const |
Returns the size of the component of element a. | |
void | split (const Item &item) |
Splits up the component of the element. | |
void | makeRep (const Item &item) |
Sets the given element to the leader element of its component. | |
void | erase (const Item &item) |
Removes the given element from the structure. | |
bool | move (const Item &item, const Item &comp) |
Moves the given element to another component. | |
void | eraseClass (const Item &item) |
Removes the component of the given element from the structure. | |
Classes | |
class | ClassIt |
Lemon style iterator for the representant items. More... | |
class | ItemIt |
Lemon style iterator for the items of a component. More... |
void insert | ( | const Item & | item | ) | [inline] |
This method creates a new component consisting only of the given element.
void insert | ( | const Item & | item, | |
const Item & | comp | |||
) | [inline] |
This methods inserts the element a into the component of the element comp.
const Item& find | ( | const Item & | item | ) | const [inline] |
The method returns the leader of the component of the given element.
bool join | ( | const Item & | a, | |
const Item & | b | |||
) | [inline] |
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.
int size | ( | const Item & | item | ) | const [inline] |
Returns the size of the component of element a.
void split | ( | const Item & | item | ) | [inline] |
Splitting the component of the element into sigleton components (component of size one).
void makeRep | ( | const Item & | item | ) | [inline] |
Sets the given element to the leader element of its component.
void erase | ( | const Item & | item | ) | [inline] |
Removes the element from its component and if the component becomes empty then removes that component from the component list.
bool move | ( | const Item & | item, | |
const Item & | comp | |||
) | [inline] |
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.
void eraseClass | ( | const Item & | item | ) | [inline] |
Removes the component of the given element from the structure.