integer_graphalg.h

Aller à la documentation de ce fichier.

 
/*****************************************************************************
*                                                                            *
*  ------------------------------ graphalg.h ------------------------------  *
*                                                                            *
*****************************************************************************/
 
#ifndef __integer_GRAPHALG_H__
#define __integer_GRAPHALG_H__
 
#include "graph.h"
#include "list.h"
 
/* For Kruskal's algorithm */
typedef struct {
  int source; 
  int destination; 
  double weight; 
} we_t;
 
/* For Dijkstra's algorithm */
typedef struct {
  int vertex; 
  double distance; 
  int parent; 
} ed_t;
 
 
/*****************************************************************************
*                                                                            *
*  --------------------------- Public Interface ---------------------------  *
*                                                                            *
*****************************************************************************/
 
/* Depth-first search */
int integer_dfs(integer_graph_t *graph,
           int start,
           integer_list_t *ordered);
 
int integer_dfs_all(integer_graph_t *graph,
           integer_list_t *ordered);
 
/* Breadth-first search */
int integer_bfs(integer_graph_t *graph,
           int start,
           integer_list_t *ordered);
 
int integer_bfs_all(integer_graph_t *graph,
           integer_list_t *ordered);
 
/* Toplogical sort */
int integer_ts (integer_graph_t* graph, integer_list_t* ordered);
 
/* Implementation of Kruskal's algorithm */
int integer_mst(integer_graph_t *graph, generic_list_t **span);
 
/* Implementation of Dijkstra's algorithm */
int integer_shortest(integer_graph_t *graph, int start, generic_list_t **paths);
 
/* Implementation of Edmonds-Karp's algorithm */
int integer_maxflow(integer_graph_t *graph, int source, int target,
           double*** localflows, double *flow);
 
#endif