1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/kruskal.h Fri Feb 29 11:01:39 2008 +0000
1.3 @@ -0,0 +1,319 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2008
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_KRUSKAL_H
1.23 +#define LEMON_KRUSKAL_H
1.24 +
1.25 +#include <algorithm>
1.26 +#include <vector>
1.27 +#include <lemon/unionfind.h>
1.28 +// #include <lemon/graph_utils.h>
1.29 +#include <lemon/maps.h>
1.30 +
1.31 +// #include <lemon/radix_sort.h>
1.32 +
1.33 +#include <lemon/bits/utility.h>
1.34 +#include <lemon/bits/traits.h>
1.35 +
1.36 +///\ingroup spantree
1.37 +///\file
1.38 +///\brief Kruskal's algorithm to compute a minimum cost tree
1.39 +///
1.40 +///Kruskal's algorithm to compute a minimum cost tree.
1.41 +///
1.42 +
1.43 +namespace lemon {
1.44 +
1.45 + namespace _kruskal_bits {
1.46 +
1.47 + // Kruskal for directed graphs.
1.48 +
1.49 + template <typename Digraph, typename In, typename Out>
1.50 + typename disable_if<lemon::UndirectedTagIndicator<Digraph>,
1.51 + typename In::value_type::second_type >::type
1.52 + kruskal(const Digraph& digraph, const In& in, Out& out,dummy<0> = 0) {
1.53 + typedef typename In::value_type::second_type Value;
1.54 + typedef typename Digraph::template NodeMap<int> IndexMap;
1.55 + typedef typename Digraph::Node Node;
1.56 +
1.57 + IndexMap index(digraph);
1.58 + UnionFind<IndexMap> uf(index);
1.59 + for (typename Digraph::NodeIt it(digraph); it != INVALID; ++it) {
1.60 + uf.insert(it);
1.61 + }
1.62 +
1.63 + Value tree_value = 0;
1.64 + for (typename In::const_iterator it = in.begin(); it != in.end(); ++it) {
1.65 + if (uf.join(digraph.target(it->first),digraph.source(it->first))) {
1.66 + out.set(it->first, true);
1.67 + tree_value += it->second;
1.68 + }
1.69 + else {
1.70 + out.set(it->first, false);
1.71 + }
1.72 + }
1.73 + return tree_value;
1.74 + }
1.75 +
1.76 + // Kruskal for undirected graphs.
1.77 +
1.78 + template <typename Graph, typename In, typename Out>
1.79 + typename enable_if<lemon::UndirectedTagIndicator<Graph>,
1.80 + typename In::value_type::second_type >::type
1.81 + kruskal(const Graph& graph, const In& in, Out& out,dummy<1> = 1) {
1.82 + typedef typename In::value_type::second_type Value;
1.83 + typedef typename Graph::template NodeMap<int> IndexMap;
1.84 + typedef typename Graph::Node Node;
1.85 +
1.86 + IndexMap index(graph);
1.87 + UnionFind<IndexMap> uf(index);
1.88 + for (typename Graph::NodeIt it(graph); it != INVALID; ++it) {
1.89 + uf.insert(it);
1.90 + }
1.91 +
1.92 + Value tree_value = 0;
1.93 + for (typename In::const_iterator it = in.begin(); it != in.end(); ++it) {
1.94 + if (uf.join(graph.u(it->first),graph.v(it->first))) {
1.95 + out.set(it->first, true);
1.96 + tree_value += it->second;
1.97 + }
1.98 + else {
1.99 + out.set(it->first, false);
1.100 + }
1.101 + }
1.102 + return tree_value;
1.103 + }
1.104 +
1.105 +
1.106 + template <typename Sequence>
1.107 + struct PairComp {
1.108 + typedef typename Sequence::value_type Value;
1.109 + bool operator()(const Value& left, const Value& right) {
1.110 + return left.second < right.second;
1.111 + }
1.112 + };
1.113 +
1.114 + template <typename In, typename Enable = void>
1.115 + struct SequenceInputIndicator {
1.116 + static const bool value = false;
1.117 + };
1.118 +
1.119 + template <typename In>
1.120 + struct SequenceInputIndicator<In,
1.121 + typename exists<typename In::value_type::first_type>::type> {
1.122 + static const bool value = true;
1.123 + };
1.124 +
1.125 + template <typename In, typename Enable = void>
1.126 + struct MapInputIndicator {
1.127 + static const bool value = false;
1.128 + };
1.129 +
1.130 + template <typename In>
1.131 + struct MapInputIndicator<In,
1.132 + typename exists<typename In::Value>::type> {
1.133 + static const bool value = true;
1.134 + };
1.135 +
1.136 + template <typename In, typename Enable = void>
1.137 + struct SequenceOutputIndicator {
1.138 + static const bool value = false;
1.139 + };
1.140 +
1.141 + template <typename Out>
1.142 + struct SequenceOutputIndicator<Out,
1.143 + typename exists<typename Out::value_type>::type> {
1.144 + static const bool value = true;
1.145 + };
1.146 +
1.147 + template <typename Out, typename Enable = void>
1.148 + struct MapOutputIndicator {
1.149 + static const bool value = false;
1.150 + };
1.151 +
1.152 + template <typename Out>
1.153 + struct MapOutputIndicator<Out,
1.154 + typename exists<typename Out::Value>::type> {
1.155 + static const bool value = true;
1.156 + };
1.157 +
1.158 + template <typename In, typename InEnable = void>
1.159 + struct KruskalValueSelector {};
1.160 +
1.161 + template <typename In>
1.162 + struct KruskalValueSelector<In,
1.163 + typename enable_if<SequenceInputIndicator<In>, void>::type>
1.164 + {
1.165 + typedef typename In::value_type::second_type Value;
1.166 + };
1.167 +
1.168 + template <typename In>
1.169 + struct KruskalValueSelector<In,
1.170 + typename enable_if<MapInputIndicator<In>, void>::type>
1.171 + {
1.172 + typedef typename In::Value Value;
1.173 + };
1.174 +
1.175 + template <typename Graph, typename In, typename Out,
1.176 + typename InEnable = void>
1.177 + struct KruskalInputSelector {};
1.178 +
1.179 + template <typename Graph, typename In, typename Out,
1.180 + typename InEnable = void>
1.181 + struct KruskalOutputSelector {};
1.182 +
1.183 + template <typename Graph, typename In, typename Out>
1.184 + struct KruskalInputSelector<Graph, In, Out,
1.185 + typename enable_if<SequenceInputIndicator<In>, void>::type >
1.186 + {
1.187 + typedef typename In::value_type::second_type Value;
1.188 +
1.189 + static Value kruskal(const Graph& graph, const In& in, Out& out) {
1.190 + return KruskalOutputSelector<Graph, In, Out>::
1.191 + kruskal(graph, in, out);
1.192 + }
1.193 +
1.194 + };
1.195 +
1.196 + template <typename Graph, typename In, typename Out>
1.197 + struct KruskalInputSelector<Graph, In, Out,
1.198 + typename enable_if<MapInputIndicator<In>, void>::type >
1.199 + {
1.200 + typedef typename In::Value Value;
1.201 + static Value kruskal(const Graph& graph, const In& in, Out& out) {
1.202 + typedef typename In::Key MapArc;
1.203 + typedef typename In::Value Value;
1.204 + typedef typename ItemSetTraits<Graph, MapArc>::ItemIt MapArcIt;
1.205 + typedef std::vector<std::pair<MapArc, Value> > Sequence;
1.206 + Sequence seq;
1.207 +
1.208 + for (MapArcIt it(graph); it != INVALID; ++it) {
1.209 + seq.push_back(std::make_pair(it, in[it]));
1.210 + }
1.211 +
1.212 + std::sort(seq.begin(), seq.end(), PairComp<Sequence>());
1.213 + return KruskalOutputSelector<Graph, Sequence, Out>::
1.214 + kruskal(graph, seq, out);
1.215 + }
1.216 + };
1.217 +
1.218 + template <typename Graph, typename In, typename Out>
1.219 + struct KruskalOutputSelector<Graph, In, Out,
1.220 + typename enable_if<SequenceOutputIndicator<Out>, void>::type >
1.221 + {
1.222 + typedef typename In::value_type::second_type Value;
1.223 +
1.224 + static Value kruskal(const Graph& graph, const In& in, Out& out) {
1.225 + typedef StoreBoolMap<Out> Map;
1.226 + Map map(out);
1.227 + return _kruskal_bits::kruskal(graph, in, map);
1.228 + }
1.229 +
1.230 + };
1.231 +
1.232 + template <typename Graph, typename In, typename Out>
1.233 + struct KruskalOutputSelector<Graph, In, Out,
1.234 + typename enable_if<MapOutputIndicator<Out>, void>::type >
1.235 + {
1.236 + typedef typename In::value_type::second_type Value;
1.237 +
1.238 + static Value kruskal(const Graph& graph, const In& in, Out& out) {
1.239 + return _kruskal_bits::kruskal(graph, in, out);
1.240 + }
1.241 + };
1.242 +
1.243 + }
1.244 +
1.245 + /// \ingroup spantree
1.246 + ///
1.247 + /// \brief Kruskal's algorithm to find a minimum cost tree of a graph.
1.248 + ///
1.249 + /// This function runs Kruskal's algorithm to find a minimum cost tree.
1.250 + /// Due to some C++ hacking, it accepts various input and output types.
1.251 + ///
1.252 + /// \param g The graph the algorithm runs on.
1.253 + /// It can be either \ref concepts::Digraph "directed" or
1.254 + /// \ref concepts::Graph "undirected".
1.255 + /// If the graph is directed, the algorithm consider it to be
1.256 + /// undirected by disregarding the direction of the arcs.
1.257 + ///
1.258 + /// \param in This object is used to describe the arc costs. It can be one
1.259 + /// of the following choices.
1.260 + /// - An STL compatible 'Forward Container' with
1.261 + /// <tt>std::pair<GR::Edge,X></tt> or
1.262 + /// <tt>std::pair<GR::Arc,X></tt> as its <tt>value_type</tt>, where
1.263 + /// \c X is the type of the costs. The pairs indicates the arcs
1.264 + /// along with the assigned cost. <em>They must be in a
1.265 + /// cost-ascending order.</em>
1.266 + /// - Any readable Arc map. The values of the map indicate the arc costs.
1.267 + ///
1.268 + /// \retval out Here we also have a choise.
1.269 + /// - It can be a writable \c bool arc map. After running the
1.270 + /// algorithm this will contain the found minimum cost spanning
1.271 + /// tree: the value of an arc will be set to \c true if it belongs
1.272 + /// to the tree, otherwise it will be set to \c false. The value of
1.273 + /// each arc will be set exactly once.
1.274 + /// - It can also be an iteraror of an STL Container with
1.275 + /// <tt>GR::Edge</tt> or <tt>GR::Arc</tt> as its
1.276 + /// <tt>value_type</tt>. The algorithm copies the elements of the
1.277 + /// found tree into this sequence. For example, if we know that the
1.278 + /// spanning tree of the graph \c g has say 53 arcs, then we can
1.279 + /// put its arcs into an STL vector \c tree with a code like this.
1.280 + ///\code
1.281 + /// std::vector<Arc> tree(53);
1.282 + /// kruskal(g,cost,tree.begin());
1.283 + ///\endcode
1.284 + /// Or if we don't know in advance the size of the tree, we can
1.285 + /// write this.
1.286 + ///\code std::vector<Arc> tree;
1.287 + /// kruskal(g,cost,std::back_inserter(tree));
1.288 + ///\endcode
1.289 + ///
1.290 + /// \return The total cost of the found tree.
1.291 + ///
1.292 + /// \warning If kruskal runs on an be consistent of using the same
1.293 + /// Arc type for input and output.
1.294 + ///
1.295 +
1.296 +#ifdef DOXYGEN
1.297 + template <class Graph, class In, class Out>
1.298 + Value kruskal(GR const& g, const In& in, Out& out)
1.299 +#else
1.300 + template <class Graph, class In, class Out>
1.301 + inline typename _kruskal_bits::KruskalValueSelector<In>::Value
1.302 + kruskal(const Graph& graph, const In& in, Out& out)
1.303 +#endif
1.304 + {
1.305 + return _kruskal_bits::KruskalInputSelector<Graph, In, Out>::
1.306 + kruskal(graph, in, out);
1.307 + }
1.308 +
1.309 +
1.310 +
1.311 +
1.312 + template <class Graph, class In, class Out>
1.313 + inline typename _kruskal_bits::KruskalValueSelector<In>::Value
1.314 + kruskal(const Graph& graph, const In& in, const Out& out)
1.315 + {
1.316 + return _kruskal_bits::KruskalInputSelector<Graph, In, const Out>::
1.317 + kruskal(graph, in, out);
1.318 + }
1.319 +
1.320 +} //namespace lemon
1.321 +
1.322 +#endif //LEMON_KRUSKAL_H