Disjoint-Set

A disjoint-set implementation using a union-find algorithm. More...

Typedefs
typedef struct disjoint_set	disjoint_set_t
	Opaque type for a disjoint-set.
Functions
int	disjoint_set_new (disjoint_set_t **ds, size_t size)
	Creates a new disjoint-set.
int	disjoint_set_free (disjoint_set_t *ds)
	Frees a disjoint-set.
int	disjoint_set_union (disjoint_set_t *ds, size_t id1, size_t id2)
	Unites the sets that contain two elements.
int	disjoint_set_find (disjoint_set_t *ds, size_t *set_id, size_t id)
	Finds the set containing an element.

---

Detailed Description

A disjoint-set implementation using a union-find algorithm.

---

Function Documentation

int disjoint_set_find	(	disjoint_set_t *	ds,
		size_t *	set,
		size_t	elem
	)

Finds the set containing an element.

Parameters:

	ds	the disjoint_set_t to search in
[out]	set	the found set
	elem	the element to find the set of

Returns:

the operation error code

Definition at line 181 of file disjoint_set.c.

References find_set().

Referenced by disjoint_set_union(), and overlap_graph_remove_cycles().

Here is the call graph for this function:

Here is the caller graph for this function:

int disjoint_set_free

(

disjoint_set_t *

ds

)

Frees a disjoint-set.

Parameters:

ds

the disjoint_set_t to free

Returns:

the operation error code

Definition at line 134 of file disjoint_set.c.

Referenced by overlap_graph_remove_cycles().

Here is the caller graph for this function:

int disjoint_set_new	(	disjoint_set_t **	ds,
		size_t	size
	)

Creates a new disjoint-set.

The disjoint-set contains integer elements from 0 to size - 1, initially each in its own set.

Parameters:

[out]	ds	the created disjoint_set_t
	size	the size of the disjoint-set

Returns:

the operation error code

Definition at line 94 of file disjoint_set.c.

Referenced by overlap_graph_remove_cycles().

Here is the caller graph for this function:

int disjoint_set_union	(	disjoint_set_t *	ds,
		size_t	elem1,
		size_t	elem2
	)

Unites the sets that contain two elements.

Parameters:

	ds	the disjoint_set_t that contains the elements
	elem1	the first element
	elem2	the second element

Returns:

the operation error code

Definition at line 156 of file disjoint_set.c.

References disjoint_set_find(), and link_sets().

Referenced by overlap_graph_remove_cycles().

Here is the call graph for this function:

Here is the caller graph for this function: