COIN-OR::LEMON - Graph Library

Changeset 1584:cf4bc8d477f4 in lemon-0.x for demo


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

File:
1 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}
Note: See TracChangeset for help on using the changeset viewer.