Several changes. \n If new map is added to mapstorage it emits signal with the name of the new map. This was important, because from now on not only tha mapwin should be updated. \n Furthermore algobox gets a pointer to mapstorage instead of only the mapnames from it. This is important because without it it would be complicated to pass all of the required maps to algobox.
2 * demo/kruskal_demo.cc - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 ///\brief Minimum weight spanning tree by Kruskal algorithm (demo).
21 /// This demo program shows how to find a minimum weight spanning tree
22 /// in a graph by using the Kruskal algorithm.
24 /// \include kruskal_demo.cc
29 #include <lemon/maps.h>
30 #include <lemon/kruskal.h>
31 #include <lemon/list_graph.h>
35 using namespace lemon;
40 typedef ListGraph::Node Node;
41 typedef ListGraph::Edge Edge;
42 typedef ListGraph::NodeIt NodeIt;
43 typedef ListGraph::EdgeIt EdgeIt;
46 //Make an example graph g.
54 Edge e1 = g.addEdge(s, v1);
55 Edge e2 = g.addEdge(s, v2);
56 Edge e3 = g.addEdge(v1, v2);
57 Edge e4 = g.addEdge(v2, v1);
58 Edge e5 = g.addEdge(v1, v3);
59 Edge e6 = g.addEdge(v3, v2);
60 Edge e7 = g.addEdge(v2, v4);
61 Edge e8 = g.addEdge(v4, v3);
62 Edge e9 = g.addEdge(v3, t);
63 Edge e10 = g.addEdge(v4, t);
65 //Make the input for the kruskal.
66 typedef ListGraph::EdgeMap<int> ECostMap;
67 ECostMap edge_cost_map(g);
69 // Fill the edge_cost_map.
70 edge_cost_map.set(e1, -10);
71 edge_cost_map.set(e2, -9);
72 edge_cost_map.set(e3, -8);
73 edge_cost_map.set(e4, -7);
74 edge_cost_map.set(e5, -6);
75 edge_cost_map.set(e6, -5);
76 edge_cost_map.set(e7, -4);
77 edge_cost_map.set(e8, -3);
78 edge_cost_map.set(e9, -2);
79 edge_cost_map.set(e10, -1);
81 // Make the map or the vector, which will contain the edges of the minimum
84 typedef ListGraph::EdgeMap<bool> EBoolMap;
87 vector<Edge> tree_edge_vec;
92 //Input: a graph (g); a costmap of the graph (edge_cost_map); a
93 //boolmap (tree_map) or a vector (tree_edge_vec) to store the edges
96 //Output: it gives back the value of the minimum spanning tree, and
97 //set true for the edges of the tree in the edgemap tree_map or
98 //store the edges of the tree in the vector tree_edge_vec;
101 // Kruskal with boolmap;
102 std::cout << "The weight of the minimum spanning tree is " <<
103 kruskal(g, edge_cost_map, tree_map)<<std::endl;
106 std::cout << "The edges of the tree:" ;
107 for(EdgeIt i(g); i!=INVALID; ++i){
110 std::cout << g.id(i) <<";";
114 std::cout << std::endl;
115 std::cout << "The size of the tree is: "<< k << std::endl;
118 // Kruskal with vector;
119 std::cout << "The weight of the minimum spanning tree again is " <<
120 kruskal(g, edge_cost_map, std::back_inserter(tree_edge_vec)) <<std::endl;
124 std::cout << "The edges of the tree again: " ;
125 for(int i=tree_edge_vec.size()-1; i>=0; i--)
126 std::cout << g.id(tree_edge_vec[i]) << ";" ;
127 std::cout << std::endl;
128 std::cout << "The size of the tree again is: "<< tree_edge_vec.size()