Référence du fichier integer_graphalg.h

Liste d'algorithmes sur les graphes. Plus de détails...

#include "graph.h"
#include "list.h"

Aller au code source de ce fichier.

Structures de données
struct	we_t
	Type de données internes pour l'algorithme de de forêt couvrante de poids minimal. Cette structure de données est utilisée dans le résultat produit par l'algorithme de Kruskal. Il décrit les différentes arêtes composants l'arbre couvrant. Plus de détails...
struct	ed_t
	Type de données internes pour l'algorithme de de plus courts chemins. Cette structure de données est utilisée dans le résultat produit par l'algorithme de Kruskal. Il décrit les différents points de passage pour atteindre un sommet. Plus de détails...

Fonctions
int	integer_dfs (integer_graph_t *graph, int start, integer_list_t *ordered)
	Parcours en profondeur d'abord d'un graphe dont les noeuds contiennent des valeurs de type int
int	integer_dfs_all (integer_graph_t *graph, integer_list_t *ordered)
	Parcours en profondeur d'abord d'un graphe dont les noeuds contiennent des valeurs de type int
int	integer_bfs (integer_graph_t *graph, int start, integer_list_t *ordered)
	Parcours en largeur d'abord d'un graphe dont les noeuds contiennent des valeurs de type int
int	integer_bfs_all (integer_graph_t *graph, integer_list_t *ordered)
	Parcours en largeur d'abord d'un graphe dont les noeuds contiennent des valeurs de type int
int	integer_ts (integer_graph_t *graph, integer_list_t *ordered)
	Effectue un tri topologique d'un graphe dont les noeuds contiennent des valeurs de type int
int	integer_mst (integer_graph_t *graph, generic_list_t **span)
	Calcul de l'arbre couvrant de poids minimal d'un graphe dont les noeuds contiennent des valeurs de type int
int	integer_shortest (integer_graph_t *graph, int start, generic_list_t **paths)
	Calcul du plus court chemin d'un sommet source vers tous les autres avec un cout minimal d'un graphe dont les noeuds contiennent des valeurs de type int
int	integer_maxflow (integer_graph_t *graph, int source, int target, double ***localflows, double *flow)
	Calcul du flot maximal d'un sommet source vers un sommet destination d'un graphe dont les noeuds contiennent des valeurs de type int

Description détaillée

Liste d'algorithmes sur les graphes.

1. Parcours de graphes en profondeur d'abord en deux versions
2. Parcours de graphes en largeur d'abord en deux versions
3. Algorithme de tri topologique
4. Algorithme de Kruskal: arbre couvrant de point minimal
5. Algorithme de Dijkstra: plus court chemin pour un graphe à pondération positive
6. Algorithme de Edmonds-Karp: flot maximum

Documentation des fonctions

integer_bfs()

int integer_bfs	(	integer_graph_t *	graph,
		int	start,
		integer_list_t *	ordered )

Parcours en largeur d'abord d'un graphe dont les noeuds contiennent des valeurs de type int

Parcours d'un graphe en largeur à partir d'un sommet donné

Paramètres

