demo/kruskal_demo.cc
author ladanyi
Tue, 23 Aug 2005 15:57:12 +0000
changeset 1646 2dd083dded66
parent 1584 cf4bc8d477f4
child 1875 98698b69a902
permissions -rw-r--r--
- handle the case when there is no id map in the edgeset section
- do not use ListGraph.id() to determine the id of a new node/edge
     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 spanning tree
    22 /// in a graph by using the Kruskal algorithm. 
    23 ///
    24 /// \include kruskal_demo.cc
    25 
    26 #include <iostream>
    27 #include <vector>
    28 
    29 #include <lemon/maps.h>
    30 #include <lemon/kruskal.h>
    31 #include <lemon/list_graph.h>
    32 
    33 
    34 using namespace std;
    35 using namespace lemon;
    36 
    37 
    38 int main() {
    39 
    40   typedef ListGraph::Node Node;
    41   typedef ListGraph::Edge Edge;
    42   typedef ListGraph::NodeIt NodeIt;
    43   typedef ListGraph::EdgeIt EdgeIt;
    44 
    45   ListGraph g;
    46   //Make an example graph g.
    47   Node s=g.addNode();
    48   Node v1=g.addNode();
    49   Node v2=g.addNode();
    50   Node v3=g.addNode();
    51   Node v4=g.addNode();
    52   Node t=g.addNode();
    53   
    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);
    64 
    65   //Make the input for the kruskal.
    66   typedef ListGraph::EdgeMap<int> ECostMap;
    67   ECostMap edge_cost_map(g);
    68 
    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);
    80 
    81   // Make the map or the vector, which will contain the edges of the minimum
    82   // spanning tree.
    83 
    84   typedef ListGraph::EdgeMap<bool> EBoolMap;
    85   EBoolMap tree_map(g);
    86 
    87   vector<Edge> tree_edge_vec;
    88 
    89 
    90   //Kruskal Algorithm.  
    91 
    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
    94   //of the output tree;
    95 
    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;
    99 
   100 
   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;
   104 
   105   int k=0;
   106   std::cout << "The edges of the tree:" ;
   107   for(EdgeIt i(g); i!=INVALID; ++i){
   108 
   109     if (tree_map[i]) { 
   110       std::cout << g.id(i) <<";";
   111       ++k;
   112     }
   113   }
   114   std::cout << std::endl;
   115   std::cout << "The size of the tree is: "<< k << std::endl;
   116 
   117 
   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;
   121 
   122 
   123 
   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()
   129 	    << std::endl; 
   130 
   131   
   132   return 0;
   133 }