lemon/kruskal.h
author Peter Kovacs <kpeter@inf.elte.hu>
Sat, 16 Mar 2013 16:20:41 +0100
changeset 1070 ee9bac10f58e
parent 584 33c6b6e755cd
child 1092 dceba191c00d
permissions -rw-r--r--
Debug checking for capacity bounds in min cost flow algorithms (#454)
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2009
     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/maps.h>
    26 
    27 #include <lemon/core.h>
    28 #include <lemon/bits/traits.h>
    29 
    30 ///\ingroup spantree
    31 ///\file
    32 ///\brief Kruskal's algorithm to compute a minimum cost spanning tree
    33 
    34 namespace lemon {
    35 
    36   namespace _kruskal_bits {
    37 
    38     // Kruskal for directed graphs.
    39 
    40     template <typename Digraph, typename In, typename Out>
    41     typename disable_if<lemon::UndirectedTagIndicator<Digraph>,
    42                        typename In::value_type::second_type >::type
    43     kruskal(const Digraph& digraph, const In& in, Out& out,dummy<0> = 0) {
    44       typedef typename In::value_type::second_type Value;
    45       typedef typename Digraph::template NodeMap<int> IndexMap;
    46       typedef typename Digraph::Node Node;
    47 
    48       IndexMap index(digraph);
    49       UnionFind<IndexMap> uf(index);
    50       for (typename Digraph::NodeIt it(digraph); it != INVALID; ++it) {
    51         uf.insert(it);
    52       }
    53 
    54       Value tree_value = 0;
    55       for (typename In::const_iterator it = in.begin(); it != in.end(); ++it) {
    56         if (uf.join(digraph.target(it->first),digraph.source(it->first))) {
    57           out.set(it->first, true);
    58           tree_value += it->second;
    59         }
    60         else {
    61           out.set(it->first, false);
    62         }
    63       }
    64       return tree_value;
    65     }
    66 
    67     // Kruskal for undirected graphs.
    68 
    69     template <typename Graph, typename In, typename Out>
    70     typename enable_if<lemon::UndirectedTagIndicator<Graph>,
    71                        typename In::value_type::second_type >::type
    72     kruskal(const Graph& graph, const In& in, Out& out,dummy<1> = 1) {
    73       typedef typename In::value_type::second_type Value;
    74       typedef typename Graph::template NodeMap<int> IndexMap;
    75       typedef typename Graph::Node Node;
    76 
    77       IndexMap index(graph);
    78       UnionFind<IndexMap> uf(index);
    79       for (typename Graph::NodeIt it(graph); it != INVALID; ++it) {
    80         uf.insert(it);
    81       }
    82 
    83       Value tree_value = 0;
    84       for (typename In::const_iterator it = in.begin(); it != in.end(); ++it) {
    85         if (uf.join(graph.u(it->first),graph.v(it->first))) {
    86           out.set(it->first, true);
    87           tree_value += it->second;
    88         }
    89         else {
    90           out.set(it->first, false);
    91         }
    92       }
    93       return tree_value;
    94     }
    95 
    96 
    97     template <typename Sequence>
    98     struct PairComp {
    99       typedef typename Sequence::value_type Value;
   100       bool operator()(const Value& left, const Value& right) {
   101         return left.second < right.second;
   102       }
   103     };
   104 
   105     template <typename In, typename Enable = void>
   106     struct SequenceInputIndicator {
   107       static const bool value = false;
   108     };
   109 
   110     template <typename In>
   111     struct SequenceInputIndicator<In,
   112       typename exists<typename In::value_type::first_type>::type> {
   113       static const bool value = true;
   114     };
   115 
   116     template <typename In, typename Enable = void>
   117     struct MapInputIndicator {
   118       static const bool value = false;
   119     };
   120 
   121     template <typename In>
   122     struct MapInputIndicator<In,
   123       typename exists<typename In::Value>::type> {
   124       static const bool value = true;
   125     };
   126 
   127     template <typename In, typename Enable = void>
   128     struct SequenceOutputIndicator {
   129       static const bool value = false;
   130     };
   131 
   132     template <typename Out>
   133     struct SequenceOutputIndicator<Out,
   134       typename exists<typename Out::value_type>::type> {
   135       static const bool value = true;
   136     };
   137 
   138     template <typename Out, typename Enable = void>
   139     struct MapOutputIndicator {
   140       static const bool value = false;
   141     };
   142 
   143     template <typename Out>
   144     struct MapOutputIndicator<Out,
   145       typename exists<typename Out::Value>::type> {
   146       static const bool value = true;
   147     };
   148 
   149     template <typename In, typename InEnable = void>
   150     struct KruskalValueSelector {};
   151 
   152     template <typename In>
   153     struct KruskalValueSelector<In,
   154       typename enable_if<SequenceInputIndicator<In>, void>::type>
   155     {
   156       typedef typename In::value_type::second_type Value;
   157     };
   158 
   159     template <typename In>
   160     struct KruskalValueSelector<In,
   161       typename enable_if<MapInputIndicator<In>, void>::type>
   162     {
   163       typedef typename In::Value Value;
   164     };
   165 
   166     template <typename Graph, typename In, typename Out,
   167               typename InEnable = void>
   168     struct KruskalInputSelector {};
   169 
   170     template <typename Graph, typename In, typename Out,
   171               typename InEnable = void>
   172     struct KruskalOutputSelector {};
   173 
   174     template <typename Graph, typename In, typename Out>
   175     struct KruskalInputSelector<Graph, In, Out,
   176       typename enable_if<SequenceInputIndicator<In>, void>::type >
   177     {
   178       typedef typename In::value_type::second_type Value;
   179 
   180       static Value kruskal(const Graph& graph, const In& in, Out& out) {
   181         return KruskalOutputSelector<Graph, In, Out>::
   182           kruskal(graph, in, out);
   183       }
   184 
   185     };
   186 
   187     template <typename Graph, typename In, typename Out>
   188     struct KruskalInputSelector<Graph, In, Out,
   189       typename enable_if<MapInputIndicator<In>, void>::type >
   190     {
   191       typedef typename In::Value Value;
   192       static Value kruskal(const Graph& graph, const In& in, Out& out) {
   193         typedef typename In::Key MapArc;
   194         typedef typename In::Value Value;
   195         typedef typename ItemSetTraits<Graph, MapArc>::ItemIt MapArcIt;
   196         typedef std::vector<std::pair<MapArc, Value> > Sequence;
   197         Sequence seq;
   198 
   199         for (MapArcIt it(graph); it != INVALID; ++it) {
   200           seq.push_back(std::make_pair(it, in[it]));
   201         }
   202 
   203         std::sort(seq.begin(), seq.end(), PairComp<Sequence>());
   204         return KruskalOutputSelector<Graph, Sequence, Out>::
   205           kruskal(graph, seq, out);
   206       }
   207     };
   208 
   209     template <typename T>
   210     struct RemoveConst {
   211       typedef T type;
   212     };
   213 
   214     template <typename T>
   215     struct RemoveConst<const T> {
   216       typedef T type;
   217     };
   218 
   219     template <typename Graph, typename In, typename Out>
   220     struct KruskalOutputSelector<Graph, In, Out,
   221       typename enable_if<SequenceOutputIndicator<Out>, void>::type >
   222     {
   223       typedef typename In::value_type::second_type Value;
   224 
   225       static Value kruskal(const Graph& graph, const In& in, Out& out) {
   226         typedef LoggerBoolMap<typename RemoveConst<Out>::type> Map;
   227         Map map(out);
   228         return _kruskal_bits::kruskal(graph, in, map);
   229       }
   230 
   231     };
   232 
   233     template <typename Graph, typename In, typename Out>
   234     struct KruskalOutputSelector<Graph, In, Out,
   235       typename enable_if<MapOutputIndicator<Out>, void>::type >
   236     {
   237       typedef typename In::value_type::second_type Value;
   238 
   239       static Value kruskal(const Graph& graph, const In& in, Out& out) {
   240         return _kruskal_bits::kruskal(graph, in, out);
   241       }
   242     };
   243 
   244   }
   245 
   246   /// \ingroup spantree
   247   ///
   248   /// \brief Kruskal's algorithm for finding a minimum cost spanning tree of
   249   /// a graph.
   250   ///
   251   /// This function runs Kruskal's algorithm to find a minimum cost
   252   /// spanning tree of a graph.
   253   /// Due to some C++ hacking, it accepts various input and output types.
   254   ///
   255   /// \param g The graph the algorithm runs on.
   256   /// It can be either \ref concepts::Digraph "directed" or
   257   /// \ref concepts::Graph "undirected".
   258   /// If the graph is directed, the algorithm consider it to be
   259   /// undirected by disregarding the direction of the arcs.
   260   ///
   261   /// \param in This object is used to describe the arc/edge costs.
   262   /// It can be one of the following choices.
   263   /// - An STL compatible 'Forward Container' with
   264   /// <tt>std::pair<GR::Arc,C></tt> or
   265   /// <tt>std::pair<GR::Edge,C></tt> as its <tt>value_type</tt>, where
   266   /// \c C is the type of the costs. The pairs indicates the arcs/edges
   267   /// along with the assigned cost. <em>They must be in a
   268   /// cost-ascending order.</em>
   269   /// - Any readable arc/edge map. The values of the map indicate the
   270   /// arc/edge costs.
   271   ///
   272   /// \retval out Here we also have a choice.
   273   /// - It can be a writable arc/edge map with \c bool value type. After
   274   /// running the algorithm it will contain the found minimum cost spanning
   275   /// tree: the value of an arc/edge will be set to \c true if it belongs
   276   /// to the tree, otherwise it will be set to \c false. The value of
   277   /// each arc/edge will be set exactly once.
   278   /// - It can also be an iteraror of an STL Container with
   279   /// <tt>GR::Arc</tt> or <tt>GR::Edge</tt> as its
   280   /// <tt>value_type</tt>.  The algorithm copies the elements of the
   281   /// found tree into this sequence.  For example, if we know that the
   282   /// spanning tree of the graph \c g has say 53 arcs, then we can
   283   /// put its arcs into an STL vector \c tree with a code like this.
   284   ///\code
   285   /// std::vector<Arc> tree(53);
   286   /// kruskal(g,cost,tree.begin());
   287   ///\endcode
   288   /// Or if we don't know in advance the size of the tree, we can
   289   /// write this.
   290   ///\code
   291   /// std::vector<Arc> tree;
   292   /// kruskal(g,cost,std::back_inserter(tree));
   293   ///\endcode
   294   ///
   295   /// \return The total cost of the found spanning tree.
   296   ///
   297   /// \note If the input graph is not (weakly) connected, a spanning
   298   /// forest is calculated instead of a spanning tree.
   299 
   300 #ifdef DOXYGEN
   301   template <typename Graph, typename In, typename Out>
   302   Value kruskal(const Graph& g, const In& in, Out& out)
   303 #else
   304   template <class Graph, class In, class Out>
   305   inline typename _kruskal_bits::KruskalValueSelector<In>::Value
   306   kruskal(const Graph& graph, const In& in, Out& out)
   307 #endif
   308   {
   309     return _kruskal_bits::KruskalInputSelector<Graph, In, Out>::
   310       kruskal(graph, in, out);
   311   }
   312 
   313 
   314   template <class Graph, class In, class Out>
   315   inline typename _kruskal_bits::KruskalValueSelector<In>::Value
   316   kruskal(const Graph& graph, const In& in, const Out& out)
   317   {
   318     return _kruskal_bits::KruskalInputSelector<Graph, In, const Out>::
   319       kruskal(graph, in, out);
   320   }
   321 
   322 } //namespace lemon
   323 
   324 #endif //LEMON_KRUSKAL_H