1.1 --- a/lemon/kruskal.h Sun Jul 13 16:46:56 2008 +0100
1.2 +++ b/lemon/kruskal.h Sun Jul 13 19:51:02 2008 +0100
1.3 @@ -1,6 +1,6 @@
1.4 -/* -*- C++ -*-
1.5 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.6 *
1.7 - * This file is a part of LEMON, a generic C++ optimization library
1.8 + * This file is a part of LEMON, a generic C++ optimization library.
1.9 *
1.10 * Copyright (C) 2003-2008
1.11 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.12 @@ -45,18 +45,18 @@
1.13
1.14 template <typename Digraph, typename In, typename Out>
1.15 typename disable_if<lemon::UndirectedTagIndicator<Digraph>,
1.16 - typename In::value_type::second_type >::type
1.17 + typename In::value_type::second_type >::type
1.18 kruskal(const Digraph& digraph, const In& in, Out& out,dummy<0> = 0) {
1.19 typedef typename In::value_type::second_type Value;
1.20 typedef typename Digraph::template NodeMap<int> IndexMap;
1.21 typedef typename Digraph::Node Node;
1.22 -
1.23 +
1.24 IndexMap index(digraph);
1.25 UnionFind<IndexMap> uf(index);
1.26 for (typename Digraph::NodeIt it(digraph); it != INVALID; ++it) {
1.27 uf.insert(it);
1.28 }
1.29 -
1.30 +
1.31 Value tree_value = 0;
1.32 for (typename In::const_iterator it = in.begin(); it != in.end(); ++it) {
1.33 if (uf.join(digraph.target(it->first),digraph.source(it->first))) {
1.34 @@ -74,18 +74,18 @@
1.35
1.36 template <typename Graph, typename In, typename Out>
1.37 typename enable_if<lemon::UndirectedTagIndicator<Graph>,
1.38 - typename In::value_type::second_type >::type
1.39 + typename In::value_type::second_type >::type
1.40 kruskal(const Graph& graph, const In& in, Out& out,dummy<1> = 1) {
1.41 typedef typename In::value_type::second_type Value;
1.42 typedef typename Graph::template NodeMap<int> IndexMap;
1.43 typedef typename Graph::Node Node;
1.44 -
1.45 +
1.46 IndexMap index(graph);
1.47 UnionFind<IndexMap> uf(index);
1.48 for (typename Graph::NodeIt it(graph); it != INVALID; ++it) {
1.49 uf.insert(it);
1.50 }
1.51 -
1.52 +
1.53 Value tree_value = 0;
1.54 for (typename In::const_iterator it = in.begin(); it != in.end(); ++it) {
1.55 if (uf.join(graph.u(it->first),graph.v(it->first))) {
1.56 @@ -104,7 +104,7 @@
1.57 struct PairComp {
1.58 typedef typename Sequence::value_type Value;
1.59 bool operator()(const Value& left, const Value& right) {
1.60 - return left.second < right.second;
1.61 + return left.second < right.second;
1.62 }
1.63 };
1.64
1.65 @@ -114,7 +114,7 @@
1.66 };
1.67
1.68 template <typename In>
1.69 - struct SequenceInputIndicator<In,
1.70 + struct SequenceInputIndicator<In,
1.71 typename exists<typename In::value_type::first_type>::type> {
1.72 static const bool value = true;
1.73 };
1.74 @@ -125,7 +125,7 @@
1.75 };
1.76
1.77 template <typename In>
1.78 - struct MapInputIndicator<In,
1.79 + struct MapInputIndicator<In,
1.80 typename exists<typename In::Value>::type> {
1.81 static const bool value = true;
1.82 };
1.83 @@ -134,9 +134,9 @@
1.84 struct SequenceOutputIndicator {
1.85 static const bool value = false;
1.86 };
1.87 -
1.88 +
1.89 template <typename Out>
1.90 - struct SequenceOutputIndicator<Out,
1.91 + struct SequenceOutputIndicator<Out,
1.92 typename exists<typename Out::value_type>::type> {
1.93 static const bool value = true;
1.94 };
1.95 @@ -147,7 +147,7 @@
1.96 };
1.97
1.98 template <typename Out>
1.99 - struct MapOutputIndicator<Out,
1.100 + struct MapOutputIndicator<Out,
1.101 typename exists<typename Out::Value>::type> {
1.102 static const bool value = true;
1.103 };
1.104 @@ -157,18 +157,18 @@
1.105
1.106 template <typename In>
1.107 struct KruskalValueSelector<In,
1.108 - typename enable_if<SequenceInputIndicator<In>, void>::type>
1.109 + typename enable_if<SequenceInputIndicator<In>, void>::type>
1.110 {
1.111 typedef typename In::value_type::second_type Value;
1.112 - };
1.113 + };
1.114
1.115 template <typename In>
1.116 struct KruskalValueSelector<In,
1.117 - typename enable_if<MapInputIndicator<In>, void>::type>
1.118 + typename enable_if<MapInputIndicator<In>, void>::type>
1.119 {
1.120 typedef typename In::Value Value;
1.121 - };
1.122 -
1.123 + };
1.124 +
1.125 template <typename Graph, typename In, typename Out,
1.126 typename InEnable = void>
1.127 struct KruskalInputSelector {};
1.128 @@ -176,10 +176,10 @@
1.129 template <typename Graph, typename In, typename Out,
1.130 typename InEnable = void>
1.131 struct KruskalOutputSelector {};
1.132 -
1.133 +
1.134 template <typename Graph, typename In, typename Out>
1.135 struct KruskalInputSelector<Graph, In, Out,
1.136 - typename enable_if<SequenceInputIndicator<In>, void>::type >
1.137 + typename enable_if<SequenceInputIndicator<In>, void>::type >
1.138 {
1.139 typedef typename In::value_type::second_type Value;
1.140
1.141 @@ -192,7 +192,7 @@
1.142
1.143 template <typename Graph, typename In, typename Out>
1.144 struct KruskalInputSelector<Graph, In, Out,
1.145 - typename enable_if<MapInputIndicator<In>, void>::type >
1.146 + typename enable_if<MapInputIndicator<In>, void>::type >
1.147 {
1.148 typedef typename In::Value Value;
1.149 static Value kruskal(const Graph& graph, const In& in, Out& out) {
1.150 @@ -201,7 +201,7 @@
1.151 typedef typename ItemSetTraits<Graph, MapArc>::ItemIt MapArcIt;
1.152 typedef std::vector<std::pair<MapArc, Value> > Sequence;
1.153 Sequence seq;
1.154 -
1.155 +
1.156 for (MapArcIt it(graph); it != INVALID; ++it) {
1.157 seq.push_back(std::make_pair(it, in[it]));
1.158 }
1.159 @@ -224,7 +224,7 @@
1.160
1.161 template <typename Graph, typename In, typename Out>
1.162 struct KruskalOutputSelector<Graph, In, Out,
1.163 - typename enable_if<SequenceOutputIndicator<Out>, void>::type >
1.164 + typename enable_if<SequenceOutputIndicator<Out>, void>::type >
1.165 {
1.166 typedef typename In::value_type::second_type Value;
1.167
1.168 @@ -238,7 +238,7 @@
1.169
1.170 template <typename Graph, typename In, typename Out>
1.171 struct KruskalOutputSelector<Graph, In, Out,
1.172 - typename enable_if<MapOutputIndicator<Out>, void>::type >
1.173 + typename enable_if<MapOutputIndicator<Out>, void>::type >
1.174 {
1.175 typedef typename In::value_type::second_type Value;
1.176
1.177 @@ -254,17 +254,17 @@
1.178 /// \brief Kruskal algorithm to find a minimum cost spanning tree of
1.179 /// a graph.
1.180 ///
1.181 - /// This function runs Kruskal's algorithm to find a minimum cost
1.182 + /// This function runs Kruskal's algorithm to find a minimum cost
1.183 /// spanning tree.
1.184 /// Due to some C++ hacking, it accepts various input and output types.
1.185 ///
1.186 /// \param g The graph the algorithm runs on.
1.187 - /// It can be either \ref concepts::Digraph "directed" or
1.188 + /// It can be either \ref concepts::Digraph "directed" or
1.189 /// \ref concepts::Graph "undirected".
1.190 - /// If the graph is directed, the algorithm consider it to be
1.191 + /// If the graph is directed, the algorithm consider it to be
1.192 /// undirected by disregarding the direction of the arcs.
1.193 ///
1.194 - /// \param in This object is used to describe the arc/edge costs.
1.195 + /// \param in This object is used to describe the arc/edge costs.
1.196 /// It can be one of the following choices.
1.197 /// - An STL compatible 'Forward Container' with
1.198 /// <tt>std::pair<GR::Arc,X></tt> or
1.199 @@ -272,7 +272,7 @@
1.200 /// \c X is the type of the costs. The pairs indicates the arcs/edges
1.201 /// along with the assigned cost. <em>They must be in a
1.202 /// cost-ascending order.</em>
1.203 - /// - Any readable arc/edge map. The values of the map indicate the
1.204 + /// - Any readable arc/edge map. The values of the map indicate the
1.205 /// arc/edge costs.
1.206 ///
1.207 /// \retval out Here we also have a choice.
1.208 @@ -292,10 +292,10 @@
1.209 /// kruskal(g,cost,tree.begin());
1.210 ///\endcode
1.211 /// Or if we don't know in advance the size of the tree, we can
1.212 - /// write this.
1.213 + /// write this.
1.214 ///\code
1.215 /// std::vector<Arc> tree;
1.216 - /// kruskal(g,cost,std::back_inserter(tree));
1.217 + /// kruskal(g,cost,std::back_inserter(tree));
1.218 ///\endcode
1.219 ///
1.220 /// \return The total cost of the found spanning tree.
1.221 @@ -307,18 +307,18 @@
1.222 #ifdef DOXYGEN
1.223 template <class Graph, class In, class Out>
1.224 Value kruskal(GR const& g, const In& in, Out& out)
1.225 -#else
1.226 +#else
1.227 template <class Graph, class In, class Out>
1.228 - inline typename _kruskal_bits::KruskalValueSelector<In>::Value
1.229 - kruskal(const Graph& graph, const In& in, Out& out)
1.230 + inline typename _kruskal_bits::KruskalValueSelector<In>::Value
1.231 + kruskal(const Graph& graph, const In& in, Out& out)
1.232 #endif
1.233 {
1.234 return _kruskal_bits::KruskalInputSelector<Graph, In, Out>::
1.235 kruskal(graph, in, out);
1.236 }
1.237
1.238 -
1.239 -
1.240 +
1.241 +
1.242
1.243 template <class Graph, class In, class Out>
1.244 inline typename _kruskal_bits::KruskalValueSelector<In>::Value
1.245 @@ -326,7 +326,7 @@
1.246 {
1.247 return _kruskal_bits::KruskalInputSelector<Graph, In, const Out>::
1.248 kruskal(graph, in, out);
1.249 - }
1.250 + }
1.251
1.252 } //namespace lemon
1.253