src/work/johanna/kruskal.h
author deba
Thu, 02 Sep 2004 10:07:30 +0000
changeset 782 df2e45e09652
parent 755 a8c2e828ce0b
permissions -rw-r--r--
--This line, and those below, will be ignored--

A hugo/sym_map_factory.h
M hugo/list_graph.h
A hugo/array_map_factory.h
A hugo/map_registry.h
M hugo/smart_graph.h
A hugo/map_defines.h
A hugo/extended_pair.h
M hugo/full_graph.h
A hugo/vector_map_factory.h
beckerjc@150
     1
// -*- c++ -*- //
beckerjc@150
     2
#ifndef HUGO_KRUSKAL_H
beckerjc@150
     3
#define HUGO_KRUSKAL_H
beckerjc@150
     4
beckerjc@150
     5
#include <algorithm>
alpar@737
     6
#include <hugo/unionfind.h>
beckerjc@150
     7
alpar@758
     8
/**
alpar@758
     9
@defgroup spantree Minimum Cost Spanning Tree Algorithms
alpar@758
    10
\brief This group containes the algorithms for finding a minimum cost spanning
alpar@758
    11
tree in a graph
alpar@758
    12
@ingroup galgs
alpar@758
    13
*/
alpar@758
    14
alpar@758
    15
///\ingroup spantree
alpar@682
    16
///\file
alpar@682
    17
///\brief Kruskal's algorithm to compute a minimum cost tree
alpar@682
    18
beckerjc@150
    19
