home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / graph_al / _spannin.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  2.8 KB  |  123 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _spanning.c
  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.  
  17. /*******************************************************************************
  18. *                                                                              *
  19. *  SPANNING_TREE  (spanning tree)                                              *
  20. *                                                                              *
  21. *******************************************************************************/
  22.  
  23.  
  24.  
  25. #include <LEDA/graph_alg.h>
  26.  
  27. #include <LEDA/node_partition.h>
  28.  
  29.  
  30. list(edge) SPANNING_TREE(const graph& G)
  31. { node v,w;
  32.   edge e;
  33.   list(edge) EL;
  34.   node_partition P(G);
  35.  
  36.   forall_edges(e,G)
  37.      { v = source(e);
  38.        w = target(e);
  39.        if (! P.same_block(v,w))
  40.         { EL.append(e);
  41.           P.union_blocks(v,w);
  42.          }
  43.       }
  44.  
  45.   return EL;
  46. }
  47.  
  48.  
  49. /*******************************************************************************
  50. *                                                                              *
  51. *  LEDA 1.0    (graph algorithms)                                              *
  52. *                                                                              *
  53. *  MIN_SPANNING_TREE   (minimum spanning tree)                                 *
  54. *                                                                              *
  55. *******************************************************************************/
  56.  
  57. static edge_array(int) edge_cost;
  58.  
  59. static int CMP_EDGES(edge& e1, edge& e2) 
  60. { return (edge_cost[e1] - edge_cost[e2]); }
  61.  
  62. list(edge) MIN_SPANNING_TREE(const graph& G, const edge_array(int)& cost)
  63. { node v,w;
  64.   edge e;
  65.   list(edge) EL;
  66.   node_partition P(G);
  67.  
  68.   list(edge) OEL = G.all_edges();
  69.  
  70.   edge_cost = cost;
  71.  
  72.   OEL.sort(CMP_EDGES);
  73.  
  74.   forall(e,OEL)
  75.      { v = source(e);
  76.        w = target(e);
  77.        if (! P.same_block(v,w))
  78.         { EL.append(e);
  79.           P.union_blocks(v,w);
  80.          }
  81.       }
  82.  
  83.   return EL;
  84. }
  85.  
  86.  
  87.  
  88.  
  89. #ifndef NO_REAL_GRAPH_ALG
  90.  
  91.  
  92. static edge_array(real) edge_cost1;
  93.  
  94. static int CMP_EDGES1(edge& e1, edge& e2) 
  95. { return (edge_cost[e1] - edge_cost[e2]); }
  96.  
  97. list(edge) MIN_SPANNING_TREE(const graph& G, const edge_array(real)& cost)
  98. { node v,w;
  99.   edge e;
  100.   list(edge) EL;
  101.   node_partition P(G);
  102.  
  103.   list(edge) OEL = G.all_edges();
  104.  
  105.   edge_cost1 = cost;
  106.  
  107.   OEL.sort(CMP_EDGES1);
  108.  
  109.   forall(e,OEL)
  110.      { v = source(e);
  111.        w = target(e);
  112.        if (! P.same_block(v,w))
  113.         { EL.append(e);
  114.           P.union_blocks(v,w);
  115.          }
  116.       }
  117.  
  118.   return EL;
  119. }
  120.  
  121.  
  122. #endif
  123.