/* -*- C++ -*- * demo/kruskal_demo.cc - Part of LEMON, a generic C++ optimization library * * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * * Permission to use, modify and distribute this software is granted * provided that this copyright notice appears in all copies. For * precise terms see the accompanying LICENSE file. * * This software is provided "AS IS" with no warranty of any kind, * express or implied, and with no claim as to its suitability for any * purpose. * */ ///\ingroup demos ///\file ///\brief Minimum weight spanning tree by Kruskal algorithm (demo). /// /// This demo program shows how to find a minimum weight spanning tree /// in a graph by using the Kruskal algorithm. #include #include #include #include #include using namespace std; using namespace lemon; int main() { typedef ListGraph::Node Node; typedef ListGraph::Edge Edge; typedef ListGraph::NodeIt NodeIt; typedef ListGraph::EdgeIt EdgeIt; ListGraph g; //Make an example graph g. Node s=g.addNode(); Node v1=g.addNode(); Node v2=g.addNode(); Node v3=g.addNode(); Node v4=g.addNode(); Node t=g.addNode(); Edge e1 = g.addEdge(s, v1); Edge e2 = g.addEdge(s, v2); Edge e3 = g.addEdge(v1, v2); Edge e4 = g.addEdge(v2, v1); Edge e5 = g.addEdge(v1, v3); Edge e6 = g.addEdge(v3, v2); Edge e7 = g.addEdge(v2, v4); Edge e8 = g.addEdge(v4, v3); Edge e9 = g.addEdge(v3, t); Edge e10 = g.addEdge(v4, t); //Make the input and output for the kruskal. typedef ListGraph::EdgeMap ECostMap; typedef ListGraph::EdgeMap EBoolMap; ECostMap edge_cost_map(g, 2); EBoolMap tree_map(g); // Kruskal. std::cout << "The weight of the minimum spanning tree by using Kruskal algorithm is " << kruskal(g, ConstMap(2), tree_map)< tree_edge_vec; //Test with non uniform costs and inserter. std::cout << "The weight of the minimum spanning tree with non-uniform costs is " << kruskal(g, edge_cost_map_2, std::back_inserter(tree_edge_vec)) <