type_partitions.h File Reference

Types used to represent partitions. Includes the union-find algorithm. More...

#include "alloc.h"
#include "stdbool.h"
#include "stdlib.h"
#include "type_basic.h"
#include "type_dequeue.h"

Go to the source code of this file.

Classes
struct	parti
	First type used to represent a partition. This is not the one used by Union-Find. More...
struct	ufind
	Second type used to represent a partition. This is the type used by Union-Find. More...

Functions
parti *	create_parti (uint size_set, uint size_par, uint *numcl)
	Creation of a partition.
void	delete_parti (parti *)
	Release of a partition.
bool	istrivial_parti (parti *)
	Checks whether a partition is trivial (all classes are singletons).
parti *	restrict_parti (parti *, uint, bool *, uint *)
	Restriction of a partition to a subset of the partitioned set.
parti *	restrict_parti_subset (parti *, uint, bool *, uint *, uint *)
	Restriction of a partition to a subset of the partitioned set. Input partition is already a partition of a subset.
uint *	parti_compute_inv (parti *P)
	Computes the inverse mapping of a partition.
ufind *	create_ufind (uint)
	Creation of a trivial union-find partition (all classes are singletons).
void	delete_ufind (ufind *)
	Release of a union-find partition.
uint	sizeset_ufind (ufind *)
	Computes the size of the partitioned set in a union-find partition.
uint	sizepar_ufind (ufind *)
	Computes the size of the partition in a union-find partition.
void	makeset_ufind (ufind *)
	Increments the size of the partionned set in a union-find partition.
uint	find_ufind (uint, ufind *)
	Computes the class number of an element in a union-find partition.
uint	sizeclass_ufind (uint, ufind *)
	Computes the size of the class of an element in a union-find partition.
void	union_ufind (uint, uint, ufind *)
	Merging of the classes of two elements in a union-find partition.
void	print_ufind (ufind *)
	Displays a union-find partition.
ufind *	parti_to_ufind (parti *)
	Conversion from the partition type to the union-find type.
parti *	ufind_to_parti (ufind *)
	Conversion from the union-find type to the partition type.
parti *	ufind_to_parti_refined (ufind *, parti *)
	Conversion from the union-find type to the partition type. In this case, a partition that is coarser that the union-find partition is also given as input.

Detailed Description

Types used to represent partitions. Includes the union-find algorithm.

Function Documentation

create_parti()

parti * create_parti	(	uint	size_set,
		uint	size_par,
		uint *	numcl )

Creation of a partition.

Returns

The partition.

Parameters

size_set	The size of the partitioned set.
size_par	The size of the partition.
numcl	The array mapping each element to its class (used in the structure as numcl)

create_ufind()

ufind * create_ufind

(

uint

size

)

Creation of a trivial union-find partition (all classes are singletons).

Returns

The union-find partition.

Parameters

size	The size of the partitioned set.

delete_parti()

void delete_parti

(

parti *

p

)

Release of a partition.

Parameters

p	The partition that needs to be freed.

delete_ufind()

void delete_ufind

(

ufind *

uf

)

Release of a union-find partition.

Parameters

uf	The union-find partition.

find_ufind()

uint find_ufind	(	uint	i,
		ufind *	uf )

Computes the class number of an element in a union-find partition.

Returns

The class number of the element.

Parameters

i	The element.
uf	The union-find partition.

istrivial_parti()

bool istrivial_parti

(

parti *

p

)

Checks whether a partition is trivial (all classes are singletons).

Returns

A Boolean indicating whether the partition is trivial.

Parameters

p	The partition.

makeset_ufind()

void makeset_ufind

(

ufind *

uf

)

Increments the size of the partionned set in a union-find partition.

Remarks

The class of the new element is a singleton.

Parameters

uf	The union-find partition.

parti_compute_inv()

uint * parti_compute_inv

(

parti *

P

)

Computes the inverse mapping of a partition.

For each element in the partitioned set, the inverse mapping gives the index of the element in its class.

Returns

The inverse mapping of the partition.

Parameters

P	The partition.

parti_to_ufind()

ufind * parti_to_ufind

(

parti *

p

)

Conversion from the partition type to the union-find type.

Returns

A representation of the input partition in the union-find type.

Parameters

p	The partition.

print_ufind()

void print_ufind

(

ufind *

uf

)

Displays a union-find partition.

Parameters

uf	The union-find partition.

restrict_parti()

parti * restrict_parti	(	parti *	P,
		uint	size,
		bool *	insub,
		uint *	tosub )

Restriction of a partition to a subset of the partitioned set.

Remarks

Ordering of the classes is preserved.

Returns

The restricted partition.

Parameters

P	The partition.
size	The size of the subset.
insub	The array of Booleans indicating which elements are to be kept.
tosub	The array mapping each kept element to its index in the subset.

restrict_parti_subset()

parti * restrict_parti_subset	(	parti *	P,
		uint	size,
		bool *	insub,
		uint *	tosub,
		uint *	fromind )

Restriction of a partition to a subset of the partitioned set. Input partition is already a partition of a subset.

Remarks

Ordering of the classes is preserved.

Returns

The restricted partition.

Parameters

P	The partition.
size	The size of the subset.
insub	The array of Booleans indicating which elements are to be kept.
tosub	The array mapping each kept element to its index in the subset.

sizeclass_ufind()

uint sizeclass_ufind	(	uint	i,
		ufind *	uf )

Computes the size of the class of an element in a union-find partition.

Returns

The size of the class of the element.

Parameters

i	The element.
uf	The union-find partition.

sizepar_ufind()

uint sizepar_ufind

(

ufind *

uf

)

Computes the size of the partition in a union-find partition.

Returns

The size of the partition.

Parameters

uf	The union-find partition.

sizeset_ufind()

uint sizeset_ufind

(

ufind *

uf

)

Computes the size of the partitioned set in a union-find partition.

Returns

The size of the partitioned set.

Parameters

uf	The union-find partition.

ufind_to_parti()

parti * ufind_to_parti

(

ufind *

uf

)

Conversion from the union-find type to the partition type.

Returns

A representation of the input partition in the partition type.

Parameters

uf	The union-find partition.

ufind_to_parti_refined()

parti * ufind_to_parti_refined	(	ufind *	uf,
		parti *	P )

Conversion from the union-find type to the partition type. In this case, a partition that is coarser that the union-find partition is also given as input.

Returns

A representation of the input partition in the partition type.

Parameters

uf	The union-find partition.
P	A partition coarser than the union-find partition.

union_ufind()

void union_ufind	(	uint	i,
		uint	j,
		ufind *	uf )

Merging of the classes of two elements in a union-find partition.

Parameters

i	The first element.
j	The second element.
uf	The union-find partition.