demo/kruskal_demo.cc
author klao
Tue, 29 Jan 2008 03:39:05 +0000
changeset 2559 75dd6d724f26
parent 2391 14a343be7a5a
permissions -rw-r--r--
grid_ugraph.h: fixed #18 (global functions inlined)
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 ///\ingroup demos
    20 ///\file
    21 ///\brief Minimum weight spanning tree by Kruskal algorithm (demo).
    22 ///
    23 /// This demo program shows how to find a minimum weight spanning tree
    24 /// in a graph by using the Kruskal algorithm. 
    25 ///
    26 /// \include kruskal_demo.cc
    27 
    28 #include <iostream>
    29 #include <vector>
    30 
    31 #include <lemon/maps.h>
    32 #include <lemon/kruskal.h>
    33 #include <lemon/list_graph.h>
    34 
    35 
    36 using namespace std;
    37 using namespace lemon;
    38 
    39 
    40 int main() {
    41 
    42   typedef ListGraph::Node Node;
    43   typedef ListGraph::Edge Edge;
    44   typedef ListGraph::NodeIt NodeIt;
    45   typedef ListGraph::EdgeIt EdgeIt;
    46 
    47   ListGraph g;
    48   //Make an example graph g.
    49   Node s=g.addNode();
    50   Node v1=g.addNode();
    51   Node v2=g.addNode();
    52   Node v3=g.addNode();
    53   Node v4=g.addNode();
    54   Node t=g.addNode();
    55   
    56   Edge e1 = g.addEdge(s, v1);
    57   Edge e2 = g.addEdge(s, v2);
    58   Edge e3 = g.addEdge(v1, v2);
    59   Edge e4 = g.addEdge(v2, v1);
    60   Edge e5 = g.addEdge(v1, v3);
    61   Edge e6 = g.addEdge(v3, v2);
    62   Edge e7 = g.addEdge(v2, v4);
    63   Edge e8 = g.addEdge(v4, v3);
    64   Edge e9 = g.addEdge(v3, t);
    65   Edge e10 = g.addEdge(v4, t);
    66 
    67   //Make the input for the kruskal.
    68   typedef ListGraph::EdgeMap<int> ECostMap;
    69   ECostMap edge_cost_map(g);
    70 
    71   // Fill the edge_cost_map. 
    72   edge_cost_map.set(e1, -10);
    73   edge_cost_map.set(e2, -9);
    74   edge_cost_map.set(e3, -8);
    75   edge_cost_map.set(e4, -7);
    76   edge_cost_map.set(e5, -6);
    77   edge_cost_map.set(e6, -5);
    78   edge_cost_map.set(e7, -4);
    79   edge_cost_map.set(e8, -3);
    80   edge_cost_map.set(e9, -2);
    81   edge_cost_map.set(e10, -1);
    82 
    83   // Make the map or the vector, which will contain the edges of the minimum
    84   // spanning tree.
    85 
    86   typedef ListGraph::EdgeMap<bool> EBoolMap;
    87   EBoolMap tree_map(g);
    88 
    89   vector<Edge> tree_edge_vec;
    90 
    91 
    92   //Kruskal Algorithm.  
    93 
    94   //Input: a graph (g); a costmap of the graph (edge_cost_map); a
    95   //boolmap (tree_map) or a vector (tree_edge_vec) to store the edges
    96   //of the output tree;
    97 
    98   //Output: it gives back the value of the minimum spanning tree, and
    99   //set true for the edges of the tree in the edgemap tree_map or
   100   //store the edges of the tree in the vector tree_edge_vec;
   101 
   102 
   103   // Kruskal with boolmap;
   104   std::cout << "The weight of the minimum spanning tree is " << 
   105     kruskal(g, edge_cost_map, tree_map)<<std::endl;
   106 
   107   int k=0;
   108   std::cout << "The edges of the tree:" ;
   109   for(EdgeIt i(g); i!=INVALID; ++i)
   110     if (tree_map[i]) { 
   111       std::cout << g.id(i) <<";";
   112       ++k;
   113     }
   114 
   115   std::cout << std::endl;
   116   std::cout << "The size of the tree is: "<< k << std::endl;
   117 
   118 
   119   // Kruskal with vector;
   120   std::cout << "The weight of the minimum spanning tree again is " << 
   121     kruskal(g, edge_cost_map, std::back_inserter(tree_edge_vec)) <<std::endl;
   122 
   123 
   124 
   125   std::cout << "The edges of the tree again: " ;
   126   for(int i=tree_edge_vec.size()-1; i>=0;  i--)
   127     std::cout << g.id(tree_edge_vec[i]) << ";" ;
   128   std::cout << std::endl;
   129   std::cout << "The size of the tree again is: "<< tree_edge_vec.size()
   130 	    << std::endl; 
   131 
   132   
   133   return 0;
   134 }