Changeset 1578:1d3a1bcbc874 in lemon0.x
 Timestamp:
 07/21/05 00:36:37 (15 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2079
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

demo/kruskal_demo.cc
r1435 r1578 1 /* * C++ * 2 * demo/kruskal_demo.cc  Part of LEMON, a generic C++ optimization library 3 * 4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 5 * (Egervary Research Group on Combinatorial Optimization, EGRES). 6 * 7 * Permission to use, modify and distribute this software is granted 8 * provided that this copyright notice appears in all copies. For 9 * precise terms see the accompanying LICENSE file. 10 * 11 * This software is provided "AS IS" with no warranty of any kind, 12 * express or implied, and with no claim as to its suitability for any 13 * purpose. 14 * 15 */ 16 17 ///\ingroup demos 18 ///\file 19 ///\brief Minimum weight spanning tree by Kruskal algorithm (demo). 20 /// 21 ///This demo program shows how to find a minimum weight spannin tree 22 ///of a graph by using the Kruskal algorithm. 23 1 24 #include <iostream> 2 25 #include <vector> … … 18 41 typedef ListGraph::EdgeIt EdgeIt; 19 42 20 ListGraph G; 43 ListGraph g; 44 //Make an example graph g. 45 Node s=g.addNode(); 46 Node v1=g.addNode(); 47 Node v2=g.addNode(); 48 Node v3=g.addNode(); 49 Node v4=g.addNode(); 50 Node t=g.addNode(); 51 52 Edge e1 = g.addEdge(s, v1); 53 Edge e2 = g.addEdge(s, v2); 54 Edge e3 = g.addEdge(v1, v2); 55 Edge e4 = g.addEdge(v2, v1); 56 Edge e5 = g.addEdge(v1, v3); 57 Edge e6 = g.addEdge(v3, v2); 58 Edge e7 = g.addEdge(v2, v4); 59 Edge e8 = g.addEdge(v4, v3); 60 Edge e9 = g.addEdge(v3, t); 61 Edge e10 = g.addEdge(v4, t); 21 62 22 Node s=G.addNode(); 23 Node v1=G.addNode(); 24 Node v2=G.addNode(); 25 Node v3=G.addNode(); 26 Node v4=G.addNode(); 27 Node t=G.addNode(); 28 29 Edge e1 = G.addEdge(s, v1); 30 Edge e2 = G.addEdge(s, v2); 31 Edge e3 = G.addEdge(v1, v2); 32 Edge e4 = G.addEdge(v2, v1); 33 Edge e5 = G.addEdge(v1, v3); 34 Edge e6 = G.addEdge(v3, v2); 35 Edge e7 = G.addEdge(v2, v4); 36 Edge e8 = G.addEdge(v4, v3); 37 Edge e9 = G.addEdge(v3, t); 38 Edge e10 = G.addEdge(v4, t); 39 63 //Make the input and output for the kruskal. 40 64 typedef ListGraph::EdgeMap<int> ECostMap; 41 65 typedef ListGraph::EdgeMap<bool> EBoolMap; 42 66 43 ECostMap edge_cost_map(G, 2); 44 EBoolMap tree_map(G); 45 67 ECostMap edge_cost_map(g, 2); 68 EBoolMap tree_map(g); 46 69 47 //Test with const map. 48 std::cout << "The weight of the minimum spanning tree is " << kruskalEdgeMap(G, ConstMap<ListGraph::Edge,int>(2), tree_map)<<std::endl; 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; 49 73 50 /* 51 ==10, 52 "Total cost should be 10"); 53 //Test with a edge map (filled with uniform costs). 54 check(kruskalEdgeMap(G, edge_cost_map, tree_map)==10, 55 "Total cost should be 10"); 56 57 edge_cost_map.set(e1, 10); 58 edge_cost_map.set(e2, 9); 59 edge_cost_map.set(e3, 8); 60 edge_cost_map.set(e4, 7); 61 edge_cost_map.set(e5, 6); 62 edge_cost_map.set(e6, 5); 63 edge_cost_map.set(e7, 4); 64 edge_cost_map.set(e8, 3); 65 edge_cost_map.set(e9, 2); 66 edge_cost_map.set(e10, 1); 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); 67 86 68 87 vector<Edge> tree_edge_vec; 69 88 70 //Test with a edge map and inserter. 71 check(kruskalEdgeMap_IteratorOut(G, edge_cost_map, 72 back_inserter(tree_edge_vec)) 73 ==31, 74 "Total cost should be 31."); 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; 75 92 93 //The vector for the edges of the output tree. 76 94 tree_edge_vec.clear(); 77 95 78 //The above test could also be coded like this: 79 check(kruskal(G, 80 makeKruskalMapInput(G, edge_cost_map), 81 makeKruskalSequenceOutput(back_inserter(tree_edge_vec))) 82 ==31, 83 "Total cost should be 31."); 96 //Test with makeKruskalSequenceOutput and makeKruskalSequenceOutput. 84 97 85 check(tree_edge_vec.size()==5,"The tree should have 5 edges."); 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; 86 100 87 check(tree_edge_vec[0]==e1 && 88 tree_edge_vec[1]==e2 && 89 tree_edge_vec[2]==e5 && 90 tree_edge_vec[3]==e7 && 91 tree_edge_vec[4]==e9, 92 "Wrong tree."); 93 */ 101 94 102 return 0; 95 103 } 
doc/quicktour.dox
r1541 r1578 142 142 143 143 144 <li> If you want to design a network and want to minimize the total length 145 of wires then you might be looking for a <b>minimum spanning tree</b> in 146 an undirected graph. This can be found using the Kruskal algorithm: the 147 function \ref lemon::kruskal "LEMON Kruskal ..." does this job for you. 148 The following code fragment shows an example: 149 150 Ide Zsuzska fog irni! 144 <li> If you want to design a network and want to minimize the total 145 length of wires then you might be looking for a <b>minimum spanning 146 tree</b> in an undirected graph. This can be found using the Kruskal 147 algorithm: the function \ref lemon::kruskal "LEMON Kruskal " does 148 this job for you. After we had a graph \c g and a cost map \c 149 edge_cost_map , the following code fragment shows an example how to get weight of the minmum spanning tree, if the costs are uniform: 150 151 \dontinclude kruskal_demo.cc 152 \skip std::cout 153 \until kruskal 154 155 It gives back a edge bool map, which contains the edges of the tree. 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 are 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 168 169 See the whole program in \ref kruskal_demo.cc. 170 171 151 172 152 173 <li>Many problems in network optimization can be formalized by means
Note: See TracChangeset
for help on using the changeset viewer.