Class
UnionFindUnion-Find data structure.
Union-Find data structure.
Defined in | <seqan/misc/union_find.h> |
---|---|
Signature |
template <typename T>
class UnionFind;
|
Template Parameters
T |
The integer type the data structure operates on. |
---|
Interface Function Overview
-
void clear(uf);
Clear the Union-Find data structure. -
TValue findSet(uf, q);
Return set identifier, given an element identifier. -
void joinSets(uf, left, right);
UNION() operation for Union-Find data structure. -
TSize length(uf);
Returns the number of entries in the Union-Find object. -
TSize resize(uf, size, tag);
Allocate number of elements for the Union-Find object. -
TSize resizeVertexMap(uf, g);
Resize Union-Find data structure to appropriate size for a vertex map. -
void reserve(uf, size, tag);
Reserve memory for the Union-Find object.
Interface Metafunction Overview
-
GetValue<TUnionFind>::Type
Returns the get-value type for the given UnionFind specialization. -
Size<TUnionFind>::Type
Returns the size type for the given UnionFind specialization. -
Value<TUnionFind>::Type
Returns the value type for the given UnionFind specialization.
Detailed Description
The data structure uses union by rank and path compresison to achieve almost linear running time.
Note that internally T is used as signed, so not the whole range is available if T is unsigned.
Interface Functions Detail
void clear(uf);
Clear the Union-Find data structure.
Parameters
uf
|
The Union-Find object to clear |
---|
Data Races
Thread safety unknown!
TValue findSet(uf, q);
Return set identifier, given an element identifier.
Parameters
uf
|
The Union-Find object to query. |
---|---|
q
|
The value to get the set identifier for. |
Returns
TValue |
Identifier of the set that q is in (Metafunction: Value). |
---|
Data Races
Thread safety unknown!
See Also
void joinSets(uf, left, right);
UNION() operation for Union-Find data structure.
Parameters
uf
|
The type the data structure operates on. |
---|---|
left
|
Representant of the left set to union. |
right
|
Representant of the right set to union. |
This function is called join and not union since union is a reserved keyword in the C and C++ programming languages.
Note that you most likely want to put return values of findSet() as the values for left and right.
Data Races
Thread safety unknown!
See Also
TSize length(uf);
Returns the number of entries in the Union-Find object.
Parameters
uf
|
The Union-Find object to query. |
---|
Returns
TSize |
The length of the Union-Find object (Metafunction: Size). |
---|
Data Races
Thread safety unknown!
TSize resize(uf, size, tag);
Allocate number of elements for the Union-Find object.
Parameters
uf
|
The Union-Find object to resize. |
---|---|
size
|
The number of elements to reserve. |
tag
|
The tag to use for reserving (defaults to Generous()). |
Returns
TSize |
The new length of the Union-Find object (Metafunction: Size). |
---|
The UF dat structure is resized to the given size, the value for each element is set to -1, i.e. they are singletons by default.
Data Races
Thread safety unknown!
TSize resizeVertexMap(uf, g);
Resize Union-Find data structure to appropriate size for a vertex map.
Parameters
uf
|
The Union-Find object to resize. |
---|---|
g
|
The graph to use for getting the vertex number. |
Returns
TSize |
New size of the vertex map (Metafunction: Size). |
---|
Data Races
Thread safety unknown!
void reserve(uf, size, tag);
Reserve memory for the Union-Find object.
Parameters
uf
|
The Union-Find object to reserve memory in. |
---|---|
size
|
The number of elements to reserve. |
tag
|
The tag to use for reserving (defaults to Generous()). |
Data Races
Thread safety unknown!