# source:lemon-0.x/src/work/johanna/kruskal.h@737:2d867176d10e

Last change on this file since 737:2d867176d10e was 737:2d867176d10e, checked in by Alpar Juttner, 20 years ago

Several changes in Kruskal alg.

• Input object interface was changed to an STL compatible one.
• template parameters of class KruskalPairVec? has been simplified.
• (the most of) the names meet the naming conventions.
• a lot of (but still not enough) documentation has been added.
• class KruskalMapVec? has been commented out.
File size: 7.6 KB
Line
1// -*- c++ -*- //
2#ifndef HUGO_KRUSKAL_H
3#define HUGO_KRUSKAL_H
4
5#include <algorithm>
6#include <hugo/unionfind.h>
7
8///\file
9///\brief Kruskal's algorithm to compute a minimum cost tree
10
11namespace hugo {
12
13  /// Kruskal's algorithm to find a minimum cost tree of a graph.
14
15  /// This function runs Kruskal's algorithm to find a minimum cost tree.
16  /// \param G The graph the algorithm runs on.
17  /// \param in This object is used to describe the edge costs. It must
18  /// be an STL 'forward container'
19  /// with value_type <tt> std::pair<Graph::Edge,X> </tt>,
20  /// where X is the type of the costs. It must contain every edge in
21  /// cost-ascending order.
22  /// \retval out This must be a writeable EdgeMap. After running the algorithm
23  /// this will contain the found minimum cost spanning tree: the value of an
24  /// edge will be set to \c true if it belongs to the tree, otherwise it will
25  /// be set to \c false. The value of each edge will be set exactly once.\n
26  /// For the sake of simplicity, there is a helper class KruskalPairVec,
27  /// which converts a
28  /// simple EdgeMap to an input of this form. Alternatively, you can use
29  /// the function \ref kruskalEdgeMap to compute the minimum cost tree if
30  /// the edge costs are given by an EdgeMap.
31  /// \return The cost of the found tree.
32
33  template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
34  typename InputEdgeOrder::value_type::second_type
35  kruskal(Graph const& G, InputEdgeOrder const& in,
36                 OutBoolMap& out)
37  {
38    typedef typename InputEdgeOrder::value_type::second_type EdgeCost;
39    typedef typename Graph::template NodeMap<int> NodeIntMap;
40    typedef typename Graph::Node Node;
41
42    NodeIntMap comp(G, -1);
43    UnionFind<Node,NodeIntMap> uf(comp);
44
45    EdgeCost tot_cost = 0;
46    for (typename InputEdgeOrder::const_iterator p = in.begin();
47         p!=in.end(); ++p ) {
49                   G.tail((*p).first)) ) {
50        out.set((*p).first, true);
51        tot_cost += (*p).second;
52      }
53      else {
54        out.set((*p).first, false);
55      }
56    }
58  }
59
60  /* A work-around for running Kruskal with const-reference bool maps... */
61
62  template<typename Map>
63  class NonConstMapWr {
64    const Map &m;
65  public:
66    typedef typename Map::ValueType ValueType;
67
68    NonConstMapWr(const Map &_m) : m(_m) {}
69
70    template<typename KeyType>
71    void set(KeyType const& k, ValueType const &v) const { m.set(k,v); }
72  };
73
74  template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
75  inline
76  typename InputEdgeOrder::ValueType
77  kruskal(Graph const& G, InputEdgeOrder const& edges,
78          OutBoolMap const& out_map)
79  {
80    NonConstMapWr<OutBoolMap> map_wr(out_map);
81    return kruskal(G, edges, map_wr);
82  }
83
84
85  /* ** ** Output-objektumok: egyszeruen extra bool mapek ** ** */
86
87  /// A writable bool-map that makes a sequence of "true" keys
88
89  /// A writable bool-map that creates a sequence out of keys that receives
90  /// the value "true".
91  /// \warning Not a regular property map, as it doesn't know its KeyType
92
93  template<typename Iterator>
94  class SequenceOutput {
95    mutable Iterator it;
96
97  public:
98    typedef bool ValueType;
99
100    SequenceOutput(Iterator const &_it) : it(_it) {}
101
102    template<typename KeyType>
103    void set(KeyType const& k, bool v) const { if(v) {*it=k; ++it;} }
104  };
105
106  template<typename Iterator>
107  inline
108  SequenceOutput<Iterator>
109  makeSequenceOutput(Iterator it) {
110    return SequenceOutput<Iterator>(it);
111  }
112
113  /* ** ** InputSource -ok ** ** */
114
115  /// Kruskal input source.
116
117  /// Kruskal input source.
118  ///
119  template<typename Graph, typename Map>
120  class KruskalPairVec
121    : public std::vector< std::pair<typename Graph::Edge,
122                                    typename Map::ValueType> > {
123
124  public:
125    typedef std::vector< std::pair<typename Graph::Edge,
126                                   typename Map::ValueType> > Parent;
127    typedef typename Parent::value_type value_type;
128//     typedef Key KeyType;
129//     typedef Val ValueType;
130//     typedef std::pair<Key,Val> PairType;
131//     typedef typename Parent::iterator iterator;
132//     typedef typename Parent::const_iterator const_iterator;
133
134  private:
135    class comparePair {
136    public:
137      bool operator()(const value_type& a,
138                      const value_type& b) {
139        return a.second < b.second;
140      }
141    };
142
143  public:
144
145    // FIXME: kell ez?
146    // KruskalPairVec(Parent const& p) : Parent(p) {}
147
148    void sort() {
149      std::sort(this->begin(), this->end(), comparePair());
150    }
151
152    // FIXME: nem nagyon illik ez ide...
153    KruskalPairVec(Graph const& G, Map const& m) {
154      typedef typename Graph::EdgeIt EdgeIt;
155
156      this->clear();
157      for(EdgeIt e(G);G.valid(e);G.next(e)) {
158        // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
159        push_back(make_pair(e, m[e]));
160      }
161      sort();
162    }
163
164//     Key const& first(const_iterator i) const { return i->first; }
165//     Key& first(iterator i) { return i->first; }
166
167//     Val const& second(const_iterator i) const { return i->second; }
168//     Val& second(iterator i) { return i->second; }
169  };
170
171
172//   template <typename Map>
173//   class KruskalMapVec : public std::vector<typename Map::KeyType> {
174//   public:
175
176//     typedef typename Map::KeyType KeyType;
177//     typedef typename Map::ValueType ValueType;
178
179//     typedef typename std::vector<KeyType> Parent;
180//     typedef typename Parent::iterator iterator;
181//     typedef typename Parent::const_iterator const_iterator;
182
183//   private:
184
185//     const Map &m;
186
187//     class compareKeys {
188//       const Map &m;
189//     public:
190//       compareKeys(Map const &_m) : m(_m) {}
191//       bool operator()(KeyType const& a, KeyType const& b) {
192//      return m[a] < m[b];
193//       }
194//     };
195
196//   public:
197
198//     KruskalMapVec(Map const& _m) : m(_m) {}
199
200//     void sort() {
201//       std::sort(begin(), end(), compareKeys(m));
202//     }
203
204//     // FIXME: nem nagyon illik ez ide...
205//     template<typename Graph>
206//     KruskalMapVec(Graph const& G, Map const& _m) : m(_m) {
207//       typedef typename Graph::EdgeIt EdgeIt;
208
209//       clear();
210//       for(EdgeIt e(G);G.valid(e);G.next(e)) {
211//       // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e))
212//      push_back(e);
213//       }
214//       sort();
215//     }
216
217//     KeyType const& first(const_iterator i) const { return *i; }
218//     KeyType& first(iterator i) { return *i; }
219
220//     ValueType const& second(const_iterator i) const { return m[*i]; }
221//     ValueType& second(iterator i) { return m[*i]; }
222//   };
223
224  /* ** ** Wrapper fuggvenyek ** ** */
225
226
227  /// \brief Wrapper to Kruskal().
228  /// Input is from an EdgeMap, output is a plain boolmap.
229
230  ///\todo some more words would be nice here.
231  ///
232  template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
233  inline
234  typename EdgeCostMap::ValueType
235  kruskalEdgeMap(Graph const& G,
236                        EdgeCostMap const& edge_costs,
237                        RetEdgeBoolMap &ret_bool_map) {
238
239    typedef KruskalPairVec<Graph,EdgeCostMap> InputVec;
240
241    InputVec iv(G, edge_costs);
242    return kruskal(G, iv, ret_bool_map);
243  }
244
245
246  /// \brief Wrapper to Kruskal().
247  /// Input is from an EdgeMap, output is to a sequence.
248
249  ///\todo it does not follow the naming convention.
250  ///
251  template <typename Graph, typename EdgeCostMap, typename RetIterator>
252  inline
253  typename EdgeCostMap::ValueType
254  kruskalEdgeMap_IteratorOut(const Graph& G,
255                             const EdgeCostMap& edge_costs,
256                             RetIterator ret_iterator)
257  {
258    typedef typename EdgeCostMap::ValueType ValueType;
259
260    typedef SequenceOutput<RetIterator> OutMap;
261    OutMap out(ret_iterator);
262
263    typedef KruskalPairVec<Graph, EdgeCostMap> InputVec;
264
265    InputVec iv(G, edge_costs);
266
267    return kruskal(G, iv, out);
268  }
269
270
271} //namespace hugo
272
273#endif //HUGO_KRUSKAL_H
Note: See TracBrowser for help on using the repository browser.