COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/johanna/kruskal.h @ 336:8ff3b3e05478

Last change on this file since 336:8ff3b3e05478 was 246:dc95ca4ebc7b, checked in by beckerjc, 20 years ago

koztes valtozat

File size: 6.8 KB
Line 
1// -*- c++ -*- //
2#ifndef HUGO_KRUSKAL_H
3#define HUGO_KRUSKAL_H
4
5#include "unionfind.h"
6#include <algorithm>
7
8namespace hugo {
9
10  template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
11  typename EdgeCostMap::ValueType
12  kruskal1(Graph const& G, EdgeCostMap const& edge_costs,
13           RetEdgeBoolMap &ret_bool_map);
14
15  template <typename Graph, typename EdgeCostMap, typename RetIterator>
16  typename EdgeCostMap::ValueType
17  kruskal2(Graph const& G, EdgeCostMap const& edge_costs,
18           RetIterator ret_iterator);
19
20  // FIXME: ret_iterator nem lehet referencia!!!
21
22  template <typename Graph, typename EdgeCostPairVec, typename RetEdgeBoolMap>
23  typename EdgeCostPairVec::value_type::second_type
24  kruskal3(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec,
25           RetEdgeBoolMap &ret_bool_map);
26
27  template <typename Graph, typename EdgeCostPairVec, typename RetIterator>
28  typename EdgeCostPairVec::value_type::second_type
29  kruskal4(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec,
30           RetIterator &ret_iterator);
31
32  template <typename Graph, typename EdgePairVec, typename RetEdgeBoolMap>
33  int
34  kruskal5(Graph const& G, EdgePairVec const& edge_pair_vec,
35           RetEdgeBoolMap &ret_bool_map);
36
37  template <typename Graph, typename EdgePairVec, typename RetIterator>
38  int
39  kruskal6(Graph const& G, EdgePairVec const& edge_pair_vec,
40           RetIterator &ret_iterator);
41
42
43  template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap,
44            typename RetIterator>
45  typename EdgeCostMap::ValueType
46  kruskal7(Graph const& G, EdgeCostMap const& edge_costs,
47           RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator);
48
49  template <typename Graph, typename EdgeCostPairVec, typename RetEdgeBoolMap,
50            typename RetIterator>
51  typename EdgeCostPairVec::value_type::second_type
52  kruskal8(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec,
53           RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator);
54
55  template <typename Graph, typename EdgePairVec, typename RetEdgeBoolMap,
56            typename RetIterator>
57  int
58  kruskal9(Graph const& G, EdgePairVec const& edge_pair_vec,
59           RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator);
60
61
62
63
64  template <typename Graph, typename InputEdgeOrder, typename OutputObserver>
65  class MinCostTreeKruskal
66  {
67
68    typedef typename Graph::EdgeIt EdgeIt;
69    typedef typename Graph::Edge Edge;
70
71  public:
72    typedef typename InputEdgeOrder::ValueType EdgeCost;
73   
74  private:
75    Graph const &G;
76    InputEdgeOrder const &edges;
77    OutputObserver &out_obs;
78
79  public:
80
81
82    MinCostTreeKruskal(Graph const& _G, InputEdgeOrder const& _edges,
83                       OutputObserver& _out_obs) :
84      G(_G), edges(_edges), out_obs(_out_obs) {}
85 
86
87    EdgeCost run()
88    {
89      typedef typename Graph::NodeMap<int> NodeIntMap;
90      typedef typename Graph::Node Node;
91      NodeIntMap comp_map(G, -1);
92      UnionFind<Node,NodeIntMap> uf(comp_map);
93     
94      EdgeCost tot_cost = 0;
95      for (typename InputEdgeOrder::const_iterator p = edges.begin();
96           p!=edges.end(); ++p ) {
97        if ( uf.joinComponents(G.head(edges.first(p)),
98                               G.tail(edges.first(p))) ) {
99          out_obs.setTrue(edges.first(p));
100          tot_cost += edges.second(p);
101        }
102        else {
103          out_obs.setFalse(edges.first(p));
104        }
105      }
106      return tot_cost;
107    }
108
109  };
110
111 
112  /* ** ** Output-objektumok (Observerek (?)) ** ** */
113 
114  template <typename BoolMap>
115  class BoolMapOutput {
116    BoolMap &bm;
117    typedef typename BoolMap::KeyType KeyType;
118
119  public:
120    BoolMapOutput(BoolMap &_bm) : bm(_bm) {}
121
122    void setTrue(KeyType const& k) { bm.set(k, true); }
123    void setFalse(KeyType const& k) { bm.set(k, false); }
124  };
125
126  template <typename Iterator>
127  class SequenceOutput {
128    Iterator &it;
129
130  public:
131    SequenceOutput(Iterator &_it) : it(_it) {}
132
133    template<typename KeyType>
134    void setTrue(KeyType const& k) { *it=k; ++it; }
135    template<typename KeyType>
136    void setFalse(KeyType const& k) {}
137  };
138
139  template <typename BoolMap, typename Iterator>
140  class CombinedOutput : BoolMapOutput<BoolMap>, SequenceOutput<Iterator> {
141    typedef BoolMapOutput<BoolMap> BMO;
142    typedef SequenceOutput<Iterator> SO;
143  public:
144    CombinedOutput(BoolMap &_bm, Iterator &_it) :
145      BMO(_bm), SO(_it) {}
146
147    template<typename KeyType>
148    void setTrue(KeyType const& k) {
149      BMO::setTrue(k);
150      SO::setTrue(k);
151    }
152    template<typename KeyType>
153    void setFalse(KeyType const& k) {
154      BMO::setFalse(k);
155      SO::setFalse(k);     
156    }
157  };
158
159
160  /* ** ** InputSource -ok ** ** */
161
162  template<typename Key, typename Val>
163  class PairVec : public std::vector< std::pair<Key,Val> > {
164
165  public:
166    typedef std::vector< std::pair<Key,Val> > Parent;
167    typedef Key KeyType;
168    typedef Val ValueType;
169    typedef std::pair<Key,Val> PairType;
170
171    typedef typename Parent::iterator iterator;
172    typedef typename Parent::const_iterator const_iterator;
173
174
175  private:
176
177    class comparePair {
178    public:
179      bool operator()(PairType const& a, PairType const& b) {
180        return a.second < b.second;
181      }
182    };
183
184  public:
185
186    // FIXME: kell ez?
187    // PairVec(Parent const& p) : Parent(p) {}
188   
189    void sort() {
190      std::sort(begin(), end(), comparePair());
191    }
192
193    // FIXME: nem nagyon illik ez ide...
194    template<typename Graph, typename Map>
195    void readGraphEdgeMap(Graph const& G, Map const& m) {
196      typedef typename Graph::EdgeIt EdgeIt;
197
198      clear();
199      for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
200        push_back(make_pair(e, m[e]));
201      }
202
203      sort();
204    }
205
206    int alma() { return 5; /* FIXME */ }
207
208    Key const& first(const_iterator i) const { return i->first; }
209    Key& first(iterator i) { return i->first; }
210
211    Val const& second(const_iterator i) const { return i->second; }
212    Val& second(iterator i) { return i->second; }
213  };
214
215  /* ** ** Wrapper fuggvenyek ** ** */
216
217  template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
218  typename EdgeCostMap::ValueType
219  kruskal1(Graph const& G, EdgeCostMap const& edge_costs,
220           RetEdgeBoolMap &ret_bool_map) {
221    typedef BoolMapOutput<RetEdgeBoolMap> OutObs;
222    OutObs out(ret_bool_map);
223
224    typedef PairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
225      InputVec;
226    InputVec iv;
227    iv.readGraphEdgeMap(G, edge_costs);
228
229    MinCostTreeKruskal<Graph,InputVec,OutObs> mctk(G, iv, out);
230    return mctk.run();
231  }
232
233  template <typename Graph, typename EdgeCostMap, typename RetIterator>
234  typename EdgeCostMap::ValueType
235  kruskal2(Graph const& G, EdgeCostMap const& edge_costs,
236           RetIterator ret_iterator) {
237    typedef SequenceOutput<RetIterator> OutObs;
238    OutObs out(ret_iterator);
239
240    typedef PairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
241      InputVec;
242    InputVec iv;
243    iv.readGraphEdgeMap(G, edge_costs);
244
245    MinCostTreeKruskal<Graph,InputVec,OutObs> mctk(G, iv, out);
246    return mctk.run();   
247  }
248
249
250} //namespace hugo
251
252#endif //HUGO_KRUSKAL_H
Note: See TracBrowser for help on using the repository browser.