Référence du fichier integer_uf.h

structure de données union-find contenant des valeurs de type int . Plus de détails...

#include <stdbool.h>

Aller au code source de ce fichier.

Structures de données
struct	integer_uf_elm
	Type de données pour représenter un élément de la structure union-find contenant des valeurs de type int Plus de détails...
struct	integer_uf
	Type de données pour représenter la structure union-find contenant des valeurs de type int Plus de détails...

Définitions de type
typedef struct integer_uf_elm	integer_uf_elm_t
	Type de données pour représenter un élément de la structure union-find contenant des valeurs de type int
typedef struct integer_uf	integer_uf_t
	Type de données pour représenter la structure union-find contenant des valeurs de type int

Fonctions
void	integer_uf_init (integer_uf_t *dset, int size)
	Initialisation d'une nouvelle structure union-find.
void	integer_uf_destroy (integer_uf_t *dset)
	Destruction d'une structure union-find.
int	integer_uf_add_element (integer_uf_t *dset, int value)
	Ajout d'un nouvel élément dans une structure union-find.
int	integer_uf_find (integer_uf_t *dset, int value, integer_uf_elm_t **result)
	Cherche le représentant d'une classe d'équivalence.
int	integer_uf_union (integer_uf_t *dset, int value1, int value2)
	Associe deux éléments dans une même classe d'équivalence.
bool	integer_uf_are_connected (integer_uf_t *dset, int value1, int value2)
	Prédicat pour tester si deux éléments sont dans la même classe d'équivalence.
int	integer_uf_size (integer_uf_t *dset)
	Accesseur sur la taille maximale de l'ensemble.
int	integer_uf_components (integer_uf_t *dset)
	Accesseur sur le nombre de classes d'équivalence.

Description détaillée

structure de données union-find contenant des valeurs de type int .

Une structure d'union-find est un ensemble de valeurs entières organisé en classe d'équivalence. La structure est représentée par un arbre avec plusieurs racines. Chaque racine est le représentant de la classe d'équivalence.

Documentation des définitions de type

integer_uf_elm_t

typedef struct integer_uf_elm integer_uf_elm_t

Type de données pour représenter un élément de la structure union-find contenant des valeurs de type int

Une structure union-find est structure arborescente avec possiblement plusieurs racines. Chaque élément de l'arbre contient une valeur, un pointeur vers son parent et une valeur indiquant sa profondeur dans l'arbre.

integer_uf_t

typedef struct integer_uf integer_uf_t

Type de données pour représenter la structure union-find contenant des valeurs de type int

Une structure union-find est structure arborescente représentée par un tableau dont les éléments sont de type integer_uf_elm_t, une valeur représentant la taille du tableau et une valeur représentant le nombre de classes d'équivalence.

Documentation des fonctions

integer_uf_add_element()

int integer_uf_add_element	(	integer_uf_t *	dset,
		int	value )

Ajout d'un nouvel élément dans une structure union-find.

La valeur d'un élément de l'ensemble est associé à l'indice du tableau. Alloue en position value alloue la mémoire d'une structure de données integer_uf_elm_t. Considère cet élément comme une nouvelle classe d'équivalence, fixe la valeur stockée à la valeur value, considère que cet élément n'a pas de parent et une profondeur de zéro.

Paramètres

dset	est un pointeur vers la structure de données union-find integer_uf_t
value	est un entier représentant la nouvelle valeur à ajouter dans l'ensemble.

Renvoie

valeur entière indiquant si tout s'est bien passé (0 pour ok, -1 pour erreur mémoire)

integer_uf_are_connected()

bool integer_uf_are_connected	(	integer_uf_t *	dset,
		int	value1,
		int	value2 )

Prédicat pour tester si deux éléments sont dans la même classe d'équivalence.

Etant données deux valeurs de l'ensemble, teste si les représentants des classes d'équivalence sont les mêmes

Paramètres

dset	est un pointeur vers la structure de données integer_uf_t
value1	un élément de l'ensemble
value2	un élément de l'ensemble

Renvoie

un booléen indiquant vrai si value1 et value2 sont dans la même classe d'équivalence

integer_uf_components()

int integer_uf_components

(

integer_uf_t *

dset

)

Accesseur sur le nombre de classes d'équivalence.

Etant donné un pointeur vers un structure d'union-find, retourne la valeur du champ components

Paramètres

dset	est un pointeur vers la structure de données integer_uf_t

Renvoie

un entier indiquant le nombre de classes d'équivalence

integer_uf_destroy()

void integer_uf_destroy

(

integer_uf_t *

dset

)

Destruction d'une structure union-find.

Parcours du tableau pour désallouer chaque élément, désalloue le tableau, et fixe à zéro la taille et le nombre de classes d'équivalence.

Paramètres

dset	est un pointeur vers la structure de données union-find integer_uf_t

integer_uf_find()

int integer_uf_find	(	integer_uf_t *	dset,
		int	value,
		integer_uf_elm_t **	result )

Cherche le représentant d'une classe d'équivalence.

Etant donné une valeur de l'ensemble, retourne le représentant de la classe d'équivalence * à laquelle value appartient. Durant la recherche du représentant, l'algorithme applique la technique de la compression de chemin.

Paramètres

dset	est un pointeur vers la structure de données union-find integer_uf_t
value	est un élément de l'ensemble
result	renvoie la structure de données de type integer_uf_elm_t* associée au représentant de la classe d'équivalence. result vaut NULL si value n'est pas dans l'ensemble.

Renvoie

valeur entière indiquant si tout s'est bien passé (0 pour ok, -1 si value n'est pas dans l'ensemble)

integer_uf_init()

void integer_uf_init	(	integer_uf_t *	dset,
		int	size )

Initialisation d'une nouvelle structure union-find.

Alloue la mémoire du tableau en fonction du nombres d'éléments maximal de l'ensemble considéré. Chaque élément du tableau est initialisé à NULL. Le nombre de classe d'équivalence est fixée à 0. Initiallement, on considère qu'aucun élément de l'ensemble n'a été ajouté.

Paramètres

dset	est un pointeur vers la structure de données union-find integer_uf_t
size	nombre maximal d'éléments dans l'ensemble

integer_uf_size()

int integer_uf_size

(

integer_uf_t *

dset

)

Accesseur sur la taille maximale de l'ensemble.

Etant donné un pointeur vers un structure d'union-find, retourne la valeur du champ size

Paramètres

dset	est un pointeur vers la structure de données integer_uf_t

Renvoie

un entier indiquant la taille maximale de l'ensemble

integer_uf_union()

int integer_uf_union	(	integer_uf_t *	dset,
		int	value1,
		int	value2 )

Associe deux éléments dans une même classe d'équivalence.

Etant donné deux valeurs de l'ensemble, considère que ces deux éléments sont dans une même classe d'équivalence en désigant l'une d'entre elles comme parent de l'autre. L'algorithme applique la méthode fusion par rang ou par profondeur pour limité l'accroissement de l'arbre associé à une même classe d'équivalence.

Paramètres

dset	est un pointeur vers la structure de données union-find integer_uf_t
value1	est un élément de l'ensemble
value2	est un élément de l'ensemble

Renvoie

valeur entière indiquant si tout s'est bien passé (0 pour ok, -1 si value1 ou value2 n'est pas dans l'ensemble)