lemon/kruskal.h
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Mar 2009 00:18:25 +0100
changeset 604 8c3112a66878
parent 220 a5d8c039f218
child 584 33c6b6e755cd
permissions -rw-r--r--
Use XTI implementation instead of ATI in NetworkSimplex (#234)

XTI (eXtended Threaded Index) is an imporved version of the widely
known ATI (Augmented Threaded Index) method for storing and updating
the spanning tree structure in Network Simplex algorithms.

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