graph	un pointeur vers une structure de données représentant un graphe (liste d'adjacence) integer_graph_t
start	sommet de départ pour le parcours en largeur d'abord
ordered	liste des sommets parcourus dans l'ordre du parcours en largeur (Remarque cette liste peut ne pas contenir tous les sommets du graphe)

Renvoie

valeur entière indiquant si tout s'est bien passé (0 pour ok)

integer_bfs_all()

int integer_bfs_all	(	integer_graph_t *	graph,
		integer_list_t *	ordered )

Parcours en largeur d'abord d'un graphe dont les noeuds contiennent des valeurs de type int

Parcours d'un graphe en largeur à partir du début de la liste d'adjacence. Pour chaque sommet on éxécute un parcours en largeur d'abord.

Paramètres

graph	un pointeur vers une structure de données représentant un graphe (liste d'adjacence) integer_graph_t
ordered	liste des sommets parcourus dans l'ordre du parcours en largeur.

Renvoie

valeur entière indiquant si tout s'est bien passé (0 pour ok)

integer_dfs()

int integer_dfs	(	integer_graph_t *	graph,
		int	start,
		integer_list_t *	ordered )

Parcours en profondeur d'abord d'un graphe dont les noeuds contiennent des valeurs de type int

Parcours d'un graphe en profondeur à partir d'un sommet donné

Paramètres

graph	un pointeur vers une structure de données représentant un graphe (liste d'adjacence) integer_graph_t
start	sommet de départ pour le parcours en profondeur d'abord
ordered	liste des sommets parcourus dans l'ordre du parcours en profondeur (Remarque cette liste peut ne pas contenir tous les sommets du graphe)

Renvoie

valeur entière indiquant si tout s'est bien passé (0 pour ok)

integer_dfs_all()

int integer_dfs_all	(	integer_graph_t *	graph,
		integer_list_t *	ordered )

Parcours en profondeur d'abord d'un graphe dont les noeuds contiennent des valeurs de type int

Parcours d'un graphe en profondeur à partir du début de la liste d'adjacence. Pour chaque sommet on éxécute un parcours en profondeur.

Paramètres

graph	un pointeur vers une structure de données représentant un graphe (liste d'adjacence) integer_graph_t
ordered	liste des sommets parcourus dans l'ordre du parcours en profondeur.

Renvoie

valeur entière indiquant si tout s'est bien passé (0 pour ok)

integer_maxflow()

int integer_maxflow	(	integer_graph_t *	graph,
		int	source,
		int	target,
		double ***	localflows,
		double *	flow )

Calcul du flot maximal d'un sommet source vers un sommet destination d'un graphe dont les noeuds contiennent des valeurs de type int

Application de l'algorithme de Edmonds-Karp. Dans cet algorithme l'allocation mémoire de la matrice localflows est réalisée en interne d'où le triple pointeur sur la matrice localflows.

Paramètres

graph	un pointeur vers une structure de données représentant un graphe (liste d'adjacence) integer_graph_t
source	sommet point de départ
target	sommet destination
localflows	pointeur vers la matrice des flots entre chaque couple de sommets contribuant au flot maximal
flow	valeur du flot maximal entre la source et la destination

Renvoie

valeur entière indiquant si tout s'est bien passé (0 pour ok)

integer_mst()

int integer_mst	(	integer_graph_t *	graph,
		generic_list_t **	span )

Calcul de l'arbre couvrant de poids minimal d'un graphe dont les noeuds contiennent des valeurs de type int

Application de l'algorithme de Kruskal. Dans cet algorithme l'allocation mémoire de la liste span est réalisée en interne d'où le double pointeur sur la liste span.

Paramètres

graph	un pointeur vers une structure de données représentant un graphe (liste d'adjacence) integer_graph_t
span	liste des arêtes représentant l'arbre couvrant de poids minimal.

Renvoie

valeur entière indiquant si tout s'est bien passé (0 pour ok)

integer_shortest()

int integer_shortest	(	integer_graph_t *	graph,
		int	start,
		generic_list_t **	paths )

Calcul du plus court chemin d'un sommet source vers tous les autres avec un cout minimal d'un graphe dont les noeuds contiennent des valeurs de type int

Application de l'algorithme de Dijkstra donc graphe dirigé avec poids positifs. Dans cet algorithme l'allocation mémoire de la liste paths est réalisée en interne d'où le double pointeur sur la liste paths.

Paramètres

graph	un pointeur vers une structure de données représentant un graphe (liste d'adjacence) integer_graph_t
start	sommet de départ pour calculer les plus courts chemins
paths	liste des arêtes composants les chemins les plus courts depuis le sommet start vers les autres sommets.

Renvoie

valeur entière indiquant si tout s'est bien passé (0 pour ok)

integer_ts()

int integer_ts	(	integer_graph_t *	graph,
		integer_list_t *	ordered )

Effectue un tri topologique d'un graphe dont les noeuds contiennent des valeurs de type int

Parcours d'un graphe à partir du début de la liste d'adjacence pour réaliser un tri topologique.

Paramètres

graph	un pointeur vers une structure de données représentant un graphe (liste d'adjacence) integer_graph_t
ordered	liste des sommets parcourus dans l'ordre du tri topologique

Renvoie

valeur entière indiquant si tout s'est bien passé (0 pour ok)