1.1 --- a/demo/kruskal_demo.cc Fri Jul 22 15:15:29 2005 +0000
1.2 +++ b/demo/kruskal_demo.cc Fri Jul 22 16:57:07 2005 +0000
1.3 @@ -60,44 +60,71 @@
1.4 Edge e9 = g.addEdge(v3, t);
1.5 Edge e10 = g.addEdge(v4, t);
1.6
1.7 - //Make the input and output for the kruskal.
1.8 + //Make the input for the kruskal.
1.9 typedef ListGraph::EdgeMap<int> ECostMap;
1.10 + ECostMap edge_cost_map(g);
1.11 +
1.12 + // Fill the edge_cost_map.
1.13 + edge_cost_map.set(e1, -10);
1.14 + edge_cost_map.set(e2, -9);
1.15 + edge_cost_map.set(e3, -8);
1.16 + edge_cost_map.set(e4, -7);
1.17 + edge_cost_map.set(e5, -6);
1.18 + edge_cost_map.set(e6, -5);
1.19 + edge_cost_map.set(e7, -4);
1.20 + edge_cost_map.set(e8, -3);
1.21 + edge_cost_map.set(e9, -2);
1.22 + edge_cost_map.set(e10, -1);
1.23 +
1.24 + // Make the map or the vector, which will contain the edges of the minimum
1.25 + // spanning tree.
1.26 +
1.27 typedef ListGraph::EdgeMap<bool> EBoolMap;
1.28 -
1.29 - ECostMap edge_cost_map(g, 2);
1.30 EBoolMap tree_map(g);
1.31
1.32 - // Kruskal.
1.33 - std::cout << "The weight of the minimum spanning tree by using Kruskal algorithm is "
1.34 - << kruskal(g, ConstMap<ListGraph::Edge,int>(2), tree_map)<<std::endl;
1.35 -
1.36 - //Make another input (non-uniform costs) for the kruskal.
1.37 - ECostMap edge_cost_map_2(g);
1.38 - edge_cost_map_2.set(e1, -10);
1.39 - edge_cost_map_2.set(e2, -9);
1.40 - edge_cost_map_2.set(e3, -8);
1.41 - edge_cost_map_2.set(e4, -7);
1.42 - edge_cost_map_2.set(e5, -6);
1.43 - edge_cost_map_2.set(e6, -5);
1.44 - edge_cost_map_2.set(e7, -4);
1.45 - edge_cost_map_2.set(e8, -3);
1.46 - edge_cost_map_2.set(e9, -2);
1.47 - edge_cost_map_2.set(e10, -1);
1.48 -
1.49 vector<Edge> tree_edge_vec;
1.50
1.51 - //Test with non uniform costs and inserter.
1.52 - std::cout << "The weight of the minimum spanning tree with non-uniform costs is " <<
1.53 - kruskal(g, edge_cost_map_2, std::back_inserter(tree_edge_vec)) <<std::endl;
1.54
1.55 - //The vector for the edges of the output tree.
1.56 - tree_edge_vec.clear();
1.57 + //Kruskal Algorithm.
1.58
1.59 - //Test with makeKruskalMapInput and makeKruskalSequenceOutput.
1.60 + //Input: a graph (g); a costmap of the graph (edge_cost_map); a
1.61 + //boolmap (tree_map) or a vector (tree_edge_vec) to store the edges
1.62 + //of the output tree;
1.63
1.64 + //Output: it gives back the value of the minimum spanning tree, and
1.65 + //set true for the edges of the tree in the edgemap tree_map or
1.66 + //store the edges of the tree in the vector tree_edge_vec;
1.67 +
1.68 +
1.69 + // Kruskal with boolmap;
1.70 + std::cout << "The weight of the minimum spanning tree is " <<
1.71 + kruskal(g, edge_cost_map, tree_map)<<std::endl;
1.72 +
1.73 + int k=0;
1.74 + std::cout << "The edges of the tree:" ;
1.75 + for(EdgeIt i(g); i!=INVALID; ++i){
1.76 +
1.77 + if (tree_map[i]) {
1.78 + std::cout << g.id(i) <<";";
1.79 + ++k;
1.80 + }
1.81 + }
1.82 + std::cout << std::endl;
1.83 + std::cout << "The size of the tree is: "<< k << std::endl;
1.84 +
1.85 +
1.86 + // Kruskal with vector;
1.87 std::cout << "The weight of the minimum spanning tree again is " <<
1.88 - kruskal(g,makeKruskalMapInput(g,edge_cost_map_2),makeKruskalSequenceOutput(std::back_inserter(tree_edge_vec)))<< std::endl;
1.89 + kruskal(g, edge_cost_map, std::back_inserter(tree_edge_vec)) <<std::endl;
1.90
1.91
1.92 +
1.93 + std::cout << "The edges of the tree again: " ;
1.94 + for(int i=tree_edge_vec.size()-1; i>=0; i--)
1.95 + std::cout << g.id(tree_edge_vec[i]) << ";" ;
1.96 + std::cout << std::endl;
1.97 + std::cout << "The size of the tree again is: "<< tree_edge_vec.size()<< std::endl;
1.98 +
1.99 +
1.100 return 0;
1.101 }
2.1 --- a/doc/quicktour.dox Fri Jul 22 15:15:29 2005 +0000
2.2 +++ b/doc/quicktour.dox Fri Jul 22 16:57:07 2005 +0000
2.3 @@ -143,28 +143,26 @@
2.4 <li> If you want to design a network and want to minimize the total
2.5 length of wires then you might be looking for a <b>minimum spanning
2.6 tree</b> in an undirected graph. This can be found using the Kruskal
2.7 -algorithm: the function \ref lemon::kruskal "LEMON Kruskal " does
2.8 -this job for you. After we had a graph \c g and a cost map \c
2.9 -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):
2.10 +algorithm: the function \ref lemon::kruskal "LEMON Kruskal " does this
2.11 +job for you.
2.12 +
2.13 +First make a graph \c g and a cost map \c
2.14 +edge_cost_map, then make a bool edgemap \c tree_map or a vector \c
2.15 +tree_edge_vec for the algorithm output. After calling the function it
2.16 +gives back the weight of the minimum spanning tree and the \c tree_map or
2.17 +the \c tree_edge_vec contains the edges of the tree.
2.18 +
2.19 +If you want to store the edges in a bool edgemap, then use the
2.20 +function as follows:
2.21
2.22 \dontinclude kruskal_demo.cc
2.23 -\skip std::cout
2.24 -\until kruskal
2.25 +\skip Kruskal with boolmap;
2.26 +\until std::endl
2.27
2.28 -In the variable \c tree_map the function gives back an edge bool map, which contains the edges of the found tree.
2.29 +And if you rather use a vector instead of a bool map:
2.30
2.31 -If the costs are non-uniform, for example the cost is given by \c
2.32 -edge_cost_map_2 , or the edges of the tree have to be given in a
2.33 -vector, then we can give to the kruskal a vector \c tree_edge_vec , instead of
2.34 -an edge bool map:
2.35 -
2.36 -\skip edge_cost_map_2
2.37 -\until edge_cost_map_2, std::back_inserter
2.38 -
2.39 -And finally the next fragment shows how to use the functions \c makeKruskalMapInput and \c makeKruskalSequenceOutPut:
2.40 -
2.41 -\skip makeKruskalSequenceOutput
2.42 -\until tree_edge_vec
2.43 +\skip Kruskal with vector;
2.44 +\until std::endl
2.45
2.46 See the whole program in \ref kruskal_demo.cc.
2.47