# source:lemon-0.x/src/work/johanna/kruskal.h@350:3a9a767b841e

Last change on this file since 350:3a9a767b841e was 349:42c660f58702, checked in by beckerjc, 18 years ago

Kruskal lenyegeben kesz.
Kell meg dokumentalni, meg meg egy par jol hasznalhato wrapper fv.
Es valamit meg kene csinalni azzal, hogy nem const ref. a kimeno boolmap,

viszont sokszor "on-the-fly" akarjuk megkonstrualni (es ilyenkor persze a
const-os mapet is lehet set-elni...)

File size: 5.4 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 ) {
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    }
38  }
39
40
41
42  /* ** ** Output-objektumok: egyszeruen extra bool mapek ** ** */
43
44  /// A writable bool-map that makes a sequence of "true" keys
45
46  /// A writable bool-map that creates a sequence out of keys that receive
47  /// the value "true".
48  /// \warning Not a regular property map, as it doesn't know its KeyType
49
50  template<typename Iterator>
51  class SequenceOutput {
52    Iterator it;
53
54  public:
55    typedef bool ValueType;
56
57    SequenceOutput(Iterator const &_it) : it(_it) {}
58
59    template<typename KeyType>
60    void set(KeyType const& k, bool v) { if(v) {*it=k; ++it;} }
61  };
62
63  template<typename Iterator>
64  inline
65  SequenceOutput<Iterator>
66  makeSequenceOutput(Iterator it) {
67    return SequenceOutput<Iterator>(it);
68  }
69
70  /* ** ** InputSource -ok ** ** */
71
72  template<typename Key, typename Val>
73  class KruskalPairVec : public std::vector< std::pair<Key,Val> > {
74
75  public:
76    typedef std::vector< std::pair<Key,Val> > Parent;
77    typedef Key KeyType;
78    typedef Val ValueType;
79    typedef std::pair<Key,Val> PairType;
80
81    typedef typename Parent::iterator iterator;
82    typedef typename Parent::const_iterator const_iterator;
83
84  private:
85    class comparePair {
86    public:
87      bool operator()(PairType const& a, PairType const& b) {
88        return a.second < b.second;
89      }
90    };
91
92  public:
93
94    // FIXME: kell ez?
95    // KruskalPairVec(Parent const& p) : Parent(p) {}
96
97    void sort() {
98      std::sort(begin(), end(), comparePair());
99    }
100
101    // FIXME: nem nagyon illik ez ide...
102    template<typename Graph, typename Map>
103    KruskalPairVec(Graph const& G, Map const& m) {
104      typedef typename Graph::EdgeIt EdgeIt;
105
106      clear();
107      FOR_EACH_LOC(EdgeIt, e, G) {
108      // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
109        push_back(make_pair(e, m[e]));
110      }
111      sort();
112    }
113
114    Key const& first(const_iterator i) const { return i->first; }
115    Key& first(iterator i) { return i->first; }
116
117    Val const& second(const_iterator i) const { return i->second; }
118    Val& second(iterator i) { return i->second; }
119  };
120
121
122  template <typename Map>
123  class KruskalMapVec : public std::vector<typename Map::KeyType> {
124  public:
125
126    typedef typename Map::KeyType KeyType;
127    typedef typename Map::ValueType ValueType;
128
129    typedef typename std::vector<KeyType> Parent;
130    typedef typename Parent::iterator iterator;
131    typedef typename Parent::const_iterator const_iterator;
132
133  private:
134
135    const Map &m;
136
137    class compareKeys {
138      const Map &m;
139    public:
140      compareKeys(Map const &_m) : m(_m) {}
141      bool operator()(KeyType const& a, KeyType const& b) {
142        return m[a] < m[b];
143      }
144    };
145
146  public:
147
148    KruskalMapVec(Map const& _m) : m(_m) {}
149
150    void sort() {
151      std::sort(begin(), end(), compareKeys(m));
152    }
153
154    // FIXME: nem nagyon illik ez ide...
155    template<typename Graph>
156    KruskalMapVec(Graph const& G, Map const& _m) : m(_m) {
157      typedef typename Graph::EdgeIt EdgeIt;
158
159      clear();
160      FOR_EACH_LOC(EdgeIt, e, G) {
161      // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
162        push_back(e);
163      }
164      sort();
165    }
166
167    KeyType const& first(const_iterator i) const { return *i; }
168    KeyType& first(iterator i) { return *i; }
169
170    ValueType const& second(const_iterator i) const { return m[*i]; }
171    ValueType& second(iterator i) { return m[*i]; }
172  };
173
174  /* ** ** Wrapper fuggvenyek ** ** */
175
176
177  /// \brief Wrapper to Kruskal().
178  /// Input is from an EdgeMap, output is a plain boolmap.
179  template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
180  typename EdgeCostMap::ValueType
181  Kruskal_EdgeCostMapIn_BoolMapOut(Graph const& G,
182                                   EdgeCostMap const& edge_costs,
183                                   RetEdgeBoolMap &ret_bool_map) {
184
185    typedef KruskalPairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
186      InputVec;
187    InputVec iv(G, edge_costs);
188
189    return Kruskal(G, iv, ret_bool_map);
190  }
191
192
193  /// \brief Wrapper to Kruskal().
194  /// Input is from an EdgeMap, output is to a sequence.
195  template <typename Graph, typename EdgeCostMap, typename RetIterator>
196  typename EdgeCostMap::ValueType
197  Kruskal_EdgeCostMapIn_IteratorOut(Graph const& G,
198                                    EdgeCostMap const& edge_costs,
199                                    RetIterator ret_iterator) {
200    typedef SequenceOutput<RetIterator> OutMap;
201    OutMap out(ret_iterator);
202
203    typedef KruskalPairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
204      InputVec;
205    InputVec iv(G, edge_costs);
206
207    return Kruskal(G, iv, out);
208  }
209
210
211} //namespace hugo
212
213#endif //HUGO_KRUSKAL_H
Note: See TracBrowser for help on using the repository browser.