COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/kruskal.h @ 2553:bfced05fa852

Last change on this file since 2553:bfced05fa852 was 2553:bfced05fa852, checked in by Alpar Juttner, 12 years ago

Happy New Year to LEMON (+ better update-copyright-header script)

File size: 19.7 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_KRUSKAL_H
20#define LEMON_KRUSKAL_H
21
22#include <algorithm>
23#include <vector>
24#include <lemon/unionfind.h>
25#include <lemon/graph_utils.h>
26#include <lemon/maps.h>
27
28#include <lemon/radix_sort.h>
29
30#include <lemon/bits/utility.h>
31#include <lemon/bits/traits.h>
32
33///\ingroup spantree
34///\file
35///\brief Kruskal's algorithm to compute a minimum cost tree
36///
37///Kruskal's algorithm to compute a minimum cost tree.
38///
39
40namespace lemon {
41
42  namespace _kruskal_bits {
43
44    template <typename Map, typename Comp>
45    struct MappedComp {
46
47      typedef typename Map::Key Key;
48
49      const Map& map;
50      Comp comp;
51
52      MappedComp(const Map& _map)
53        : map(_map), comp() {}
54
55      bool operator()(const Key& left, const Key& right) {
56        return comp(map[left], map[right]);
57      }
58
59    };
60 
61  }
62
63  /// \brief Default traits class of Kruskal class.
64  ///
65  /// Default traits class of Kruskal class.
66  /// \param _UGraph Undirected graph type.
67  /// \param _CostMap Type of cost map.
68  template <typename _UGraph, typename _CostMap>
69  struct KruskalDefaultTraits{
70
71    /// \brief The graph type the algorithm runs on.
72    typedef _UGraph UGraph;
73
74    /// \brief The type of the map that stores the edge costs.
75    ///
76    /// The type of the map that stores the edge costs.
77    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
78    typedef _CostMap CostMap;
79
80    /// \brief The type of the cost of the edges.
81    typedef typename _CostMap::Value Value;
82
83    /// \brief The type of the map that stores whether an edge is in the
84    /// spanning tree or not.
85    ///
86    /// The type of the map that stores whether an edge is in the
87    /// spanning tree or not.
88    typedef typename _UGraph::template UEdgeMap<bool> TreeMap;
89
90    /// \brief Instantiates a TreeMap.
91    ///
92    /// This function instantiates a \ref TreeMap.
93    ///
94    /// The first parameter is the graph, to which
95    /// we would like to define the \ref TreeMap
96    static TreeMap *createTreeMap(const _UGraph& graph){
97      return new TreeMap(graph);
98    }
99
100    template <typename Iterator>
101    static void sort(Iterator begin, Iterator end, const CostMap& cost) {
102      _kruskal_bits::MappedComp<CostMap, std::less<Value> > comp(cost);
103      std::sort(begin, end, comp);
104    }
105
106  };
107
108  ///\ingroup spantree
109  ///
110  /// \brief Kruskal's algorithm to find a minimum cost tree of a graph.
111  ///
112  /// This class implements Kruskal's algorithm to find a minimum cost
113  /// spanning tree. The
114  ///
115  /// \param _UGraph Undirected graph type.
116  /// \param _CostMap Type of cost map.
117  template <typename _UGraph, typename _CostMap,
118            typename _Traits = KruskalDefaultTraits<_UGraph, _CostMap> >
119  class Kruskal {
120  public:
121
122    typedef _Traits Traits;
123
124    typedef typename _Traits::UGraph UGraph;
125    typedef typename _Traits::CostMap CostMap;
126
127    typedef typename _Traits::TreeMap TreeMap;
128
129    typedef typename _Traits::Value Value;
130
131    template <typename Comp>
132    struct DefSortCompareTraits : public Traits {
133      template <typename Iterator>
134      static void sort(Iterator begin, Iterator end, const CostMap& cost) {
135        _kruskal_bits::MappedComp<CostMap, Comp> comp(cost, Comp());
136        std::sort(begin, end, comp);
137      }
138    };
139
140    /// \brief \ref named-templ-param "Named parameter" for setting the
141    /// comparator object of the standard sort
142    ///
143    /// \ref named-templ-param "Named parameter" for setting the
144    /// comparator object of the standard sort
145    template <typename Comp>
146    struct DefSortCompare
147      : public Kruskal<UGraph, CostMap, DefSortCompareTraits<Comp> > {
148      typedef Kruskal<UGraph, CostMap, DefSortCompareTraits<Comp> > Create;
149    };   
150
151    struct DefRadixSortTraits : public Traits {
152      template <typename Iterator>
153      static void sort(Iterator begin, Iterator end, const CostMap& cost) {
154        radixSort(begin, end, cost);
155      }
156    };
157
158    /// \brief \ref named-templ-param "Named parameter" for setting the
159    /// sort function to radix sort
160    ///
161    /// \brief \ref named-templ-param "Named parameter" for setting the
162    /// sort function to radix sort. The value type of the cost map should
163    /// be integral, of course.
164    struct DefRadixSort
165      : public Kruskal<UGraph, CostMap, DefRadixSortTraits> {
166      typedef Kruskal<UGraph, CostMap, DefRadixSortTraits> Create;
167    };   
168
169    template <class TM>
170    struct DefTreeMapTraits : public Traits {
171      typedef TM TreeMap;
172      static TreeMap *createTreeMap(const UGraph &) {
173        throw UninitializedParameter();
174      }
175    };
176
177    /// \brief \ref named-templ-param "Named parameter" for setting
178    /// TreeMap
179    ///
180    /// \ref named-templ-param "Named parameter" for setting TreeMap
181    ///
182    template <class TM>
183    struct DefTreeMap
184      : public Kruskal< UGraph, CostMap, DefTreeMapTraits<TM> > {
185      typedef Kruskal< UGraph, CostMap, DefTreeMapTraits<TM> > Create;
186    };   
187   
188
189  private:
190
191    typedef typename UGraph::Node Node;
192    typedef typename UGraph::NodeIt NodeIt;
193
194    typedef typename UGraph::UEdge UEdge;
195    typedef typename UGraph::UEdgeIt UEdgeIt;
196
197    const UGraph& graph;
198    const CostMap& cost;
199   
200    std::vector<UEdge> edges;
201   
202    typedef typename UGraph::template NodeMap<int> UfIndex;
203    typedef UnionFind<UfIndex> Uf;
204    UfIndex *ufi;
205    Uf *uf;
206
207    int index;
208
209    void initStructures() {
210      if (!_tree) {
211        _tree = Traits::createTreeMap(graph);
212        local_tree = true;
213      }
214      if (!uf) {
215        ufi = new typename UGraph::template NodeMap<int>(graph);
216        uf = new UnionFind<typename UGraph::template NodeMap<int> >(*ufi);
217      }
218    }
219   
220    void initUnionFind() {
221      uf->clear();
222      for (NodeIt it(graph); it != INVALID; ++it) {
223        uf->insert(it);
224      }
225    }
226
227    bool local_tree;
228    TreeMap* _tree;
229
230  public:
231
232    /// \brief Constructor
233    ///
234    /// Constructor of the algorithm.
235    Kruskal(const UGraph& _graph, const CostMap& _cost)
236      : graph(_graph), cost(_cost),
237        ufi(0), uf(0), local_tree(false), _tree(0) {}
238
239    /// \brief Destructor
240    ///
241    /// Destructor
242    ~Kruskal() {
243      if (local_tree) {
244        delete _tree;
245      }
246      if (uf) {
247        delete uf;
248        delete ufi;
249      }
250    }
251
252    /// \brief Sets the map storing the tree edges.
253    ///
254    /// Sets the map storing the tree edges.
255    /// If you don't use this function before calling \ref run(),
256    /// it will allocate one. The destuctor deallocates this
257    /// automatically allocated map, of course.
258    /// \return \c *this </tt>
259    Kruskal& treeMap(TreeMap &m){
260      if (local_tree) {
261        delete _tree;
262        local_tree = false;
263      }
264      _tree = &m;
265      return *this;
266    }
267
268    /// \brief Initialize the algorithm
269    ///
270    /// This member function initializes the unionfind data structure
271    /// and sorts the edges into ascending order
272    void init() {
273      initStructures();
274      initUnionFind();
275      for (UEdgeIt e(graph); e != INVALID; ++e) {
276        edges.push_back(e);
277        _tree->set(e, false);
278      }     
279      Traits::sort(edges.begin(), edges.end(), cost);
280      index = 0;
281    }
282
283
284    /// \brief Initialize the algorithm
285    ///
286    /// This member function initializes the unionfind data structure
287    /// and sets the edge order to the given sequence. The given
288    /// sequence should be a valid STL range of undirected edges.
289    template <typename Iterator>
290    void initPresorted(Iterator begin, Iterator end) {
291      initStructures();
292      initUnionFind();
293      edges.clear();
294      std::copy(begin, end, std::back_inserter(edges));
295      index = 0;
296    }
297
298    /// \brief Initialize the algorithm
299    ///
300    /// This member function initializes the unionfind data structure
301    /// and sets the tree to empty. It does not change the order of
302    /// the edges, it uses the order of the previous running.
303    void reinit() {
304      initStructures();
305      initUnionFind();
306      for (UEdgeIt e(graph); e != INVALID; ++e) {
307        _tree->set(e, false);
308      }
309      index = 0;
310    }
311
312
313    /// \brief Executes the algorithm.
314    ///
315    /// Executes the algorithm.
316    ///
317    /// \pre init() must be called before using this function.
318    ///
319    /// This method runs the %Kruskal algorithm.
320    void start() {
321      while (index < int(edges.size())) {
322        if (uf->join(graph.target(edges[index]), graph.source(edges[index]))) {
323          _tree->set(edges[index], true);
324        }
325        ++index;
326      }
327    }
328
329    /// \brief Runs the prim algorithm until it find a new tree edge
330    ///
331    /// Runs the prim algorithm until it find a new tree edge. If it
332    /// does not next tree edge in the sequence it gives back \c INVALID.
333    UEdge findNextTreeEdge() {
334      while (index < int(edges.size())) {
335        if (uf->join(graph.target(edges[index]), graph.source(edges[index]))) {
336          _tree->set(edges[index], true);
337          return edges[index++];
338        }       
339        ++index;
340      }
341      return INVALID;
342    }
343     
344    /// \brief Processes the next edge in the sequence
345    ///
346    /// Processes the next edge in the sequence.
347    ///
348    /// \return The prcocessed edge.
349    ///
350    /// \warning The sequence must not be empty!
351    UEdge processNextEdge() {
352      UEdge edge = edges[index++];
353      processEdge(edge);
354      return edge;
355    }
356
357    /// \brief Processes an arbitrary edge
358    ///
359    /// Processes the next edge in the sequence.
360    ///
361    /// \return True when the edge is a tree edge.
362    bool processEdge(const UEdge& edge) {
363      if (uf->join(graph.target(edge), graph.source(edge))) {
364        _tree->set(edge, true);
365        return true;
366      } else {
367        return false;
368      }   
369    }
370
371    /// \brief Returns \c false if there are edge to be processed in
372    /// sequence
373    ///
374    /// Returns \c false if there are nodes to be processed in the
375    /// sequence
376    bool emptyQueue() {
377      return index == int(edges.size());
378    }
379
380    /// \brief Returns the next edge to be processed
381    ///
382    /// Returns the next edge to be processed
383    ///
384    UEdge nextEdge() const {
385      return edges[index];
386    }
387
388    /// \brief Runs %Kruskal algorithm.
389    ///
390    /// This method runs the %Kruskal algorithm in order to compute the
391    /// minimum spanning tree (or minimum spanning forest).  The
392    /// method also works on graphs that has more than one components.
393    /// In this case it computes the minimum spanning forest.
394    void run() {
395      init();
396      start();
397    }
398
399    /// \brief Returns a reference to the tree edges map
400    ///
401    /// Returns a reference to the TreeEdgeMap of the edges of the
402    /// minimum spanning tree. The value of the map is \c true only if
403    /// the edge is in the minimum spanning tree.
404    ///
405    const TreeMap &treeMap() const { return *_tree;}
406
407    /// \brief Returns the total cost of the tree
408    ///
409    /// Returns the total cost of the tree
410    Value treeValue() const {
411      Value value = 0;
412      for (UEdgeIt it(graph); it != INVALID; ++it) {
413        if ((*_tree)[it]) {
414          value += cost[it];
415        }
416      }
417      return value;
418    }
419
420    /// \brief Returns true when the given edge is tree edge
421    ///
422    /// Returns true when the given edge is tree edge
423    bool tree(UEdge e) const {
424      return (*_tree)[e];
425    }
426   
427   
428  };
429
430
431  namespace _kruskal_bits {
432
433    template <typename Graph, typename In, typename Out>
434    typename In::value_type::second_type
435    kruskal(const Graph& graph, const In& in, Out& out) {
436      typedef typename In::value_type::second_type Value;
437      typedef typename Graph::template NodeMap<int> IndexMap;
438      typedef typename Graph::Node Node;
439     
440      IndexMap index(graph);
441      UnionFind<IndexMap> uf(index);
442      for (typename Graph::NodeIt it(graph); it != INVALID; ++it) {
443        uf.insert(it);
444      }
445     
446      Value tree_value = 0;
447      for (typename In::const_iterator it = in.begin(); it != in.end(); ++it) {
448        if (uf.join(graph.target(it->first),graph.source(it->first))) {
449          out.set(it->first, true);
450          tree_value += it->second;
451        }
452        else {
453          out.set(it->first, false);
454        }
455      }
456      return tree_value;
457    }
458
459
460    template <typename Sequence>
461    struct PairComp {
462      typedef typename Sequence::value_type Value;
463      bool operator()(const Value& left, const Value& right) {
464        return left.second < right.second;
465      }
466    };
467
468    template <typename In, typename Enable = void>
469    struct SequenceInputIndicator {
470      static const bool value = false;
471    };
472
473    template <typename In>
474    struct SequenceInputIndicator<In,
475      typename exists<typename In::value_type::first_type>::type> {
476      static const bool value = true;
477    };
478
479    template <typename In, typename Enable = void>
480    struct MapInputIndicator {
481      static const bool value = false;
482    };
483
484    template <typename In>
485    struct MapInputIndicator<In,
486      typename exists<typename In::Value>::type> {
487      static const bool value = true;
488    };
489
490    template <typename In, typename Enable = void>
491    struct SequenceOutputIndicator {
492      static const bool value = false;
493    };
494 
495    template <typename Out>
496    struct SequenceOutputIndicator<Out,
497      typename exists<typename Out::value_type>::type> {
498      static const bool value = true;
499    };
500
501    template <typename Out, typename Enable = void>
502    struct MapOutputIndicator {
503      static const bool value = false;
504    };
505
506    template <typename Out>
507    struct MapOutputIndicator<Out,
508      typename exists<typename Out::Value>::type> {
509      static const bool value = true;
510    };
511
512    template <typename In, typename InEnable = void>
513    struct KruskalValueSelector {};
514
515    template <typename In>
516    struct KruskalValueSelector<In,
517      typename enable_if<SequenceInputIndicator<In>, void>::type>
518    {
519      typedef typename In::value_type::second_type Value;
520    };   
521
522    template <typename In>
523    struct KruskalValueSelector<In,
524      typename enable_if<MapInputIndicator<In>, void>::type>
525    {
526      typedef typename In::Value Value;
527    };   
528   
529    template <typename Graph, typename In, typename Out,
530              typename InEnable = void>
531    struct KruskalInputSelector {};
532
533    template <typename Graph, typename In, typename Out,
534              typename InEnable = void>
535    struct KruskalOutputSelector {};
536   
537    template <typename Graph, typename In, typename Out>
538    struct KruskalInputSelector<Graph, In, Out,
539      typename enable_if<SequenceInputIndicator<In>, void>::type >
540    {
541      typedef typename In::value_type::second_type Value;
542
543      static Value kruskal(const Graph& graph, const In& in, Out& out) {
544        return KruskalOutputSelector<Graph, In, Out>::
545          kruskal(graph, in, out);
546      }
547
548    };
549
550    template <typename Graph, typename In, typename Out>
551    struct KruskalInputSelector<Graph, In, Out,
552      typename enable_if<MapInputIndicator<In>, void>::type >
553    {
554      typedef typename In::Value Value;
555      static Value kruskal(const Graph& graph, const In& in, Out& out) {
556        typedef typename In::Key MapEdge;
557        typedef typename In::Value Value;
558        typedef typename ItemSetTraits<Graph, MapEdge>::ItemIt MapEdgeIt;
559        typedef std::vector<std::pair<MapEdge, Value> > Sequence;
560        Sequence seq;
561       
562        for (MapEdgeIt it(graph); it != INVALID; ++it) {
563          seq.push_back(std::make_pair(it, in[it]));
564        }
565
566        std::sort(seq.begin(), seq.end(), PairComp<Sequence>());
567        return KruskalOutputSelector<Graph, Sequence, Out>::
568          kruskal(graph, seq, out);
569      }
570    };
571
572    template <typename Graph, typename In, typename Out>
573    struct KruskalOutputSelector<Graph, In, Out,
574      typename enable_if<SequenceOutputIndicator<Out>, void>::type >
575    {
576      typedef typename In::value_type::second_type Value;
577
578      static Value kruskal(const Graph& graph, const In& in, Out& out) {
579        typedef StoreBoolMap<Out> Map;
580        Map map(out);
581        return _kruskal_bits::kruskal(graph, in, map);
582      }
583
584    };
585
586    template <typename Graph, typename In, typename Out>
587    struct KruskalOutputSelector<Graph, In, Out,
588      typename enable_if<MapOutputIndicator<Out>, void>::type >
589    {
590      typedef typename In::value_type::second_type Value;
591
592      static Value kruskal(const Graph& graph, const In& in, Out& out) {
593        return _kruskal_bits::kruskal(graph, in, out);
594      }
595    };
596
597  }
598
599  /// \ingroup spantree
600  ///
601  /// \brief Kruskal's algorithm to find a minimum cost tree of a graph.
602  ///
603  /// This function runs Kruskal's algorithm to find a minimum cost tree.
604  /// Due to hard C++ hacking, it accepts various input and output types.
605  ///
606  /// \param g The graph the algorithm runs on.
607  /// It can be either \ref concepts::Graph "directed" or
608  /// \ref concepts::UGraph "undirected".
609  /// If the graph is directed, the algorithm consider it to be
610  /// undirected by disregarding the direction of the edges.
611  ///
612  /// \param in This object is used to describe the edge costs. It can be one
613  /// of the following choices.
614  ///
615  /// - An STL compatible 'Forward Container' with
616  /// <tt>std::pair<GR::UEdge,X></tt> or
617  /// <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>, where
618  /// \c X is the type of the costs. The pairs indicates the edges
619  /// along with the assigned cost. <em>They must be in a
620  /// cost-ascending order.</em>
621  /// - Any readable Edge map. The values of the map indicate the edge costs.
622  ///
623  /// \retval out Here we also have a choise.
624  /// - It can be a writable \c bool edge map.  After running the
625  /// algorithm this will contain the found minimum cost spanning
626  /// tree: the value of an edge will be set to \c true if it belongs
627  /// to the tree, otherwise it will be set to \c false. The value of
628  /// each edge will be set exactly once.
629  /// - It can also be an iteraror of an STL Container with
630  /// <tt>GR::UEdge</tt> or <tt>GR::Edge</tt> as its
631  /// <tt>value_type</tt>.  The algorithm copies the elements of the
632  /// found tree into this sequence.  For example, if we know that the
633  /// spanning tree of the graph \c g has say 53 edges, then we can
634  /// put its edges into an STL vector \c tree with a code like this.
635  ///\code
636  /// std::vector<Edge> tree(53);
637  /// kruskal(g,cost,tree.begin());
638  ///\endcode
639  /// Or if we don't know in advance the size of the tree, we can
640  /// write this. 
641  ///\code std::vector<Edge> tree;
642  /// kruskal(g,cost,std::back_inserter(tree));
643  ///\endcode
644  ///
645  /// \return The total cost of the found tree.
646  ///
647  /// \warning If kruskal runs on an be consistent of using the same
648  /// Edge type for input and output.
649  ///
650
651#ifdef DOXYGEN
652  template <class Graph, class In, class Out>
653  Value kruskal(GR const& g, const In& in, Out& out)
654#else
655  template <class Graph, class In, class Out>
656  inline typename _kruskal_bits::KruskalValueSelector<In>::Value
657  kruskal(const Graph& graph, const In& in, Out& out)
658#endif
659  {
660    return _kruskal_bits::KruskalInputSelector<Graph, In, Out>::
661      kruskal(graph, in, out);
662  }
663
664 
665 
666
667  template <class Graph, class In, class Out>
668  inline typename _kruskal_bits::KruskalValueSelector<In>::Value
669  kruskal(const Graph& graph, const In& in, const Out& out)
670  {
671    return _kruskal_bits::KruskalInputSelector<Graph, In, const Out>::
672      kruskal(graph, in, out);
673  } 
674
675} //namespace lemon
676
677#endif //LEMON_KRUSKAL_H
Note: See TracBrowser for help on using the repository browser.