Changeset 1584:cf4bc8d477f4 in lemon0.x
 Timestamp:
 07/22/05 18:57:07 (15 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2087
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

demo/kruskal_demo.cc
r1583 r1584 61 61 Edge e10 = g.addEdge(v4, t); 62 62 63 //Make the input and outputfor the kruskal.63 //Make the input for the kruskal. 64 64 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 65 82 typedef ListGraph::EdgeMap<bool> EBoolMap; 66 67 ECostMap edge_cost_map(g, 2);68 83 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 (nonuniform 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);86 84 87 85 vector<Edge> tree_edge_vec; 88 86 89 //Test with non uniform costs and inserter.90 std::cout << "The weight of the minimum spanning tree with nonuniform costs is " <<91 kruskal(g, edge_cost_map_2, std::back_inserter(tree_edge_vec)) <<std::endl;92 87 93 //The vector for the edges of the output tree. 94 tree_edge_vec.clear(); 88 //Kruskal Algorithm. 95 89 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; 97 93 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; 100 97 101 98 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 102 129 return 0; 103 130 } 
doc/quicktour.dox
r1580 r1584 144 144 length of wires then you might be looking for a <b>minimum spanning 145 145 tree</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): 146 algorithm: the function \ref lemon::kruskal "LEMON Kruskal " does this 147 job for you. 148 149 First make a graph \c g and a cost map \c 150 edge_cost_map, then make a bool edgemap \c tree_map or a vector \c 151 tree_edge_vec for the algorithm output. After calling the function it 152 gives back the weight of the minimum spanning tree and the \c tree_map or 153 the \c tree_edge_vec contains the edges of the tree. 154 155 If you want to store the edges in a bool edgemap, then use the 156 function as follows: 149 157 150 158 \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 nonuniform, 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 162 And if you rather use a vector instead of a bool map: 163 164 \skip Kruskal with vector; 165 \until std::endl 168 166 169 167 See the whole program in \ref kruskal_demo.cc.
Note: See TracChangeset
for help on using the changeset viewer.