# Changeset 1578:1d3a1bcbc874 in lemon-0.x for demo/kruskal_demo.cc

Ignore:
Timestamp:
07/21/05 00:36:37 (15 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2079
Message:

kruskal_demo corrected, quicktour filled with kruskal

File:
1 edited

Unmodified
Added
Removed
• ## demo/kruskal_demo.cc

 r1435 /* -*- 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 spannin tree ///of a graph by using the Kruskal algorithm. #include #include typedef ListGraph::EdgeIt EdgeIt; ListGraph G; 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); 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); ECostMap edge_cost_map(g, 2); EBoolMap tree_map(g); //Test with const map. std::cout << "The weight of the minimum spanning tree is " << kruskalEdgeMap(G, ConstMap(2), tree_map)<(2), tree_map)< tree_edge_vec; //Test with a edge map and inserter. check(kruskalEdgeMap_IteratorOut(G, edge_cost_map, back_inserter(tree_edge_vec)) ==-31, "Total cost should be -31."); //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)) <
Note: See TracChangeset for help on using the changeset viewer.