COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/johanna/kruskal.h @ 558:4cbfb435ec2b

Last change on this file since 558:4cbfb435ec2b was 394:3a34c5626e52, checked in by beckerjc, 17 years ago

New union-find structure with enumerable classes.

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