demo/kruskal_demo.cc
author alpar
Mon, 01 Aug 2005 21:24:55 +0000
changeset 1611 bb51e4a510c5
parent 1583 2b329fd595ef
child 1641 77f6ab7ad66f
permissions -rw-r--r--
We must always have lemon/config.h
     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 <iostream>
    25 #include <vector>
    26 
    27 #include <lemon/maps.h>
    28 #include <lemon/kruskal.h>
    29 #include <lemon/list_graph.h>
    30 
    31 
    32 using namespace std;
    33 using namespace lemon;
    34 
    35 
    36 int main() {
    37 
    38   typedef ListGraph::Node Node;
    39   typedef ListGraph::Edge Edge;
    40   typedef ListGraph::NodeIt NodeIt;
    41   typedef ListGraph::EdgeIt EdgeIt;
    42 
    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);
    62 
    63   //Make the input for the kruskal.
    64   typedef ListGraph::EdgeMap<int> ECostMap;
    65   ECostMap edge_cost_map(g);
    66 
    67   // Fill the edge_cost_map. 
    68   edge_cost_map.set(e1, -10);
    69   edge_cost_map.set(e2, -9);
    70   edge_cost_map.set(e3, -8);
    71   edge_cost_map.set(e4, -7);
    72   edge_cost_map.set(e5, -6);
    73   edge_cost_map.set(e6, -5);
    74   edge_cost_map.set(e7, -4);
    75   edge_cost_map.set(e8, -3);
    76   edge_cost_map.set(e9, -2);
    77   edge_cost_map.set(e10, -1);
    78 
    79   // Make the map or the vector, which will contain the edges of the minimum
    80   // spanning tree.
    81 
    82   typedef ListGraph::EdgeMap<bool> EBoolMap;
    83   EBoolMap tree_map(g);
    84 
    85   vector<Edge> tree_edge_vec;
    86 
    87 
    88   //Kruskal Algorithm.  
    89 
    90   //Input: a graph (g); a costmap of the graph (edge_cost_map); a
    91   //boolmap (tree_map) or a vector (tree_edge_vec) to store the edges
    92   //of the output tree;
    93 
    94   //Output: it gives back the value of the minimum spanning tree, and
    95   //set true for the edges of the tree in the edgemap tree_map or
    96   //store the edges of the tree in the vector tree_edge_vec;
    97 
    98 
    99   // Kruskal with boolmap;
   100   std::cout << "The weight of the minimum spanning tree is " << 
   101     kruskal(g, edge_cost_map, tree_map)<<std::endl;
   102 
   103   int k=0;
   104   std::cout << "The edges of the tree:" ;
   105   for(EdgeIt i(g); i!=INVALID; ++i){
   106 
   107     if (tree_map[i]) { 
   108       std::cout << g.id(i) <<";";
   109       ++k;
   110     }
   111   }
   112   std::cout << std::endl;
   113   std::cout << "The size of the tree is: "<< k << std::endl;
   114 
   115 
   116   // Kruskal with vector;
   117   std::cout << "The weight of the minimum spanning tree again is " << 
   118     kruskal(g, edge_cost_map, std::back_inserter(tree_edge_vec)) <<std::endl;
   119 
   120 
   121 
   122   std::cout << "The edges of the tree again: " ;
   123   for(int i=tree_edge_vec.size()-1; i>=0;  i--)
   124     std::cout << g.id(tree_edge_vec[i]) << ";" ;
   125   std::cout << std::endl;
   126   std::cout << "The size of the tree again is: "<< tree_edge_vec.size()<< std::endl; 
   127 
   128   
   129   return 0;
   130 }