Changeset 1578:1d3a1bcbc874 in lemon-0.x

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

kruskal_demo corrected, quicktour filled with kruskal

Files:
2 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)) <
• doc/quicktour.dox

 r1541
• If you want to design a network and want to minimize the total length of wires then you might be looking for a minimum spanning tree in an undirected graph. This can be found using the Kruskal algorithm: the function \ref lemon::kruskal "LEMON Kruskal ..." does this job for you. The following code fragment shows an example: Ide Zsuzska fog irni!
• If you want to design a network and want to minimize the total length of wires then you might be looking for a minimum spanning tree in an undirected graph. This can be found using the Kruskal algorithm: the function \ref lemon::kruskal "LEMON Kruskal " does this job for you.  After we had a graph \c g and a cost map \c edge_cost_map , the following code fragment shows an example how to get weight of the minmum spanning tree, if the costs are uniform: \dontinclude kruskal_demo.cc \skip std::cout \until kruskal It gives back a edge bool map, which contains the edges of the tree. If the costs are non-uniform, for example  the cost is given by \c edge_cost_map_2 , or the edges of the tree are have to be given in a vector, then we can give to the kruskal a vector \c tree_edge_vec , instead of an edge bool map: \skip edge_cost_map_2 \until edge_cost_map_2, std::back_inserter And finally the next fragment shows how to use the functions \c makeKruskalMapInput and \c makeKruskalSequenceOutPut: \skip makeKruskalSequenceOutput \until tree_edge_vec See the whole program in \ref kruskal_demo.cc.
• Many problems in network optimization can be formalized by means
Note: See TracChangeset for help on using the changeset viewer.