# source:lemon-0.x/src/work/johanna/kruskal.h@758:49b1a30c4dc4

Last change on this file since 758:49b1a30c4dc4 was 758:49b1a30c4dc4, checked in by Alpar Juttner, 16 years ago

New Doxygen module for path/flow algs.

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