namespace hugo {
beckerjc@150
    20
alpar@758
    21
  /// \addtogroup spantree
alpar@758
    22
  /// @{
alpar@758
    23
alpar@737
    24
  /// Kruskal's algorithm to find a minimum cost tree of a graph.
alpar@737
    25
alpar@737
    26
  /// This function runs Kruskal's algorithm to find a minimum cost tree.
alpar@737
    27
  /// \param G The graph the algorithm runs on.
alpar@737
    28
  /// \param in This object is used to describe the edge costs. It must
alpar@737
    29
  /// be an STL 'forward container'
alpar@737
    30
  /// with value_type <tt> std::pair<Graph::Edge,X> </tt>,
alpar@737
    31
  /// where X is the type of the costs. It must contain every edge in
alpar@737
    32
  /// cost-ascending order.
alpar@737
    33
  /// \retval out This must be a writeable EdgeMap. After running the algorithm
alpar@737
    34
  /// this will contain the found minimum cost spanning tree: the value of an
alpar@737
    35
  /// edge will be set to \c true if it belongs to the tree, otherwise it will
alpar@737
    36
  /// be set to \c false. The value of each edge will be set exactly once.\n
alpar@737
    37
  /// For the sake of simplicity, there is a helper class KruskalPairVec,
alpar@737
    38
  /// which converts a
alpar@737
    39
  /// simple EdgeMap to an input of this form. Alternatively, you can use
alpar@737
    40
  /// the function \ref kruskalEdgeMap to compute the minimum cost tree if
alpar@737
    41
  /// the edge costs are given by an EdgeMap.
alpar@737
    42
  /// \return The cost of the found tree.
beckerjc@150
    43
beckerjc@349
    44
  template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
alpar@737
    45
  typename InputEdgeOrder::value_type::second_type
alpar@737
    46
  kruskal(Graph const& G, InputEdgeOrder const& in, 
alpar@737
    47
		 OutBoolMap& out)
beckerjc@349
    48
  {
alpar@737
    49
    typedef typename InputEdgeOrder::value_type::second_type EdgeCost;
alpar@737
    50
    typedef typename Graph::template NodeMap<int> NodeIntMap;
beckerjc@349
    51
    typedef typename Graph::Node Node;
beckerjc@246
    52
alpar@737
    53
    NodeIntMap comp(G, -1);
alpar@737
    54
    UnionFind<Node,NodeIntMap> uf(comp); 
beckerjc@349
    55
      
beckerjc@349
    56
    EdgeCost tot_cost = 0;
alpar@737
    57
    for (typename InputEdgeOrder::const_iterator p = in.begin(); 
alpar@737
    58
	 p!=in.end(); ++p ) {
alpar@737
    59
      if ( uf.join(G.head((*p).first),
alpar@737
    60
		   G.tail((*p).first)) ) {
alpar@737
    61
	out.set((*p).first, true);
alpar@737
    62
	tot_cost += (*p).second;
beckerjc@349
    63
      }
beckerjc@349
    64
      else {
alpar@737
    65
	out.set((*p).first, false);
beckerjc@349
    66
      }
beckerjc@349
    67
    }
beckerjc@349
    68
    return tot_cost;
beckerjc@349
    69
  }
beckerjc@246
    70
beckerjc@352
    71
  /* A work-around for running Kruskal with const-reference bool maps... */
beckerjc@352
    72
beckerjc@352
    73
  template<typename Map>
beckerjc@352
    74
  class NonConstMapWr {
beckerjc@352
    75
    const Map &m;
beckerjc@352
    76
  public:
beckerjc@352
    77
    typedef typename Map::ValueType ValueType;
beckerjc@352
    78
beckerjc@352
    79
    NonConstMapWr(const Map &_m) : m(_m) {}
beckerjc@352
    80
beckerjc@352
    81
    template<typename KeyType>
beckerjc@352
    82
    void set(KeyType const& k, ValueType const &v) const { m.set(k,v); }
beckerjc@352
    83
  };
beckerjc@352
    84
beckerjc@352
    85
  template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
beckerjc@352
    86
  inline
beckerjc@352
    87
  typename InputEdgeOrder::ValueType
alpar@737
    88
  kruskal(Graph const& G, InputEdgeOrder const& edges, 
beckerjc@352
    89
	  OutBoolMap const& out_map)
beckerjc@352
    90
  {
beckerjc@352
    91
    NonConstMapWr<OutBoolMap> map_wr(out_map);
alpar@737
    92
    return kruskal(G, edges, map_wr);
beckerjc@352
    93
  }  
beckerjc@246
    94
beckerjc@349
    95
  
beckerjc@349
    96
  /* ** ** Output-objektumok: egyszeruen extra bool mapek ** ** */
beckerjc@349
    97
  
beckerjc@349
    98
  /// A writable bool-map that makes a sequence of "true" keys
beckerjc@246
    99
alpar@737
   100
  /// A writable bool-map that creates a sequence out of keys that receives
beckerjc@349
   101
  /// the value "true".
beckerjc@349
   102
  /// \warning Not a regular property map, as it doesn't know its KeyType
beckerjc@246
   103
beckerjc@349
   104
  template<typename Iterator>
beckerjc@349
   105
  class SequenceOutput {
beckerjc@352
   106
    mutable Iterator it;
beckerjc@150
   107
beckerjc@218
   108
  public:
beckerjc@349
   109
    typedef bool ValueType;
beckerjc@150
   110
beckerjc@349
   111
    SequenceOutput(Iterator const &_it) : it(_it) {}
beckerjc@150
   112
beckerjc@349
   113
    template<typename KeyType>
beckerjc@352
   114
    void set(KeyType const& k, bool v) const { if(v) {*it=k; ++it;} }
beckerjc@218
   115
  };
beckerjc@150
   116
beckerjc@349
   117
  template<typename Iterator>
beckerjc@349
   118
  inline
beckerjc@349
   119
  SequenceOutput<Iterator>
beckerjc@349
   120
  makeSequenceOutput(Iterator it) {
beckerjc@349
   121
    return SequenceOutput<Iterator>(it);
beckerjc@349
   122
  }
beckerjc@246
   123
beckerjc@246
   124
  /* ** ** InputSource -ok ** ** */
beckerjc@246
   125
alpar@737
   126
  /// Kruskal input source.
beckerjc@246
   127
alpar@737
   128
  /// Kruskal input source.
alpar@737
   129
  ///
alpar@737
   130
  template<typename Graph, typename Map>
alpar@755
   131
  class KruskalMapInput
alpar@737
   132
    : public std::vector< std::pair<typename Graph::Edge,
alpar@737
   133
				    typename Map::ValueType> > {
alpar@737
   134
    
beckerjc@246
   135
  public:
alpar@737
   136
    typedef std::vector< std::pair<typename Graph::Edge,
alpar@737
   137
				   typename Map::ValueType> > Parent;
alpar@737
   138
    typedef typename Parent::value_type value_type;
alpar@737
   139
//     typedef Key KeyType;
alpar@737
   140
//     typedef Val ValueType;
alpar@737
   141
//     typedef std::pair<Key,Val> PairType;
alpar@737
   142
//     typedef typename Parent::iterator iterator;
alpar@737
   143
//     typedef typename Parent::const_iterator const_iterator;
beckerjc@246
   144
beckerjc@246
   145
  private:
beckerjc@246
   146
    class comparePair {
beckerjc@246
   147
    public:
alpar@737
   148
      bool operator()(const value_type& a,
alpar@737
   149
		      const value_type& b) {
beckerjc@246
   150
	return a.second < b.second;
beckerjc@246
   151
      }
beckerjc@246
   152
    };
beckerjc@246
   153
beckerjc@246
   154
  public:
beckerjc@246
   155
beckerjc@246
   156
    // FIXME: kell ez?
alpar@755
   157
    // KruskalMapInput(Parent const& p) : Parent(p) {}
beckerjc@246
   158
    
beckerjc@246
   159
    void sort() {
alpar@737
   160
      std::sort(this->begin(), this->end(), comparePair());
beckerjc@246
   161
    }
beckerjc@246
   162
beckerjc@246
   163
    // FIXME: nem nagyon illik ez ide...
alpar@755
   164
    KruskalMapInput(Graph const& G, Map const& m) {
beckerjc@246
   165
      typedef typename Graph::EdgeIt EdgeIt;
alpar@737
   166
      
alpar@737
   167
      this->clear();
alpar@737
   168
      for(EdgeIt e(G);G.valid(e);G.next(e)) {
alpar@737
   169
	// for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
beckerjc@246
   170
	push_back(make_pair(e, m[e]));
beckerjc@246
   171
      }
beckerjc@246
   172
      sort();
beckerjc@246
   173
    }
beckerjc@246
   174
alpar@737
   175
//     Key const& first(const_iterator i) const { return i->first; }
alpar@737
   176
//     Key& first(iterator i) { return i->first; }
beckerjc@246
   177
alpar@737
   178
//     Val const& second(const_iterator i) const { return i->second; }
alpar@737
   179
//     Val& second(iterator i) { return i->second; }
beckerjc@246
   180
  };
beckerjc@246
   181
beckerjc@349
   182
alpar@755
   183
//   template<typename Graph, typename Map>
alpar@755
   184
//   class KruskalMapVec {
alpar@737
   185
//   public:
alpar@737
   186
    
alpar@755
   187
//     typedef std::pair<typename Map::KeyType, Map::ValueType> value_type;
alpar@755
   188
    
alpar@755
   189
//     typedef std::vector<KeyType> Container;
alpar@755
   190
//     Container container;
alpar@755
   191
//     std::vector<typename Map::KeyType> container
alpar@755
   192
//     const Map &m;
alpar@755
   193
    
alpar@755
   194
    
alpar@755
   195
//     class iterator
alpar@755
   196
//     {
alpar@755
   197
//       Container::iterator i;
alpar@755
   198
//     public:
alpar@755
   199
//       iterator &operator ++() {++i;return *this;}
alpar@755
   200
//       valuetype operator *() {return value_type(container(i),m[container(i)]);}
alpar@755
   201
//       bool operator==(iterator b) {return i==b.i;}
alpar@755
   202
//       iterator() {}
alpar@755
   203
//       iterator(Container::iterator _i) i(_i) {}
alpar@755
   204
//     };
alpar@755
   205
//     class const_iterator
alpar@755
   206
//     {
alpar@755
   207
//       Container::const_iterator i;
alpar@755
   208
//     public:
alpar@755
   209
//       iterator &operator ++() {++i;return *this;}
alpar@755
   210
//       valuetype operator *() {return value_type(container(i),m[container(i)]);}
alpar@755
   211
//       bool operator==(iterator b) {return i==b.i;}
alpar@755
   212
//       const_iterator() {}
alpar@755
   213
//       const_iterator(Container::iterator _i) i(_i) {}
alpar@755
   214
//     };
beckerjc@349
   215
alpar@755
   216
//     iterator begin() { return iterator(container.begin());}
alpar@755
   217
//     const_iterator begin() const { return iterator(container.begin());}
alpar@755
   218
//     iterator end() { return iterator(container.end());}
alpar@755
   219
//     const_iterator end() const { return iterator(container.end());}
alpar@755
   220
    
alpar@737
   221
//   private:
alpar@755
   222
    
alpar@737
   223
//     class compareKeys {
alpar@737
   224
//       const Map &m;
alpar@737
   225
//     public:
alpar@737
   226
//       compareKeys(Map const &_m) : m(_m) {}
alpar@737
   227
//       bool operator()(KeyType const& a, KeyType const& b) {
alpar@737
   228
// 	return m[a] < m[b];
alpar@737
   229
//       }
alpar@737
   230
//     };
beckerjc@349
   231
alpar@737
   232
//   public:
beckerjc@349
   233
alpar@737
   234
//     KruskalMapVec(Map const& _m) : m(_m) {}
beckerjc@349
   235
alpar@737
   236
//     void sort() {
alpar@737
   237
//       std::sort(begin(), end(), compareKeys(m));
alpar@737
   238
//     }
beckerjc@349
   239
alpar@737
   240
//     // FIXME: nem nagyon illik ez ide...
alpar@737
   241
//     template<typename Graph>
alpar@737
   242
//     KruskalMapVec(Graph const& G, Map const& _m) : m(_m) {
alpar@737
   243
//       typedef typename Graph::EdgeIt EdgeIt;
beckerjc@349
   244
alpar@737
   245
//       clear();
alpar@737
   246
//       for(EdgeIt e(G);G.valid(e);G.next(e)) {
alpar@737
   247
//       // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) 
alpar@737
   248
// 	push_back(e);
alpar@737
   249
//       }
alpar@737
   250
//       sort();
alpar@737
   251
//     }
beckerjc@349
   252
alpar@737
   253
//     KeyType const& first(const_iterator i) const { return *i; }
alpar@737
   254
//     KeyType& first(iterator i) { return *i; }
beckerjc@349
   255
alpar@737
   256
//     ValueType const& second(const_iterator i) const { return m[*i]; }
alpar@737
   257
//     ValueType& second(iterator i) { return m[*i]; }
alpar@737
   258
//   };
beckerjc@349
   259
alpar@755
   260
beckerjc@246
   261
  /* ** ** Wrapper fuggvenyek ** ** */
beckerjc@246
   262
beckerjc@349
   263
beckerjc@349
   264
  /// \brief Wrapper to Kruskal().
beckerjc@349
   265
  /// Input is from an EdgeMap, output is a plain boolmap.
alpar@737
   266
alpar@737
   267
  ///\todo some more words would be nice here.
alpar@737
   268
  ///
beckerjc@246
   269
  template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
beckerjc@352
   270
  inline
beckerjc@246
   271
  typename EdgeCostMap::ValueType
alpar@737
   272
  kruskalEdgeMap(Graph const& G,
alpar@737
   273
			EdgeCostMap const& edge_costs,
alpar@737
   274
			RetEdgeBoolMap &ret_bool_map) {
alpar@737
   275
    
alpar@755
   276
    typedef KruskalMapInput<Graph,EdgeCostMap> InputVec;
alpar@737
   277
    
beckerjc@349
   278
    InputVec iv(G, edge_costs);
alpar@737
   279
    return kruskal(G, iv, ret_bool_map);
beckerjc@246
   280
  }
beckerjc@246
   281
beckerjc@349
   282
beckerjc@349
   283
  /// \brief Wrapper to Kruskal().
beckerjc@349
   284
  /// Input is from an EdgeMap, output is to a sequence.
alpar@737
   285
alpar@737
   286
  ///\todo it does not follow the naming convention.
alpar@737
   287
  ///
beckerjc@246
   288
  template <typename Graph, typename EdgeCostMap, typename RetIterator>
beckerjc@352
   289
  inline
beckerjc@246
   290
  typename EdgeCostMap::ValueType
alpar@737
   291
  kruskalEdgeMap_IteratorOut(const Graph& G,
alpar@737
   292
			     const EdgeCostMap& edge_costs,
alpar@737
   293
			     RetIterator ret_iterator)
alpar@737
   294
  {
alpar@737
   295
    typedef typename EdgeCostMap::ValueType ValueType;
alpar@737
   296
    
beckerjc@349
   297
    typedef SequenceOutput<RetIterator> OutMap;
beckerjc@349
   298
    OutMap out(ret_iterator);
beckerjc@246
   299
alpar@755
   300
    typedef KruskalMapInput<Graph, EdgeCostMap> InputVec;
alpar@737
   301
beckerjc@349
   302
    InputVec iv(G, edge_costs);
beckerjc@246
   303
alpar@737
   304
    return kruskal(G, iv, out);
beckerjc@246
   305
  }
beckerjc@246
   306
alpar@758
   307
  /// @}
beckerjc@150
   308
beckerjc@150
   309
} //namespace hugo
beckerjc@150
   310
beckerjc@150
   311
#endif //HUGO_KRUSKAL_H