home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / incl / graph_al.h < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  5.8 KB  |  191 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  graph_alg.h
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef GRAPHALGH
  17. #define GRAPHALGH
  18.  
  19. #include <LEDA/graph.h>
  20. #include <LEDA/ugraph.h>
  21.  
  22.  
  23. //-----------------------------------------------------------------------------
  24. // Predefined:
  25. //-----------------------------------------------------------------------------
  26.                 
  27. declare(node_array,int)
  28. declare(edge_array,int)
  29. declare(node_array,edge)
  30. declare(edge_array,edge)
  31.  
  32. declare(node_matrix,int)
  33.  
  34. typedef node_array(int)  node_array(bool);
  35. typedef edge_array(int)  edge_array(bool);
  36. typedef node_matrix(int) node_matrix(bool);
  37.  
  38.  
  39.  
  40. //-----------------------------------------------------------------------------
  41. // basic graph algorithms:
  42. //-----------------------------------------------------------------------------
  43.  
  44. bool        compute_correspondence(const graph&, edge_array(edge)&);
  45.  
  46. bool        TOPSORT(const graph& G, node_array(int)& ord);
  47.  
  48. bool        TOPSORT1(graph& G);
  49.  
  50. list(node)  DFS(const graph& G, node s, node_array(bool)& reached) ;
  51.  
  52. list(node)  BFS(const graph& G, node s, node_array(int)& dist);
  53.  
  54. list(edge)  DFS_NUM(const graph& G, node_array(int)& dfsnum, 
  55.                                     node_array(int)& compnum);
  56.  
  57. int         COMPONENTS(const ugraph& G, node_array(int)& compnum);
  58.  
  59. int         COMPONENTS1(const ugraph& G, node_array(int)& compnum);
  60.  
  61. int         STRONG_COMPONENTS(const graph& G, node_array(int)& compnum);
  62.  
  63. int         STRONG_COMPONENTS1(const graph& G, node_array(int)& compnum);
  64.  
  65. int         BICONNECTED_COMPONENTS(const ugraph& G, node_array(int)& compnum);
  66.  
  67. void        acyclic_transitive_closure(graph&);
  68.  
  69. graph       TRANSITIVE_CLOSURE(const graph& G);
  70.  
  71.  
  72.  
  73. //-----------------------------------------------------------------------------
  74. // shortest paths:
  75. //-----------------------------------------------------------------------------
  76.  
  77. void DIJKSTRA(const graph& G, node s, const edge_array(int)& cost, 
  78.                                             node_array(int)& dist, 
  79.                                             node_array(edge)& pred);
  80.  
  81. bool BELLMAN_FORD(const graph& G, node s, const edge_array(int)& cost,
  82.                                                 node_array(int)& dist,
  83.                                                 node_array(edge)& pred);
  84.  
  85. void ALL_PAIRS_SHORTEST_PATHS(graph& G, const edge_array(int)&  cost,
  86.                                               node_matrix(int)& dist);
  87.  
  88.  
  89.  
  90.  
  91. //-----------------------------------------------------------------------------
  92. // maximum flow:
  93. //-----------------------------------------------------------------------------
  94.  
  95.  
  96. int  MAX_FLOW(graph& G, node s, node t, const edge_array(int)& cap,
  97.                                               edge_array(int)& flow);
  98.  
  99.  
  100. //-----------------------------------------------------------------------------
  101. // matchings:
  102. //-----------------------------------------------------------------------------
  103.  
  104. // Edmond's algorithm
  105.  
  106. list(edge) MAX_CARD_MATCHING(graph& G, bool report_blossoms = false);    
  107.  
  108.  
  109. // Hopcroft/Karp
  110.  
  111. list(edge) MAX_CARD_BIPARTITE_MATCHING(graph& G, const list(node)& A, 
  112.                                                  const list(node)& B);
  113.  
  114.  
  115.  
  116. list(edge) MAX_WEIGHT_BIPARTITE_MATCHING(graph& G, const list(node)& A, 
  117.                                                    const list(node)& B,
  118.                                                    const edge_array(int)& weight);
  119.  
  120.  
  121.  
  122.  
  123. //-----------------------------------------------------------------------------
  124. // spanning trees:
  125. //-----------------------------------------------------------------------------
  126.  
  127. list(edge) SPANNING_TREE(const graph& G);
  128.  
  129. list(edge) MIN_SPANNING_TREE(const graph& G, const edge_array(int)& cost);
  130.  
  131.  
  132.  
  133. //-----------------------------------------------------------------------------
  134. // planar graphs
  135. //-----------------------------------------------------------------------------
  136.  
  137. int PLANAR( graph&) ;
  138.  
  139. list(edge) TRIANGULATE_PLANAR_MAP(graph&);
  140.  
  141. int STRAIGHT_LINE_EMBEDDING(graph& G,node_array(int)& xcoord,
  142.                                      node_array(int)& ycoord);
  143.  
  144.  
  145.  
  146. //-----------------------------------------------------------------------------
  147. // "REAL" versions 
  148. //-----------------------------------------------------------------------------
  149.  
  150.  
  151. #ifndef NO_REAL_GRAPH_ALG
  152.  
  153.  
  154. declare(node_array,real)
  155. declare(edge_array,real)
  156. declare(node_matrix,real)
  157.  
  158. void DIJKSTRA(const graph& G, node s, const edge_array(real)& cost, 
  159.                                             node_array(real)& dist, 
  160.                                             node_array(edge)& pred);
  161.  
  162. bool BELLMAN_FORD(const graph& G, node s, const edge_array(real)& cost,
  163.                                                 node_array(real)& dist,
  164.                                                 node_array(edge)& pred);
  165.  
  166.  
  167. void ALL_PAIRS_SHORTEST_PATHS(graph& G, const edge_array(real)&  cost,
  168.                                               node_matrix(real)& dist);
  169.  
  170.  
  171. real MAX_FLOW(graph& G, node s, node t, const edge_array(real)& cap,
  172.                                               edge_array(real)& flow);
  173.  
  174.  
  175. list(edge) MAX_WEIGHT_BIPARTITE_MATCHING(graph& G, const list(node)& A, 
  176.                                                    const list(node)& B,
  177.                                                    const edge_array(real)& weight);
  178.  
  179.  
  180. int STRAIGHT_LINE_EMBEDDING(graph& G,node_array(real)& xcoord,
  181.                                      node_array(real)& ycoord);
  182.  
  183.  
  184. list(edge) MIN_SPANNING_TREE(const graph& G, const edge_array(real)& cost);
  185.  
  186.  
  187. #endif /* ifndef NO_REAL_GRAPH_ALG */
  188.  
  189.  
  190. #endif
  191.