lemon/kruskal.h
author alpar
Wed, 06 Sep 2006 08:36:52 +0000
changeset 2197 921923afd57a
parent 2084 59769591eb60
child 2205 c20b0eb92a33
permissions -rw-r--r--
Disable mip_test when no LP solver is available.
alpar@906
     1
/* -*- C++ -*-
alpar@906
     2
 *
alpar@1956
     3
 * This file is a part of LEMON, a generic C++ optimization library
alpar@1956
     4
 *
alpar@1956
     5
 * Copyright (C) 2003-2006
alpar@1956
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1359
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@906
     8
 *
alpar@906
     9
 * Permission to use, modify and distribute this software is granted
alpar@906
    10
 * provided that this copyright notice appears in all copies. For
alpar@906
    11
 * precise terms see the accompanying LICENSE file.
alpar@906
    12
 *
alpar@906
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@906
    14
 * express or implied, and with no claim as to its suitability for any
alpar@906
    15
 * purpose.
alpar@906
    16
 *
alpar@906
    17
 */
alpar@906
    18
alpar@921
    19
#ifndef LEMON_KRUSKAL_H
alpar@921
    20
#define LEMON_KRUSKAL_H
alpar@810
    21
alpar@810
    22
#include <algorithm>
klao@1942
    23
#include <vector>
alpar@921
    24
#include <lemon/unionfind.h>
deba@1993
    25
#include <lemon/bits/utility.h>
deba@1993
    26
#include <lemon/bits/traits.h>
alpar@810
    27
alpar@810
    28
///\ingroup spantree
alpar@810
    29
///\file
alpar@810
    30
///\brief Kruskal's algorithm to compute a minimum cost tree
alpar@810
    31
///
alpar@810
    32
///Kruskal's algorithm to compute a minimum cost tree.
alpar@1557
    33
///
alpar@1557
    34
///\todo The file still needs some clean-up.
alpar@810
    35
alpar@921
    36
