Référence du fichier integer_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 "list.h"
#include "set.h"

Aller au code source de ce fichier.

Structures de données
struct	integer_adjlist_elmt_
	Type de données pour représenter un élément dans la liste des voisins d'un sommet du graphe. Plus de détails...
struct	integer_adjlist_
	Type de données pour représenter la liste des voisins d'un sommet du graphe. Plus de détails...
struct	integer_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 integer_adjlist_elmt_	integer_adjlist_elmt_t
	Type de données pour représenter un élément dans la liste des voisins d'un sommet du graphe.
typedef struct integer_adjlist_	integer_adjlist_t
	Type de données pour représenter la liste des voisins d'un sommet du graphe.
typedef struct integer_graph_	integer_graph_t
	Type de données pour représenter un graphe comme une liste d'adjacence.
typedef enum integer_vertexcolor_	integer_vertexcolor_t
	Type de données pour annoter les sommets lors d'un parcours de graphe.

Énumérations
enum	integer_vertexcolor_ { integer_white , integer_gray , integer_black }
	Type de données pour annoter les sommets lors d'un parcours de graphe. Plus de détails...

Fonctions
void	integer_graph_init (integer_graph_t *graph)
	Initialisation d'un nouveau graphe.
void	integer_graph_destroy (integer_graph_t *graph)
	Destruction d'un graphe.
int	integer_graph_ins_vertex (integer_graph_t *graph, int vertex)
	Insertion d'un nouveau sommet dans un graphe.
int	integer_graph_ins_edge (integer_graph_t *graph, int vertex1, int vertex2, double weight)
	Insertion d'un nouvel arc dans un graphe.
int	integer_graph_rem_vertex (integer_graph_t *graph, int vertex)
	Suppression d'un sommet dans un graphe.
int	integer_graph_rem_edge (integer_graph_t *graph, int vertex1, int vertex2)
	Suppression d'un arc dans un graphe.
integer_list_t *	integer_graph_adjlist (integer_graph_t *graph, int vertex)
	Accesseur de la liste des voisins d'un sommet.
bool	integer_graph_is_adjacent (const integer_graph_t *graph, int vertex1, int vertex2)
	Prédicat indiquant si deux sommets sont liés par un arc.
int	integer_graph_vcount (integer_graph_t *graph)
	Accesseur du nombre de sommets du graphe.
int	integer_graph_ecount (integer_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

integer_adjlist_elmt_t

typedef struct integer_adjlist_elmt_ integer_adjlist_elmt_t

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

integer_adjlist_t

typedef struct integer_adjlist_ integer_adjlist_t

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

integer_graph_t

typedef struct integer_graph_ integer_graph_t

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

integer_vertexcolor_t

typedef enum integer_vertexcolor_ integer_vertexcolor_t

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

Documentation du type de l'énumération

integer_vertexcolor_

enum integer_vertexcolor_

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

Valeurs énumérées
integer_white	drapeau pour indiquer un sommet non considéré
integer_gray	drapeau pour indiquer un sommet en cours de traitement
integer_black	drapeau pour indiquer un sommet qui a été traité

Documentation des fonctions

integer_graph_adjlist()

integer_list_t * integer_graph_adjlist	(	integer_graph_t *	graph,
		int	vertex )

Accesseur de la liste des voisins d'un sommet.

Paramètres

graph	est un pointeur vers la structure de données de graphe integer_graph_t
vertex	nom du sommet pour lequel la liste des voisins est voulue

Renvoie

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

integer_graph_destroy()

void integer_graph_destroy

(

integer_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 integer_graph_t

integer_graph_ecount()

int integer_graph_ecount

(

integer_graph_t *

graph

)

Accesseur du nombre d'arcs du graphe.

Paramètres

graph

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

Renvoie

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

integer_graph_init()

void integer_graph_init

(

integer_graph_t *

graph

)

Initialisation d'un nouveau graphe.

Met à zéro du nombre de sommets, du nombre d'arcs et initialisation de la liste d'adjacence

Paramètres

graph

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

integer_graph_ins_edge()

int integer_graph_ins_edge	(	integer_graph_t *	graph,
		int	vertex1,
		int	vertex2,
		double	weight )

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 vertex1 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 integer_graph_t
vertex1	nom de la source de l'arc, représenté par une valeur de type int
vertex2	nom de la destination de l'arc, représenté par une valeur de type int
weight	la valeur de la pondération de l'arc (0.0 si arc non pondéré)

Renvoie

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

integer_graph_ins_vertex()

int integer_graph_ins_vertex	(	integer_graph_t *	graph,
		int	vertex )

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 integer_graph_t
vertex	nom du nouveau noeud, représenté par une valeur de type int, à ajouter

Renvoie

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

integer_graph_is_adjacent()

bool integer_graph_is_adjacent	(	const integer_graph_t *	graph,
		int	vertex1,
		int	vertex2 )

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 integer_graph_t
vertex1	nom du sommet source
vertex2	nom du sommet destination

Renvoie

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

integer_graph_rem_edge()

int integer_graph_rem_edge	(	integer_graph_t *	graph,
		int	vertex1,
		int	vertex2 )

Suppression d'un arc dans un graphe.

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

Paramètres

graph	est un pointeur vers la structure de données de graphe integer_graph_t
vertex1	nom de la source de l'arc, représenté par une valeur de type int
vertex2	nom de la destination de l'arc, représenté par une valeur de type int

Renvoie

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

integer_graph_rem_vertex()

int integer_graph_rem_vertex	(	integer_graph_t *	graph,
		int	vertex )

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 integer_graph_t
vertex	nom du sommet à supprimer

Renvoie

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

integer_graph_vcount()

int integer_graph_vcount

(

integer_graph_t *

graph

)

Accesseur du nombre de sommets du graphe.

Paramètres

graph

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

Renvoie

valeur entière donnant le nombre de sommets du graphe