diff --git a/lemon/kruskal.h b/lemon/kruskal.h --- a/lemon/kruskal.h +++ b/lemon/kruskal.h @@ -1,6 +1,6 @@ -/* -*- C++ -*- +/* -*- mode: C++; indent-tabs-mode: nil; -*- * - * This file is a part of LEMON, a generic C++ optimization library + * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2008 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport @@ -45,18 +45,18 @@ template typename disable_if, - typename In::value_type::second_type >::type + typename In::value_type::second_type >::type kruskal(const Digraph& digraph, const In& in, Out& out,dummy<0> = 0) { typedef typename In::value_type::second_type Value; typedef typename Digraph::template NodeMap IndexMap; typedef typename Digraph::Node Node; - + IndexMap index(digraph); UnionFind uf(index); for (typename Digraph::NodeIt it(digraph); it != INVALID; ++it) { uf.insert(it); } - + Value tree_value = 0; for (typename In::const_iterator it = in.begin(); it != in.end(); ++it) { if (uf.join(digraph.target(it->first),digraph.source(it->first))) { @@ -74,18 +74,18 @@ template typename enable_if, - typename In::value_type::second_type >::type + typename In::value_type::second_type >::type kruskal(const Graph& graph, const In& in, Out& out,dummy<1> = 1) { typedef typename In::value_type::second_type Value; typedef typename Graph::template NodeMap IndexMap; typedef typename Graph::Node Node; - + IndexMap index(graph); UnionFind uf(index); for (typename Graph::NodeIt it(graph); it != INVALID; ++it) { uf.insert(it); } - + Value tree_value = 0; for (typename In::const_iterator it = in.begin(); it != in.end(); ++it) { if (uf.join(graph.u(it->first),graph.v(it->first))) { @@ -104,7 +104,7 @@ struct PairComp { typedef typename Sequence::value_type Value; bool operator()(const Value& left, const Value& right) { - return left.second < right.second; + return left.second < right.second; } }; @@ -114,7 +114,7 @@ }; template - struct SequenceInputIndicator::type> { static const bool value = true; }; @@ -125,7 +125,7 @@ }; template - struct MapInputIndicator::type> { static const bool value = true; }; @@ -134,9 +134,9 @@ struct SequenceOutputIndicator { static const bool value = false; }; - + template - struct SequenceOutputIndicator::type> { static const bool value = true; }; @@ -147,7 +147,7 @@ }; template - struct MapOutputIndicator::type> { static const bool value = true; }; @@ -157,18 +157,18 @@ template struct KruskalValueSelector, void>::type> + typename enable_if, void>::type> { typedef typename In::value_type::second_type Value; - }; + }; template struct KruskalValueSelector, void>::type> + typename enable_if, void>::type> { typedef typename In::Value Value; - }; - + }; + template struct KruskalInputSelector {}; @@ -176,10 +176,10 @@ template struct KruskalOutputSelector {}; - + template struct KruskalInputSelector, void>::type > + typename enable_if, void>::type > { typedef typename In::value_type::second_type Value; @@ -192,7 +192,7 @@ template struct KruskalInputSelector, void>::type > + typename enable_if, void>::type > { typedef typename In::Value Value; static Value kruskal(const Graph& graph, const In& in, Out& out) { @@ -201,7 +201,7 @@ typedef typename ItemSetTraits::ItemIt MapArcIt; typedef std::vector > Sequence; Sequence seq; - + for (MapArcIt it(graph); it != INVALID; ++it) { seq.push_back(std::make_pair(it, in[it])); } @@ -224,7 +224,7 @@ template struct KruskalOutputSelector, void>::type > + typename enable_if, void>::type > { typedef typename In::value_type::second_type Value; @@ -238,7 +238,7 @@ template struct KruskalOutputSelector, void>::type > + typename enable_if, void>::type > { typedef typename In::value_type::second_type Value; @@ -254,17 +254,17 @@ /// \brief Kruskal algorithm to find a minimum cost spanning tree of /// a graph. /// - /// This function runs Kruskal's algorithm to find a minimum cost + /// This function runs Kruskal's algorithm to find a minimum cost /// spanning tree. /// Due to some C++ hacking, it accepts various input and output types. /// /// \param g The graph the algorithm runs on. - /// It can be either \ref concepts::Digraph "directed" or + /// It can be either \ref concepts::Digraph "directed" or /// \ref concepts::Graph "undirected". - /// If the graph is directed, the algorithm consider it to be + /// If the graph is directed, the algorithm consider it to be /// undirected by disregarding the direction of the arcs. /// - /// \param in This object is used to describe the arc/edge costs. + /// \param in This object is used to describe the arc/edge costs. /// It can be one of the following choices. /// - An STL compatible 'Forward Container' with /// std::pair or @@ -272,7 +272,7 @@ /// \c X is the type of the costs. The pairs indicates the arcs/edges /// along with the assigned cost. They must be in a /// cost-ascending order. - /// - Any readable arc/edge map. The values of the map indicate the + /// - Any readable arc/edge map. The values of the map indicate the /// arc/edge costs. /// /// \retval out Here we also have a choice. @@ -292,10 +292,10 @@ /// kruskal(g,cost,tree.begin()); ///\endcode /// Or if we don't know in advance the size of the tree, we can - /// write this. + /// write this. ///\code /// std::vector tree; - /// kruskal(g,cost,std::back_inserter(tree)); + /// kruskal(g,cost,std::back_inserter(tree)); ///\endcode /// /// \return The total cost of the found spanning tree. @@ -307,18 +307,18 @@ #ifdef DOXYGEN template Value kruskal(GR const& g, const In& in, Out& out) -#else +#else template - inline typename _kruskal_bits::KruskalValueSelector::Value - kruskal(const Graph& graph, const In& in, Out& out) + inline typename _kruskal_bits::KruskalValueSelector::Value + kruskal(const Graph& graph, const In& in, Out& out) #endif { return _kruskal_bits::KruskalInputSelector:: kruskal(graph, in, out); } - - + + template inline typename _kruskal_bits::KruskalValueSelector::Value @@ -326,7 +326,7 @@ { return _kruskal_bits::KruskalInputSelector:: kruskal(graph, in, out); - } + } } //namespace lemon