Référence du fichier generic_graph.h

Structure de données de graphes orientés ou non, pondérés ou non, représentés par une liste d'adjacence. Plus de détails...

#include <stdlib.h>
#include <stdbool.h>
#include "generic_list.h"
#include "generic_set.h"

Aller au code source de ce fichier.

Structures de données
struct	generic_adjlist_
	Type de données pour représenter la liste des voisins d'un sommet du graphe. Plus de détails...
struct	generic_graph_
	Type de données pour représenter un graphe comme une liste d'adjacence. Plus de détails...

Définitions de type
typedef struct generic_adjlist_	generic_adjlist_t
	Type de données pour représenter la liste des voisins d'un sommet du graphe.
typedef struct generic_graph_	generic_graph_t
	Type de données pour représenter un graphe comme une liste d'adjacence.
typedef enum vertexcolor_	vertexcolor_t
	Type de données pour annoter les sommets lors d'un parcours de graphe.

Énumérations
enum	vertexcolor_ { white , gray , black }
	Type de données pour annoter les sommets lors d'un parcours de graphe. Plus de détails...

Fonctions
void	generic_graph_init (generic_graph_t *graph, int(*compare)(const void *key1, const void *key2), void *(*build)(const void *data), void(*destroy)(void *data))
	Initialisation d'un nouveau graphe.
void	generic_graph_destroy (generic_graph_t *graph)
	Destruction d'un graphe.
int	generic_graph_ins_vertex (generic_graph_t *graph, const void *data)
	Insertion d'un nouveau sommet dans un graphe.
int	generic_graph_ins_edge (generic_graph_t *graph, const void *data1, const void *data2)
	Insertion d'un nouvel arc dans un graphe.
int	generic_graph_rem_vertex (generic_graph_t *graph, void **data)
	Suppression d'un sommet dans un graphe.
int	generic_graph_rem_edge (generic_graph_t *graph, void *data1, void **data2)
	Suppression d'un arc dans un graphe.
int	generic_graph_adjlist (const generic_graph_t *graph, const void *data, generic_adjlist_t **adjlist)
	Accesseur de la liste des voisins d'un sommet.
bool	generic_graph_is_adjacent (const generic_graph_t *graph, const void *data1, const void *data2)
	Prédicat indiquant si deux sommets sont liés par un arc.
generic_list_t	generic_graph_adjlists (generic_graph_t *graph)
	Accesseur de la liste d'ajdacence d'un graphe.
int	generic_graph_vcount (generic_graph_t *graph)
	Accesseur du nombre de sommets du graphe.
int	generic_graph_ecount (generic_graph_t *graph)
	Accesseur du nombre d'arcs du graphe.

Description détaillée

Structure de données de graphes orientés ou non, pondérés ou non, représentés par une liste d'adjacence.

Une liste d'adjacence est représentée par une liste simplement chainée (générique) dont les éléments sont des ensembles (génériques) contenant des valeurs et un poids (pondération de l'arc).

Documentation des définitions de type

generic_adjlist_t

typedef struct generic_adjlist_ generic_adjlist_t

Type de données pour représenter la liste des voisins d'un sommet du graphe.

generic_graph_t

typedef struct generic_graph_ generic_graph_t

Type de données pour représenter un graphe comme une liste d'adjacence.

vertexcolor_t

typedef enum vertexcolor_ vertexcolor_t

Type de données pour annoter les sommets lors d'un parcours de graphe.

Documentation du type de l'énumération

vertexcolor_

enum vertexcolor_

Type de données pour annoter les sommets lors d'un parcours de graphe.

Valeurs énumérées
white	drapeau pour indiquer un sommet non considéré
gray	drapeau pour indiquer un sommet en cours de traitement
black	drapeau pour indiquer un sommet qui a été traité

Documentation des fonctions

generic_graph_adjlist()

int generic_graph_adjlist	(	const generic_graph_t *	graph,
		const void *	data,
		generic_adjlist_t **	adjlist )

Accesseur de la liste des voisins d'un sommet.

Paramètres

graph	est un pointeur vers la structure de données de graphe generic_graph_t
data	sommet pour lequel la liste des voisins est voulue

Renvoie

un pointeur vers une liste chainée de type generic_list_t contenant la liste des voisins (sans pondération)

generic_graph_adjlists()

generic_list_t generic_graph_adjlists

(

generic_graph_t *

graph

)

Accesseur de la liste d'ajdacence d'un graphe.

Paramètres

graph

est un pointeur vers la structure de données de graphe generic_graph_t

Renvoie

un pointeur vers une liste chainée de type generic_list_t contenant la liste des sommets et leurs voisins

generic_graph_destroy()

void generic_graph_destroy

(

generic_graph_t *

graph

)

Destruction d'un graphe.

