# source:lemon-0.x/src/work/johanna/kruskal.h@682:1ea8162ce638

Last change on this file since 682:1ea8162ce638 was 682:1ea8162ce638, checked in by Alpar Juttner, 19 years ago

doc

File size: 6.2 KB
Line
1// -*- c++ -*- //
2#ifndef HUGO_KRUSKAL_H
3#define HUGO_KRUSKAL_H
4
5#include <algorithm>
6#include <unionfind.h>
7#include <for_each_macros.h>
8
9///\file
10///\brief Kruskal's algorithm to compute a minimum cost tree
11
12namespace hugo {
13
14  /// Kruskal's algorithm to compute a minimum cost tree
15
16  template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
17  typename InputEdgeOrder::ValueType
18  Kruskal(Graph const& G, InputEdgeOrder const& edges,
19          OutBoolMap& out_map)
20  {
21    typedef typename InputEdgeOrder::ValueType EdgeCost;
22    typedef typename Graph::NodeMap<int> NodeIntMap;
23    typedef typename Graph::Node Node;
24
25    NodeIntMap comp_map(G, -1);
26    UnionFind<Node,NodeIntMap> uf(comp_map);
27
28    EdgeCost tot_cost = 0;
29    for (typename InputEdgeOrder::const_iterator p = edges.begin();
30         p!=edges.end(); ++p ) {
32                             G.tail(edges.first(p))) ) {
33        out_map.set(edges.first(p), true);
34        tot_cost += edges.second(p);
35      }
36      else {
37        out_map.set(edges.first(p), false);
38      }
39    }
41  }
42
43  /* A work-around for running Kruskal with const-reference bool maps... */
44
45  template<typename Map>
46  class NonConstMapWr {
47    const Map &m;
48  public:
49    typedef typename Map::ValueType ValueType;
50
51    NonConstMapWr(const Map &_m) : m(_m) {}
52
53    template<typename KeyType>
54    void set(KeyType const& k, ValueType const &v) const { m.set(k,v); }
55  };
56
57  template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
58  inline
59  typename InputEdgeOrder::ValueType
60  Kruskal(Graph const& G, InputEdgeOrder const& edges,
61          OutBoolMap const& out_map)
62  {
63    NonConstMapWr<OutBoolMap> map_wr(out_map);
64    return Kruskal(G, edges, map_wr);
65  }
66
67
68  /* ** ** Output-objektumok: egyszeruen extra bool mapek ** ** */
69
70  /// A writable bool-map that makes a sequence of "true" keys
71
72  /// A writable bool-map that creates a sequence out of keys that receive
73  /// the value "true".
74  /// \warning Not a regular property map, as it doesn't know its KeyType
75
76  template<typename Iterator>
77  class SequenceOutput {
78    mutable Iterator it;
79
80  public:
81    typedef bool ValueType;
82
83    SequenceOutput(Iterator const &_it) : it(_it) {}
84
85    template<typename KeyType>
86    void set(KeyType const& k, bool v) const { if(v) {*it=k; ++it;} }
87  };
88
89  template<typename Iterator>
90  inline
91  SequenceOutput<Iterator>
92  makeSequenceOutput(Iterator it) {
93    return SequenceOutput<Iterator>(it);
94  }
95
96  /* ** ** InputSource -ok ** ** */
97
98  template<typename Key, typename Val>
99  class KruskalPairVec : public std::vector< std::pair<Key,Val> > {
100
101  public:
102    typedef std::vector< std::pair<Key,Val> > Parent;
103    typedef Key KeyType;
104    typedef Val ValueType;
105    typedef std::pair<Key,Val> PairType;
106
107    typedef typename Parent::iterator iterator;
108    typedef typename Parent::const_iterator const_iterator;
109
110  private:
111    class comparePair {
112    public:
113      bool operator()(PairType const& a, PairType const& b) {
114        return a.second < b.second;
115      }
116    };
117
118  public:
119
120    // FIXME: kell ez?
121    // KruskalPairVec(Parent const& p) : Parent(p) {}
122
123    void sort() {
124      std::sort(begin(), end(), comparePair());
125    }
126
127    // FIXME: nem nagyon illik ez ide...
128    template<typename Graph, typename Map>
129    KruskalPairVec(Graph const& G, Map const& m) {
130      typedef typename Graph::EdgeIt EdgeIt;
131
132      clear();
133      FOR_EACH_LOC(EdgeIt, e, G) {
134      // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
135        push_back(make_pair(e, m[e]));
136      }
137      sort();
138    }
139
140    Key const& first(const_iterator i) const { return i->first; }
141    Key& first(iterator i) { return i->first; }
142
143    Val const& second(const_iterator i) const { return i->second; }
144    Val& second(iterator i) { return i->second; }
145  };
146
147
148  template <typename Map>
149  class KruskalMapVec : public std::vector<typename Map::KeyType> {
150  public:
151
152    typedef typename Map::KeyType KeyType;
153    typedef typename Map::ValueType ValueType;
154
155    typedef typename std::vector<KeyType> Parent;
156    typedef typename Parent::iterator iterator;
157    typedef typename Parent::const_iterator const_iterator;
158
159  private:
160
161    const Map &m;
162
163    class compareKeys {
164      const Map &m;
165    public:
166      compareKeys(Map const &_m) : m(_m) {}
167      bool operator()(KeyType const& a, KeyType const& b) {
168        return m[a] < m[b];
169      }
170    };
171
172  public:
173
174    KruskalMapVec(Map const& _m) : m(_m) {}
175
176    void sort() {
177      std::sort(begin(), end(), compareKeys(m));
178    }
179
180    // FIXME: nem nagyon illik ez ide...
181    template<typename Graph>
182    KruskalMapVec(Graph const& G, Map const& _m) : m(_m) {
183      typedef typename Graph::EdgeIt EdgeIt;
184
185      clear();
186      FOR_EACH_LOC(EdgeIt, e, G) {
187      // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
188        push_back(e);
189      }
190      sort();
191    }
192
193    KeyType const& first(const_iterator i) const { return *i; }
194    KeyType& first(iterator i) { return *i; }
195
196    ValueType const& second(const_iterator i) const { return m[*i]; }
197    ValueType& second(iterator i) { return m[*i]; }
198  };
199
200  /* ** ** Wrapper fuggvenyek ** ** */
201
202
203  /// \brief Wrapper to Kruskal().
204  /// Input is from an EdgeMap, output is a plain boolmap.
205  template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
206  inline
207  typename EdgeCostMap::ValueType
208  Kruskal_EdgeCostMapIn_BoolMapOut(Graph const& G,
209                                   EdgeCostMap const& edge_costs,
210                                   RetEdgeBoolMap &ret_bool_map) {
211
212    typedef KruskalPairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
213      InputVec;
214    InputVec iv(G, edge_costs);
215
216    return Kruskal(G, iv, ret_bool_map);
217  }
218
219
220  /// \brief Wrapper to Kruskal().
221  /// Input is from an EdgeMap, output is to a sequence.
222  template <typename Graph, typename EdgeCostMap, typename RetIterator>
223  inline
224  typename EdgeCostMap::ValueType
225  Kruskal_EdgeCostMapIn_IteratorOut(Graph const& G,
226                                    EdgeCostMap const& edge_costs,
227                                    RetIterator ret_iterator) {
228    typedef SequenceOutput<RetIterator> OutMap;
229    OutMap out(ret_iterator);
230
231    typedef KruskalPairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
232      InputVec;
233    InputVec iv(G, edge_costs);
234
235    return Kruskal(G, iv, out);
236  }
237
238
239} //namespace hugo
240
241#endif //HUGO_KRUSKAL_H
Note: See TracBrowser for help on using the repository browser.