libin103 1.4
Bibliothèque de structures de données en C
|
Liste d'algorithmes sur les graphes. Plus de détails...
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 | |
Liste d'algorithmes sur les graphes.
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é
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) |
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.
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. |
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é
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) |
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.
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. |
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.
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 |
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.
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. |
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.
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. |
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.
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 |