COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/johanna/kruskal.h @ 408:cc8629dc2935

Last change on this file since 408:cc8629dc2935 was 394:3a34c5626e52, checked in by beckerjc, 20 years ago

New union-find structure with enumerable classes.

File size: 6.1 KB
RevLine 
[150]1// -*- c++ -*- //
2#ifndef HUGO_KRUSKAL_H
3#define HUGO_KRUSKAL_H
4
5#include <algorithm>
[349]6#include <unionfind.h>
7#include <for_each_macros.h>
[150]8
9namespace hugo {
10
[349]11  /// Kruskal's algorithm to compute a minimum cost tree
[150]12
[349]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;
[246]21
[349]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 ) {
[394]28      if ( uf.join(G.head(edges.first(p)),
[349]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  }
[246]39
[352]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  } 
[246]63
[349]64 
65  /* ** ** Output-objektumok: egyszeruen extra bool mapek ** ** */
66 
67  /// A writable bool-map that makes a sequence of "true" keys
[246]68
[349]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
[246]72
[349]73  template<typename Iterator>
74  class SequenceOutput {
[352]75    mutable Iterator it;
[150]76
[218]77  public:
[349]78    typedef bool ValueType;
[150]79
[349]80    SequenceOutput(Iterator const &_it) : it(_it) {}
[150]81
[349]82    template<typename KeyType>
[352]83    void set(KeyType const& k, bool v) const { if(v) {*it=k; ++it;} }
[218]84  };
[150]85
[349]86  template<typename Iterator>
87  inline
88  SequenceOutput<Iterator>
89  makeSequenceOutput(Iterator it) {
90    return SequenceOutput<Iterator>(it);
91  }
[246]92
93  /* ** ** InputSource -ok ** ** */
94
95  template<typename Key, typename Val>
[349]96  class KruskalPairVec : public std::vector< std::pair<Key,Val> > {
[246]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?
[349]118    // KruskalPairVec(Parent const& p) : Parent(p) {}
[246]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>
[349]126    KruskalPairVec(Graph const& G, Map const& m) {
[246]127      typedef typename Graph::EdgeIt EdgeIt;
128
129      clear();
[349]130      FOR_EACH_LOC(EdgeIt, e, G) {
131      // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
[246]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
[349]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
[246]197  /* ** ** Wrapper fuggvenyek ** ** */
198
[349]199
200  /// \brief Wrapper to Kruskal().
201  /// Input is from an EdgeMap, output is a plain boolmap.
[246]202  template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
[352]203  inline
[246]204  typename EdgeCostMap::ValueType
[349]205  Kruskal_EdgeCostMapIn_BoolMapOut(Graph const& G,
206                                   EdgeCostMap const& edge_costs,
207                                   RetEdgeBoolMap &ret_bool_map) {
[246]208
[349]209    typedef KruskalPairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
[246]210      InputVec;
[349]211    InputVec iv(G, edge_costs);
[246]212
[349]213    return Kruskal(G, iv, ret_bool_map);
[246]214  }
215
[349]216
217  /// \brief Wrapper to Kruskal().
218  /// Input is from an EdgeMap, output is to a sequence.
[246]219  template <typename Graph, typename EdgeCostMap, typename RetIterator>
[352]220  inline
[246]221  typename EdgeCostMap::ValueType
[349]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);
[246]227
[349]228    typedef KruskalPairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
[246]229      InputVec;
[349]230    InputVec iv(G, edge_costs);
[246]231
[349]232    return Kruskal(G, iv, out);
[246]233  }
234
[150]235
236} //namespace hugo
237
238#endif //HUGO_KRUSKAL_H
Note: See TracBrowser for help on using the repository browser.