namespace lemon {
alpar@810
    37
alpar@810
    38
  /// \addtogroup spantree
alpar@810
    39
  /// @{
alpar@810
    40
alpar@810
    41
  /// Kruskal's algorithm to find a minimum cost tree of a graph.
alpar@810
    42
alpar@810
    43
  /// This function runs Kruskal's algorithm to find a minimum cost tree.
alpar@1557
    44
  /// Due to hard C++ hacking, it accepts various input and output types.
alpar@1557
    45
  ///
alpar@1555
    46
  /// \param g The graph the algorithm runs on.
deba@2111
    47
  /// It can be either \ref concept::Graph "directed" or 
klao@1909
    48
  /// \ref concept::UGraph "undirected".
alpar@1555
    49
  /// If the graph is directed, the algorithm consider it to be 
alpar@1555
    50
  /// undirected by disregarding the direction of the edges.
alpar@810
    51
  ///
alpar@1557
    52
  /// \param in This object is used to describe the edge costs. It can be one
alpar@1557
    53
  /// of the following choices.
alpar@1557
    54
  /// - An STL compatible 'Forward Container'
alpar@824
    55
  /// with <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>,
alpar@1557
    56
  /// where \c X is the type of the costs. The pairs indicates the edges along
alpar@1557
    57
  /// with the assigned cost. <em>They must be in a
alpar@1557
    58
  /// cost-ascending order.</em>
alpar@1557
    59
  /// - Any readable Edge map. The values of the map indicate the edge costs.
alpar@810
    60
  ///
alpar@1557
    61
  /// \retval out Here we also have a choise.
alpar@1557
    62
  /// - Is can be a writable \c bool edge map. 
alpar@810
    63
  /// After running the algorithm
alpar@810
    64
  /// this will contain the found minimum cost spanning tree: the value of an
alpar@810
    65
  /// edge will be set to \c true if it belongs to the tree, otherwise it will
alpar@810
    66
  /// be set to \c false. The value of each edge will be set exactly once.
alpar@1557
    67
  /// - It can also be an iteraror of an STL Container with
alpar@1557
    68
  /// <tt>GR::Edge</tt> as its <tt>value_type</tt>.
alpar@1557
    69
  /// The algorithm copies the elements of the found tree into this sequence.
alpar@1557
    70
  /// For example, if we know that the spanning tree of the graph \c g has
alpar@1603
    71
  /// say 53 edges, then
alpar@1557
    72
  /// we can put its edges into a STL vector \c tree with a code like this.
alpar@1946
    73
  ///\code
alpar@1557
    74
  /// std::vector<Edge> tree(53);
alpar@1557
    75
  /// kruskal(g,cost,tree.begin());
alpar@1946
    76
  ///\endcode
alpar@1557
    77
  /// Or if we don't know in advance the size of the tree, we can write this.
alpar@1946
    78
  ///\code
alpar@1557
    79
  /// std::vector<Edge> tree;
alpar@1557
    80
  /// kruskal(g,cost,std::back_inserter(tree));
alpar@1946
    81
  ///\endcode
alpar@810
    82
  ///
alpar@810
    83
  /// \return The cost of the found tree.
alpar@1449
    84
  ///
alpar@1631
    85
  /// \warning If kruskal is run on an
klao@1909
    86
  /// \ref lemon::concept::UGraph "undirected graph", be sure that the
alpar@1603
    87
  /// map storing the tree is also undirected
klao@1909
    88
  /// (e.g. ListUGraph::UEdgeMap<bool>, otherwise the values of the
alpar@1603
    89
  /// half of the edges will not be set.
alpar@1603
    90
  ///
alpar@1449
    91
  /// \todo Discuss the case of undirected graphs: In this case the algorithm
klao@1909
    92
  /// also require <tt>Edge</tt>s instead of <tt>UEdge</tt>s, as some
alpar@1449
    93
  /// people would expect. So, one should be careful not to add both of the
klao@1909
    94
  /// <tt>Edge</tt>s belonging to a certain <tt>UEdge</tt>.
alpar@1570
    95
  /// (\ref kruskal() and \ref KruskalMapInput are kind enough to do so.)
alpar@810
    96
alpar@1557
    97
#ifdef DOXYGEN
alpar@824
    98
  template <class GR, class IN, class OUT>
alpar@824
    99
  typename IN::value_type::second_type
alpar@1547
   100
  kruskal(GR const& g, IN const& in, 
alpar@1557
   101
	  OUT& out)
alpar@1557
   102
#else
alpar@1557
   103
  template <class GR, class IN, class OUT>
alpar@1557
   104
  typename IN::value_type::second_type
alpar@1557
   105
  kruskal(GR const& g, IN const& in, 
alpar@1557
   106
	  OUT& out,
alpar@1557
   107
// 	  typename IN::value_type::first_type = typename GR::Edge()
alpar@1557
   108
// 	  ,typename OUT::Key = OUT::Key()
alpar@1557
   109
// 	  //,typename OUT::Key = typename GR::Edge()
alpar@1557
   110
	  const typename IN::value_type::first_type * = 
alpar@1557
   111
	  (const typename IN::value_type::first_type *)(0),
alpar@1557
   112
	  const typename OUT::Key * = (const typename OUT::Key *)(0)
alpar@1557
   113
	  )
alpar@1557
   114
#endif
alpar@810
   115
  {
alpar@824
   116
    typedef typename IN::value_type::second_type EdgeCost;
alpar@824
   117
    typedef typename GR::template NodeMap<int> NodeIntMap;
alpar@824
   118
    typedef typename GR::Node Node;
alpar@810
   119
alpar@1547
   120
    NodeIntMap comp(g, -1);
alpar@810
   121
    UnionFind<Node,NodeIntMap> uf(comp); 
alpar@810
   122
      
alpar@810
   123
    EdgeCost tot_cost = 0;
alpar@824
   124
    for (typename IN::const_iterator p = in.begin(); 
alpar@810
   125
	 p!=in.end(); ++p ) {
alpar@1547
   126
      if ( uf.join(g.target((*p).first),
alpar@1547
   127
		   g.source((*p).first)) ) {
alpar@810
   128
	out.set((*p).first, true);
alpar@810
   129
	tot_cost += (*p).second;
alpar@810
   130
      }
alpar@810
   131
      else {
alpar@810
   132
	out.set((*p).first, false);
alpar@810
   133
      }
alpar@810
   134
    }
alpar@810
   135
    return tot_cost;
alpar@810
   136
  }
alpar@810
   137
alpar@1557
   138
 
alpar@1557
   139
  /// @}
alpar@1557
   140
alpar@1557
   141
  
alpar@810
   142
  /* A work-around for running Kruskal with const-reference bool maps... */
alpar@810
   143
klao@885
   144
  /// Helper class for calling kruskal with "constant" output map.
klao@885
   145
klao@885
   146
  /// Helper class for calling kruskal with output maps constructed
klao@885
   147
  /// on-the-fly.
alpar@810
   148
  ///
klao@885
   149
  /// A typical examle is the following call:
alpar@1547
   150
  /// <tt>kruskal(g, some_input, makeSequenceOutput(iterator))</tt>.
klao@885
   151
  /// Here, the third argument is a temporary object (which wraps around an
klao@885
   152
  /// iterator with a writable bool map interface), and thus by rules of C++
klao@885
   153
  /// is a \c const object. To enable call like this exist this class and
klao@885
   154
  /// the prototype of the \ref kruskal() function with <tt>const& OUT</tt>
klao@885
   155
  /// third argument.
alpar@824
   156
  template<class Map>
alpar@810
   157
  class NonConstMapWr {
alpar@810
   158
    const Map &m;
alpar@810
   159
  public:
alpar@1557
   160
    typedef typename Map::Key Key;
alpar@987
   161
    typedef typename Map::Value Value;
alpar@810
   162
alpar@810
   163
    NonConstMapWr(const Map &_m) : m(_m) {}
alpar@810
   164
alpar@987
   165
    template<class Key>
alpar@987
   166
    void set(Key const& k, Value const &v) const { m.set(k,v); }
alpar@810
   167
  };
alpar@810
   168
alpar@824
   169
  template <class GR, class IN, class OUT>
alpar@810
   170
  inline
klao@885
   171
  typename IN::value_type::second_type
alpar@1557
   172
  kruskal(GR const& g, IN const& edges, OUT const& out_map,
alpar@1557
   173
// 	  typename IN::value_type::first_type = typename GR::Edge(),
alpar@1557
   174
// 	  typename OUT::Key = GR::Edge()
alpar@1557
   175
	  const typename IN::value_type::first_type * = 
alpar@1557
   176
	  (const typename IN::value_type::first_type *)(0),
alpar@1557
   177
	  const typename OUT::Key * = (const typename OUT::Key *)(0)
alpar@1557
   178
	  )
alpar@810
   179
  {
alpar@824
   180
    NonConstMapWr<OUT> map_wr(out_map);
alpar@1547
   181
    return kruskal(g, edges, map_wr);
alpar@810
   182
  }  
alpar@810
   183
alpar@810
   184
  /* ** ** Input-objects ** ** */
alpar@810
   185
zsuzska@1274
   186
  /// Kruskal's input source.
alpar@1557
   187
 
zsuzska@1274
   188
  /// Kruskal's input source.
alpar@810
   189
  ///
alpar@1570
   190
  /// In most cases you possibly want to use the \ref kruskal() instead.
alpar@810
   191
  ///
alpar@810
   192
  /// \sa makeKruskalMapInput()
alpar@810
   193
  ///
alpar@824
   194
  ///\param GR The type of the graph the algorithm runs on.
alpar@810
   195
  ///\param Map An edge map containing the cost of the edges.
alpar@810
   196
  ///\par
alpar@810
   197
  ///The cost type can be any type satisfying
alpar@810
   198
  ///the STL 'LessThan comparable'
alpar@810
   199
  ///concept if it also has an operator+() implemented. (It is necessary for
alpar@810
   200
  ///computing the total cost of the tree).
alpar@810
   201
  ///
alpar@824
   202
  template<class GR, class Map>
alpar@810
   203
  class KruskalMapInput
alpar@824
   204
    : public std::vector< std::pair<typename GR::Edge,
alpar@987
   205
				    typename Map::Value> > {
alpar@810
   206
    
alpar@810
   207
  public:
alpar@824
   208
    typedef std::vector< std::pair<typename GR::Edge,
alpar@987
   209
				   typename Map::Value> > Parent;
alpar@810
   210
    typedef typename Parent::value_type value_type;
alpar@810
   211
alpar@810
   212
  private:
alpar@810
   213
    class comparePair {
alpar@810
   214
    public:
alpar@810
   215
      bool operator()(const value_type& a,
alpar@810
   216
		      const value_type& b) {
alpar@810
   217
	return a.second < b.second;
alpar@810
   218
      }
alpar@810
   219
    };
alpar@810
   220
alpar@1449
   221
    template<class _GR>
deba@1979
   222
    typename enable_if<UndirectedTagIndicator<_GR>,void>::type
alpar@1547
   223
    fillWithEdges(const _GR& g, const Map& m,dummy<0> = 0) 
alpar@1449
   224
    {
klao@1909
   225
      for(typename GR::UEdgeIt e(g);e!=INVALID;++e) 
deba@1679
   226
	push_back(value_type(g.direct(e, true), m[e]));
alpar@1449
   227
    }
alpar@1449
   228
alpar@1449
   229
    template<class _GR>
deba@1979
   230
    typename disable_if<UndirectedTagIndicator<_GR>,void>::type
alpar@1547
   231
    fillWithEdges(const _GR& g, const Map& m,dummy<1> = 1) 
alpar@1449
   232
    {
alpar@1547
   233
      for(typename GR::EdgeIt e(g);e!=INVALID;++e) 
alpar@1449
   234
	push_back(value_type(e, m[e]));
alpar@1449
   235
    }
alpar@1449
   236
    
alpar@1449
   237
    
alpar@810
   238
  public:
alpar@810
   239
alpar@810
   240
    void sort() {
alpar@810
   241
      std::sort(this->begin(), this->end(), comparePair());
alpar@810
   242
    }
alpar@810
   243
alpar@1547
   244
    KruskalMapInput(GR const& g, Map const& m) {
alpar@1547
   245
      fillWithEdges(g,m); 
alpar@810
   246
      sort();
alpar@810
   247
    }
alpar@810
   248
  };
alpar@810
   249
alpar@810
   250
  /// Creates a KruskalMapInput object for \ref kruskal()
alpar@810
   251
zsuzska@1274
   252
  /// It makes easier to use 
alpar@810
   253
  /// \ref KruskalMapInput by making it unnecessary 
alpar@810
   254
  /// to explicitly give the type of the parameters.
alpar@810
   255
  ///
alpar@810
   256
  /// In most cases you possibly
alpar@1570
   257
  /// want to use \ref kruskal() instead.
alpar@810
   258
  ///
alpar@1547
   259
  ///\param g The type of the graph the algorithm runs on.
alpar@810
   260
  ///\param m An edge map containing the cost of the edges.
alpar@810
   261
  ///\par
alpar@810
   262
  ///The cost type can be any type satisfying the
alpar@810
   263
  ///STL 'LessThan Comparable'
alpar@810
   264
  ///concept if it also has an operator+() implemented. (It is necessary for
alpar@810
   265
  ///computing the total cost of the tree).
alpar@810
   266
  ///
alpar@810
   267
  ///\return An appropriate input source for \ref kruskal().
alpar@810
   268
  ///
alpar@824
   269
  template<class GR, class Map>
alpar@810
   270
  inline
alpar@1547
   271
  KruskalMapInput<GR,Map> makeKruskalMapInput(const GR &g,const Map &m)
alpar@810
   272
  {
alpar@1547
   273
    return KruskalMapInput<GR,Map>(g,m);
alpar@810
   274
  }
alpar@810
   275
  
alpar@810
   276
  
klao@885
   277
klao@885
   278
  /* ** ** Output-objects: simple writable bool maps ** ** */
alpar@810
   279
  
klao@885
   280
klao@885
   281
alpar@810
   282
  /// A writable bool-map that makes a sequence of "true" keys
alpar@810
   283
alpar@810
   284
  /// A writable bool-map that creates a sequence out of keys that receives
alpar@810
   285
  /// the value "true".
klao@885
   286
  ///
klao@885
   287
  /// \sa makeKruskalSequenceOutput()
klao@885
   288
  ///
klao@885
   289
  /// Very often, when looking for a min cost spanning tree, we want as
klao@885
   290
  /// output a container containing the edges of the found tree. For this
klao@885
   291
  /// purpose exist this class that wraps around an STL iterator with a
klao@885
   292
  /// writable bool map interface. When a key gets value "true" this key
klao@885
   293
  /// is added to sequence pointed by the iterator.
klao@885
   294
  ///
klao@885
   295
  /// A typical usage:
alpar@1946
   296
  ///\code
klao@885
   297
  /// std::vector<Graph::Edge> v;
klao@885
   298
  /// kruskal(g, input, makeKruskalSequenceOutput(back_inserter(v)));
alpar@1946
   299
  ///\endcode
klao@885
   300
  /// 
klao@885
   301
  /// For the most common case, when the input is given by a simple edge
klao@885
   302
  /// map and the output is a sequence of the tree edges, a special
klao@885
   303
  /// wrapper function exists: \ref kruskalEdgeMap_IteratorOut().
klao@885
   304
  ///
alpar@987
   305
  /// \warning Not a regular property map, as it doesn't know its Key
klao@885
   306
alpar@824
   307
  template<class Iterator>
klao@885
   308
  class KruskalSequenceOutput {
alpar@810
   309
    mutable Iterator it;
alpar@810
   310
alpar@810
   311
  public:
klao@1942
   312
    typedef typename std::iterator_traits<Iterator>::value_type Key;
alpar@987
   313
    typedef bool Value;
alpar@810
   314
klao@885
   315
    KruskalSequenceOutput(Iterator const &_it) : it(_it) {}
alpar@810
   316
alpar@987
   317
    template<typename Key>
alpar@987
   318
    void set(Key const& k, bool v) const { if(v) {*it=k; ++it;} }
alpar@810
   319
  };
alpar@810
   320
alpar@824
   321
  template<class Iterator>
alpar@810
   322
  inline
klao@885
   323
  KruskalSequenceOutput<Iterator>
klao@885
   324
  makeKruskalSequenceOutput(Iterator it) {
klao@885
   325
    return KruskalSequenceOutput<Iterator>(it);
alpar@810
   326
  }
alpar@810
   327
klao@885
   328
klao@885
   329
alpar@810
   330
  /* ** ** Wrapper funtions ** ** */
alpar@810
   331
alpar@1557
   332
//   \brief Wrapper function to kruskal().
alpar@1557
   333
//   Input is from an edge map, output is a plain bool map.
alpar@1557
   334
//  
alpar@1557
   335
//   Wrapper function to kruskal().
alpar@1557
   336
//   Input is from an edge map, output is a plain bool map.
alpar@1557
   337
//  
alpar@1557
   338
//   \param g The type of the graph the algorithm runs on.
alpar@1557
   339
//   \param in An edge map containing the cost of the edges.
alpar@1557
   340
//   \par
alpar@1557
   341
//   The cost type can be any type satisfying the
alpar@1557
   342
//   STL 'LessThan Comparable'
alpar@1557
   343
//   concept if it also has an operator+() implemented. (It is necessary for
alpar@1557
   344
//   computing the total cost of the tree).
alpar@1557
   345
//  
alpar@1557
   346
//   \retval out This must be a writable \c bool edge map.
alpar@1557
   347
//   After running the algorithm
alpar@1557
   348
//   this will contain the found minimum cost spanning tree: the value of an
alpar@1557
   349
//   edge will be set to \c true if it belongs to the tree, otherwise it will
alpar@1557
   350
//   be set to \c false. The value of each edge will be set exactly once.
alpar@1557
   351
//  
alpar@1557
   352
//   \return The cost of the found tree.
alpar@810
   353
alpar@824
   354
  template <class GR, class IN, class RET>
alpar@810
   355
  inline
alpar@987
   356
  typename IN::Value
alpar@1557
   357
  kruskal(GR const& g,
alpar@1557
   358
	  IN const& in,
alpar@1557
   359
	  RET &out,
alpar@1557
   360
	  //	  typename IN::Key = typename GR::Edge(),
alpar@1557
   361
	  //typename IN::Key = typename IN::Key (),
alpar@1557
   362
	  //	  typename RET::Key = typename GR::Edge()
alpar@1557
   363
	  const typename IN::Key *  = (const typename IN::Key *)(0),
alpar@1557
   364
	  const typename RET::Key * = (const typename RET::Key *)(0)
alpar@1557
   365
	  )
alpar@1557
   366
  {
alpar@1547
   367
    return kruskal(g,
alpar@1547
   368
		   KruskalMapInput<GR,IN>(g,in),
alpar@810
   369
		   out);
alpar@810
   370
  }
alpar@810
   371
alpar@1557
   372
//   \brief Wrapper function to kruskal().
alpar@1557
   373
//   Input is from an edge map, output is an STL Sequence.
alpar@1557
   374
//  
alpar@1557
   375
//   Wrapper function to kruskal().
alpar@1557
   376
//   Input is from an edge map, output is an STL Sequence.
alpar@1557
   377
//  
alpar@1557
   378
//   \param g The type of the graph the algorithm runs on.
alpar@1557
   379
//   \param in An edge map containing the cost of the edges.
alpar@1557
   380
//   \par
alpar@1557
   381
//   The cost type can be any type satisfying the
alpar@1557
   382
//   STL 'LessThan Comparable'
alpar@1557
   383
//   concept if it also has an operator+() implemented. (It is necessary for
alpar@1557
   384
//   computing the total cost of the tree).
alpar@1557
   385
//  
alpar@1557
   386
//   \retval out This must be an iteraror of an STL Container with
alpar@1557
   387
//   <tt>GR::Edge</tt> as its <tt>value_type</tt>.
alpar@1557
   388
//   The algorithm copies the elements of the found tree into this sequence.
alpar@1557
   389
//   For example, if we know that the spanning tree of the graph \c g has
alpar@1603
   390
//   say 53 edges, then
alpar@1557
   391
//   we can put its edges into a STL vector \c tree with a code like this.
alpar@1946
   392
//\code
alpar@1557
   393
//   std::vector<Edge> tree(53);
alpar@1570
   394
//   kruskal(g,cost,tree.begin());
alpar@1946
   395
//\endcode
alpar@1557
   396
//   Or if we don't know in advance the size of the tree, we can write this.
alpar@1946
   397
//\code
alpar@1557
   398
//   std::vector<Edge> tree;
alpar@1570
   399
//   kruskal(g,cost,std::back_inserter(tree));
alpar@1946
   400
//\endcode
alpar@1557
   401
//  
alpar@1557
   402
//   \return The cost of the found tree.
alpar@1557
   403
//  
alpar@1557
   404
//   \bug its name does not follow the coding style.
klao@885
   405
alpar@824
   406
  template <class GR, class IN, class RET>
alpar@810
   407
  inline
alpar@987
   408
  typename IN::Value
alpar@1557
   409
  kruskal(const GR& g,
alpar@1557
   410
	  const IN& in,
alpar@1557
   411
	  RET out,
alpar@1557
   412
	  const typename RET::value_type * = 
alpar@1557
   413
	  (const typename RET::value_type *)(0)
alpar@1557
   414
	  )
alpar@810
   415
  {
klao@885
   416
    KruskalSequenceOutput<RET> _out(out);
alpar@1547
   417
    return kruskal(g, KruskalMapInput<GR,IN>(g, in), _out);
alpar@810
   418
  }
alpar@1557
   419
 
klao@1942
   420
  template <class GR, class IN, class RET>
klao@1942
   421
  inline
klao@1942
   422
  typename IN::Value
klao@1942
   423
  kruskal(const GR& g,
klao@1942
   424
	  const IN& in,
klao@1942
   425
	  RET *out
klao@1942
   426
	  )
klao@1942
   427
  {
klao@1942
   428
    KruskalSequenceOutput<RET*> _out(out);
klao@1942
   429
    return kruskal(g, KruskalMapInput<GR,IN>(g, in), _out);
klao@1942
   430
  }
klao@1942
   431
 
alpar@810
   432
  /// @}
alpar@810
   433
alpar@921
   434
} //namespace lemon
alpar@810
   435
alpar@921
   436
#endif //LEMON_KRUSKAL_H