libin103 1.4
Bibliothèque de structures de données en C
Chargement...
Recherche...
Aucune correspondance
Structures de données | Fonctions
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
graphun pointeur vers une structure de données représentant un graphe (liste d'adjacence) integer_graph_t
startsommet de départ pour le parcours en largeur d'abord
orderedliste 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
graphun pointeur vers une structure de données représentant un graphe (liste d'adjacence) integer_graph_t
orderedliste 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
graphun pointeur vers une structure de données représentant un graphe (liste d'adjacence) integer_graph_t
startsommet de départ pour le parcours en profondeur d'abord
orderedliste 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
graphun pointeur vers une structure de données représentant un graphe (liste d'adjacence) integer_graph_t
orderedliste 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
graphun pointeur vers une structure de données représentant un graphe (liste d'adjacence) integer_graph_t
sourcesommet point de départ
targetsommet destination
localflowspointeur vers la matrice des flots entre chaque couple de sommets contribuant au flot maximal
flowvaleur 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
graphun pointeur vers une structure de données représentant un graphe (liste d'adjacence) integer_graph_t
spanliste 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
graphun pointeur vers une structure de données représentant un graphe (liste d'adjacence) integer_graph_t
startsommet de départ pour calculer les plus courts chemins
pathsliste 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
graphun pointeur vers une structure de données représentant un graphe (liste d'adjacence) integer_graph_t
orderedliste des sommets parcourus dans l'ordre du tri topologique
Renvoie
valeur entière indiquant si tout s'est bien passé (0 pour ok)