Parcours la liste d'adjacence (adjlists) puis parcours de l'ensemble (adjacent) pour détruire tous les éléments de la liste d'adjacence. Puis, mise à zéro du nombre de sommets, du nombre d'arcs et à NULL la liste d'adjacence (adjlists)

Paramètres

graph

est un pointeur vers la structure de données de graphe generic_graph_t

generic_graph_ecount()

int generic_graph_ecount

(

generic_graph_t *

graph

)

Accesseur du nombre d'arcs du graphe.

Paramètres

graph

est un pointeur vers la structure de données de graphe generic_graph_t

Renvoie

valeur entière donnant le nombre d'arcs du graphe

generic_graph_init()

void generic_graph_init	(	generic_graph_t *	graph,
		int(*)(const void *key1, const void *key2)	compare,
		void *(*)(const void *data)	build,
		void(*)(void *data)	destroy )

Initialisation d'un nouveau graphe.

Met à zéro du nombre de sommets, du nombre d'arcs et initialisation de la liste d'adjacence. Cette fonction nécessite une fonction de comparaison des éléments du graphe, une fonction de construction d'un élément du graphe et une fonction de destruction des éléments du graphe.

Paramètres

graph	est un pointeur vers la structure de données de graphe generic_graph_t
compare	fonction permettant la comparaison de deux sommets du graphe
build	fonction permettant la construction d'un sommet du graphe
destroy	fonction permettant la destruction d'un sommet du graphe

generic_graph_ins_edge()

int generic_graph_ins_edge	(	generic_graph_t *	graph,
		const void *	data1,
		const void *	data2 )

Insertion d'un nouvel arc dans un graphe.

Remarque: par défaut on considère un arc directionnel donc un graphe dirigé.

1. Vérifie que l'arc n'existe pas déjà
2. Ajoute un nouveau voisin au sommet data1 avec la pondération
3. Mise à jour du nombre d'arcs dans le graphe

Paramètres

graph	est un pointeur vers la structure de données de graphe generic_graph_t
data1	source de l'arc, représenté par une valeur de type void*
data2	destination de l'arc, représenté par une valeur de type void*

Renvoie

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

generic_graph_ins_vertex()

int generic_graph_ins_vertex	(	generic_graph_t *	graph,
		const void *	data )

Insertion d'un nouveau sommet dans un graphe.

1. Parcours la liste d'adjacence (adjlists) pour savoir si le sommet est déjà présent ou pas
2. Si pas présent, ajout d'un nouvel élément à la liste d'adjacence (adjlists)
3. Mise à jour du nombre de sommets dans le graphe

Paramètres

graph	est un pointeur vers la structure de données de graphe generic_graph_t
data	nouveau noeud, représenté par une valeur de type void*, à ajouter

Renvoie

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

generic_graph_is_adjacent()

bool generic_graph_is_adjacent	(	const generic_graph_t *	graph,
		const void *	data1,
		const void *	data2 )

Prédicat indiquant si deux sommets sont liés par un arc.

Remarque: on considère le lien directionnel entre deux sommets.

Paramètres

graph	est un pointeur vers la structure de données de graphe generic_graph_t
data1	sommet source
data2	sommet destination

Renvoie

une valeur booléenne indiquant s'il y a un arc entre vertex1 et vertex2 (orienté).

generic_graph_rem_edge()

int generic_graph_rem_edge	(	generic_graph_t *	graph,
		void *	data1,
		void **	data2 )

Suppression d'un arc dans un graphe.

1. Vérifie que l'arc existe
2. Si oui suppression du sommet data2 dans la liste des voisins de data1
3. Mise à jour du nombre de sommets dans le graphe

Paramètres

graph	est un pointeur vers la structure de données de graphe generic_graph_t
data1	source de l'arc, représenté par une valeur de type void*
data2	destination de l'arc, représenté par une valeur de type void*

Renvoie

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

generic_graph_rem_vertex()

int generic_graph_rem_vertex	(	generic_graph_t *	graph,
		void **	data )

Suppression d'un sommet dans un graphe.

On peut supprimer un sommet que s'il n'a plus de voisins, c'est à dire, plus d'arc entre lui et les autres sommets du graphe.

1. Vérifie que le sommet ne contient pas de voisins (adjlists vide)
2. Si oui suppression du sommet
3. Mise à jour du nombre de sommets dans le graphe

Paramètres

graph	est un pointeur vers la structure de données de graphe generic_graph_t
data	sommet à supprimer

Renvoie

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

generic_graph_vcount()

int generic_graph_vcount

(

generic_graph_t *

graph

)

Accesseur du nombre de sommets du graphe.

Paramètres

graph

est un pointeur vers la structure de données de graphe generic_graph_t

Renvoie

valeur entière donnant le nombre de sommets du graphe