Class UnionFind
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

Interface Metafunction Overview

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!

Interface Metafunctions Detail

GetValue<TUnionFind>::Type

Returns the get-value type for the given UnionFind specialization.

Template Parameters

TUnionFind The UnionFind specialization to query for its get-value type.

Size<TUnionFind>::Type

Returns the size type for the given UnionFind specialization.

Template Parameters

TUnionFind The UnionFind specialization to query for its size type.

Value<TUnionFind>::Type

Returns the value type for the given UnionFind specialization.

Template Parameters

TUnionFind The UnionFind specialization to query for its value type.