COIN-OR::LEMON - Graph Library

Changeset 1584:cf4bc8d477f4 in lemon-0.x


Ignore:
Timestamp:
07/22/05 18:57:07 (14 years ago)
Author:
zsuzska
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2087
Message:

corrections

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • demo/kruskal_demo.cc

    r1583 r1584  
    6161  Edge e10 = g.addEdge(v4, t);
    6262
    63   //Make the input and output for the kruskal.
     63  //Make the input for the kruskal.
    6464  typedef ListGraph::EdgeMap<int> ECostMap;
     65  ECostMap edge_cost_map(g);
     66
     67  // Fill the edge_cost_map.
     68  edge_cost_map.set(e1, -10);
     69  edge_cost_map.set(e2, -9);
     70  edge_cost_map.set(e3, -8);
     71  edge_cost_map.set(e4, -7);
     72  edge_cost_map.set(e5, -6);
     73  edge_cost_map.set(e6, -5);
     74  edge_cost_map.set(e7, -4);
     75  edge_cost_map.set(e8, -3);
     76  edge_cost_map.set(e9, -2);
     77  edge_cost_map.set(e10, -1);
     78
     79  // Make the map or the vector, which will contain the edges of the minimum
     80  // spanning tree.
     81
    6582  typedef ListGraph::EdgeMap<bool> EBoolMap;
    66 
    67   ECostMap edge_cost_map(g, 2);
    6883  EBoolMap tree_map(g);
    69 
    70   // Kruskal.
    71   std::cout << "The weight of the minimum spanning tree by using Kruskal algorithm is "
    72             << kruskal(g, ConstMap<ListGraph::Edge,int>(2), tree_map)<<std::endl;
    73 
    74   //Make another input (non-uniform costs) for the kruskal.
    75   ECostMap edge_cost_map_2(g);
    76   edge_cost_map_2.set(e1, -10);
    77   edge_cost_map_2.set(e2, -9);
    78   edge_cost_map_2.set(e3, -8);
    79   edge_cost_map_2.set(e4, -7);
    80   edge_cost_map_2.set(e5, -6);
    81   edge_cost_map_2.set(e6, -5);
    82   edge_cost_map_2.set(e7, -4);
    83   edge_cost_map_2.set(e8, -3);
    84   edge_cost_map_2.set(e9, -2);
    85   edge_cost_map_2.set(e10, -1);
    8684
    8785  vector<Edge> tree_edge_vec;
    8886
    89   //Test with non uniform costs and inserter.
    90   std::cout << "The weight of the minimum spanning tree with non-uniform costs is " <<
    91     kruskal(g, edge_cost_map_2, std::back_inserter(tree_edge_vec)) <<std::endl;
    9287
    93   //The vector for the edges of the output tree.
    94   tree_edge_vec.clear();
     88  //Kruskal Algorithm. 
    9589
    96   //Test with makeKruskalMapInput and makeKruskalSequenceOutput.
     90  //Input: a graph (g); a costmap of the graph (edge_cost_map); a
     91  //boolmap (tree_map) or a vector (tree_edge_vec) to store the edges
     92  //of the output tree;
    9793
    98   std::cout << "The weight of the minimum spanning tree again is " <<
    99    kruskal(g,makeKruskalMapInput(g,edge_cost_map_2),makeKruskalSequenceOutput(std::back_inserter(tree_edge_vec)))<< std::endl;
     94  //Output: it gives back the value of the minimum spanning tree, and
     95  //set true for the edges of the tree in the edgemap tree_map or
     96  //store the edges of the tree in the vector tree_edge_vec;
    10097
    10198
     99  // Kruskal with boolmap;
     100  std::cout << "The weight of the minimum spanning tree is " <<
     101    kruskal(g, edge_cost_map, tree_map)<<std::endl;
     102
     103  int k=0;
     104  std::cout << "The edges of the tree:" ;
     105  for(EdgeIt i(g); i!=INVALID; ++i){
     106
     107    if (tree_map[i]) {
     108      std::cout << g.id(i) <<";";
     109      ++k;
     110    }
     111  }
     112  std::cout << std::endl;
     113  std::cout << "The size of the tree is: "<< k << std::endl;
     114
     115
     116  // Kruskal with vector;
     117  std::cout << "The weight of the minimum spanning tree again is " <<
     118    kruskal(g, edge_cost_map, std::back_inserter(tree_edge_vec)) <<std::endl;
     119
     120
     121
     122  std::cout << "The edges of the tree again: " ;
     123  for(int i=tree_edge_vec.size()-1; i>=0;  i--)
     124    std::cout << g.id(tree_edge_vec[i]) << ";" ;
     125  std::cout << std::endl;
     126  std::cout << "The size of the tree again is: "<< tree_edge_vec.size()<< std::endl;
     127
     128 
    102129  return 0;
    103130}
  • doc/quicktour.dox

    r1580 r1584  
    144144length of wires then you might be looking for a <b>minimum spanning
    145145tree</b> in an undirected graph. This can be found using the Kruskal
    146 algorithm: the function \ref lemon::kruskal "LEMON Kruskal " does
    147 this job for you.  After we had a graph \c g and a cost map \c
    148 edge_cost_map , the following code fragment shows an example how to get weight of the minmum spanning tree (in this first example the costs are uniform; this is of course not the case in real life applications):
     146algorithm: the function \ref lemon::kruskal "LEMON Kruskal " does this
     147job for you. 
     148
     149First make a graph \c g and a cost map \c
     150edge_cost_map, then make a bool edgemap \c tree_map or a vector \c
     151tree_edge_vec for the algorithm output. After calling the function it
     152gives back the weight of the minimum spanning tree and the \c tree_map or
     153the \c tree_edge_vec contains the edges of the tree.
     154
     155If you want to store the edges in a bool edgemap, then use the
     156function as follows:
    149157
    150158\dontinclude kruskal_demo.cc
    151 \skip std::cout
    152 \until kruskal
    153 
    154 In the variable \c tree_map the function gives back an edge bool map, which contains the edges of the found tree.
    155 
    156 If the costs are non-uniform, for example  the cost is given by \c
    157 edge_cost_map_2 , or the edges of the tree  have to be given in a
    158 vector, then we can give to the kruskal a vector \c tree_edge_vec , instead of
    159 an edge bool map:
    160 
    161 \skip edge_cost_map_2
    162 \until edge_cost_map_2, std::back_inserter
    163 
    164 And finally the next fragment shows how to use the functions \c makeKruskalMapInput and \c makeKruskalSequenceOutPut:
    165 
    166 \skip makeKruskalSequenceOutput
    167 \until tree_edge_vec
     159\skip Kruskal with boolmap;
     160\until  std::endl
     161
     162And if you rather use a vector instead of a bool map:
     163
     164\skip Kruskal with vector;
     165\until std::endl
    168166
    169167See the whole program in \ref kruskal_demo.cc.
Note: See TracChangeset for help on using the changeset viewer.