COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/johanna/kruskal.h @ 755:a8c2e828ce0b

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