COIN-OR::LEMON - Graph Library

Changeset 1578:1d3a1bcbc874 in lemon-0.x


Ignore:
Timestamp:
07/21/05 00:36:37 (14 years ago)
Author:
zsuzska
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

Legend:

Unmodified
Added
Removed
  • demo/kruskal_demo.cc

    r1435 r1578  
     1/* -*- C++ -*-
     2 * demo/kruskal_demo.cc - Part of LEMON, a generic C++ optimization library
     3 *
     4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     6 *
     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.
     10 *
     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
     13 * purpose.
     14 *
     15 */
     16
     17///\ingroup demos
     18///\file
     19///\brief Minimum weight spanning tree by Kruskal algorithm (demo).
     20///
     21///This demo program shows how to find a minimum weight spannin tree
     22///of a graph by using the Kruskal algorithm.
     23
    124#include <iostream>
    225#include <vector>
     
    1841  typedef ListGraph::EdgeIt EdgeIt;
    1942
    20   ListGraph G;
     43  ListGraph g;
     44  //Make an example graph g.
     45  Node s=g.addNode();
     46  Node v1=g.addNode();
     47  Node v2=g.addNode();
     48  Node v3=g.addNode();
     49  Node v4=g.addNode();
     50  Node t=g.addNode();
     51 
     52  Edge e1 = g.addEdge(s, v1);
     53  Edge e2 = g.addEdge(s, v2);
     54  Edge e3 = g.addEdge(v1, v2);
     55  Edge e4 = g.addEdge(v2, v1);
     56  Edge e5 = g.addEdge(v1, v3);
     57  Edge e6 = g.addEdge(v3, v2);
     58  Edge e7 = g.addEdge(v2, v4);
     59  Edge e8 = g.addEdge(v4, v3);
     60  Edge e9 = g.addEdge(v3, t);
     61  Edge e10 = g.addEdge(v4, t);
    2162
    22   Node s=G.addNode();
    23   Node v1=G.addNode();
    24   Node v2=G.addNode();
    25   Node v3=G.addNode();
    26   Node v4=G.addNode();
    27   Node t=G.addNode();
    28  
    29   Edge e1 = G.addEdge(s, v1);
    30   Edge e2 = G.addEdge(s, v2);
    31   Edge e3 = G.addEdge(v1, v2);
    32   Edge e4 = G.addEdge(v2, v1);
    33   Edge e5 = G.addEdge(v1, v3);
    34   Edge e6 = G.addEdge(v3, v2);
    35   Edge e7 = G.addEdge(v2, v4);
    36   Edge e8 = G.addEdge(v4, v3);
    37   Edge e9 = G.addEdge(v3, t);
    38   Edge e10 = G.addEdge(v4, t);
    39 
     63  //Make the input and output for the kruskal.
    4064  typedef ListGraph::EdgeMap<int> ECostMap;
    4165  typedef ListGraph::EdgeMap<bool> EBoolMap;
    4266
    43   ECostMap edge_cost_map(G, 2);
    44   EBoolMap tree_map(G);
    45  
     67  ECostMap edge_cost_map(g, 2);
     68  EBoolMap tree_map(g);
    4669
    47   //Test with const map.
    48   std::cout << "The weight of the minimum spanning tree is " << kruskalEdgeMap(G, ConstMap<ListGraph::Edge,int>(2), tree_map)<<std::endl;
     70  // Kruskal.
     71  std::cout << "The weight of the minimum spanning tree by using Kruskal algorithm is "
     72            << kruskal(g, ConstMap<ListGraph::Edge,int>(2), tree_map)<<std::endl;
    4973
    50 /*
    51   ==10,
    52         "Total cost should be 10");
    53   //Test with a edge map (filled with uniform costs).
    54   check(kruskalEdgeMap(G, edge_cost_map, tree_map)==10,
    55         "Total cost should be 10");
    56 
    57   edge_cost_map.set(e1, -10);
    58   edge_cost_map.set(e2, -9);
    59   edge_cost_map.set(e3, -8);
    60   edge_cost_map.set(e4, -7);
    61   edge_cost_map.set(e5, -6);
    62   edge_cost_map.set(e6, -5);
    63   edge_cost_map.set(e7, -4);
    64   edge_cost_map.set(e8, -3);
    65   edge_cost_map.set(e9, -2);
    66   edge_cost_map.set(e10, -1);
     74  //Make another input (non-uniform costs) for the kruskal.
     75  ECostMap edge_cost_map_2(g);
     76  edge_cost_map_2.set(e1, -10);
     77  edge_cost_map_2.set(e2, -9);
     78  edge_cost_map_2.set(e3, -8);
     79  edge_cost_map_2.set(e4, -7);
     80  edge_cost_map_2.set(e5, -6);
     81  edge_cost_map_2.set(e6, -5);
     82  edge_cost_map_2.set(e7, -4);
     83  edge_cost_map_2.set(e8, -3);
     84  edge_cost_map_2.set(e9, -2);
     85  edge_cost_map_2.set(e10, -1);
    6786
    6887  vector<Edge> tree_edge_vec;
    6988
    70   //Test with a edge map and inserter.
    71   check(kruskalEdgeMap_IteratorOut(G, edge_cost_map,
    72                                    back_inserter(tree_edge_vec))
    73         ==-31,
    74         "Total cost should be -31.");
     89  //Test with non uniform costs and inserter.
     90  std::cout << "The weight of the minimum spanning tree with non-uniform costs is " <<
     91    kruskal(g, edge_cost_map_2, std::back_inserter(tree_edge_vec)) <<std::endl;
    7592
     93  //The vector for the edges of the output tree.
    7694  tree_edge_vec.clear();
    7795
    78   //The above test could also be coded like this:
    79   check(kruskal(G,
    80                 makeKruskalMapInput(G, edge_cost_map),
    81                 makeKruskalSequenceOutput(back_inserter(tree_edge_vec)))
    82         ==-31,
    83         "Total cost should be -31.");
     96  //Test with makeKruskalSequenceOutput and makeKruskalSequenceOutput.
    8497
    85   check(tree_edge_vec.size()==5,"The tree should have 5 edges.");
     98  std::cout << "The weight of the minimum spanning tree again is " <<
     99   kruskal(g,makeKruskalMapInput(g,edge_cost_map_2),makeKruskalSequenceOutput(std::back_inserter(tree_edge_vec)))<< std::endl;
    86100
    87   check(tree_edge_vec[0]==e1 &&
    88         tree_edge_vec[1]==e2 &&
    89         tree_edge_vec[2]==e5 &&
    90         tree_edge_vec[3]==e7 &&
    91         tree_edge_vec[4]==e9,
    92         "Wrong tree.");
    93 */
     101
    94102  return 0;
    95103}
  • doc/quicktour.dox

    r1541 r1578  
    142142
    143143
    144 <li> If you want to design a network and want to minimize the total length
    145 of wires then you might be looking for a <b>minimum spanning tree</b> in
    146 an undirected graph. This can be found using the Kruskal algorithm: the
    147 function \ref lemon::kruskal "LEMON Kruskal ..." does this job for you.
    148 The following code fragment shows an example:
    149 
    150 Ide Zsuzska fog irni!
     144<li> If you want to design a network and want to minimize the total
     145length of wires then you might be looking for a <b>minimum spanning
     146tree</b> in an undirected graph. This can be found using the Kruskal
     147algorithm: the function \ref lemon::kruskal "LEMON Kruskal " does
     148this job for you.  After we had a graph \c g and a cost map \c
     149edge_cost_map , the following code fragment shows an example how to get weight of the minmum spanning tree, if the costs are uniform:
     150
     151\dontinclude kruskal_demo.cc
     152\skip std::cout
     153\until kruskal
     154
     155It gives back a edge bool map, which contains the edges of the tree.
     156If the costs are non-uniform, for example  the cost is given by \c
     157edge_cost_map_2 , or the edges of the tree are have to be given in a
     158vector, then we can give to the kruskal a vector \c tree_edge_vec , instead of
     159an edge bool map:
     160
     161\skip edge_cost_map_2
     162\until edge_cost_map_2, std::back_inserter
     163
     164And finally the next fragment shows how to use the functions \c makeKruskalMapInput and \c makeKruskalSequenceOutPut:
     165
     166\skip makeKruskalSequenceOutput
     167\until tree_edge_vec
     168
     169See the whole program in \ref kruskal_demo.cc.
     170
     171
    151172
    152173<li>Many problems in network optimization can be formalized by means
Note: See TracChangeset for help on using the changeset viewer.