lemon/kruskal.h
author alpar
Tue, 24 Apr 2007 09:39:01 +0000
changeset 2436 0c941c524b47
parent 2428 c06e86364234
child 2553 bfced05fa852
permissions -rw-r--r--
Integer parameters also convert to double
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2007
     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 
    40 namespace 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