Changeset 209:765619b7cbb2 in lemon-1.2 for lemon/kruskal.h

Timestamp:

07/13/08 20:51:02 (17 years ago)

Author:

Alpar Juttner <alpar@…>

Branch:

default

Phase:

public

Message:

Apply unify-sources.sh to the source tree

File:

• lemon/kruskal.h (modified) (22 diffs)

lemon/kruskal.h

@@ -1 @@
-/* -*- C++ -*-
- *
- * This file is a part of LEMON, a generic C++ optimization library
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
  *
  * Copyright (C) 2003-2008
@@ -46 +46 @@
     template <typename Digraph, typename In, typename Out>
     typename disable_if<lemon::UndirectedTagIndicator<Digraph>,
-                       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<int> IndexMap;
       typedef typename Digraph::Node Node;
-      
+
       IndexMap index(digraph);
       UnionFind<IndexMap> uf(index);
@@ -57 +57 @@
         uf.insert(it);
       }
-      
+
       Value tree_value = 0;
       for (typename In::const_iterator it = in.begin(); it != in.end(); ++it) {
@@ -75 +75 @@
     template <typename Graph, typename In, typename Out>
     typename enable_if<lemon::UndirectedTagIndicator<Graph>,
-                       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<int> IndexMap;
       typedef typename Graph::Node Node;
-      
+
       IndexMap index(graph);
       UnionFind<IndexMap> uf(index);
@@ -86 +86 @@
         uf.insert(it);
       }
-      
+
       Value tree_value = 0;
       for (typename In::const_iterator it = in.begin(); it != in.end(); ++it) {
@@ -105 +105 @@
       typedef typename Sequence::value_type Value;
       bool operator()(const Value& left, const Value& right) {
-        return left.second < right.second;
+        return left.second < right.second;
       }
     };
@@ -115 +115 @@
 
     template <typename In>
-    struct SequenceInputIndicator<In, 
+    struct SequenceInputIndicator<In,
       typename exists<typename In::value_type::first_type>::type> {
       static const bool value = true;
@@ -126 +126 @@
 
     template <typename In>
-    struct MapInputIndicator<In, 
+    struct MapInputIndicator<In,
       typename exists<typename In::Value>::type> {
       static const bool value = true;
@@ -135 +135 @@
       static const bool value = false;
     };
- 
+
     template <typename Out>
-    struct SequenceOutputIndicator<Out, 
+    struct SequenceOutputIndicator<Out,
       typename exists<typename Out::value_type>::type> {
       static const bool value = true;
@@ -148 +148 @@
 
     template <typename Out>
-    struct MapOutputIndicator<Out, 
+    struct MapOutputIndicator<Out,
       typename exists<typename Out::Value>::type> {
       static const bool value = true;
@@ -158 +158 @@
     template <typename In>
     struct KruskalValueSelector<In,
-      typename enable_if<SequenceInputIndicator<In>, void>::type> 
-    {
-      typedef typename In::value_type::second_type Value;
-    };    
+      typename enable_if<SequenceInputIndicator<In>, void>::type>
+    {
+      typedef typename In::value_type::second_type Value;
+    };
 
     template <typename In>
     struct KruskalValueSelector<In,
-      typename enable_if<MapInputIndicator<In>, void>::type> 
+      typename enable_if<MapInputIndicator<In>, void>::type>
     {
       typedef typename In::Value Value;
-    };    
-    
+    };
+
     template <typename Graph, typename In, typename Out,
               typename InEnable = void>
@@ -177 +177 @@
               typename InEnable = void>
     struct KruskalOutputSelector {};
-    
+
     template <typename Graph, typename In, typename Out>
     struct KruskalInputSelector<Graph, In, Out,
-      typename enable_if<SequenceInputIndicator<In>, void>::type > 
+      typename enable_if<SequenceInputIndicator<In>, void>::type >
     {
       typedef typename In::value_type::second_type Value;
@@ -193 +193 @@
     template <typename Graph, typename In, typename Out>
     struct KruskalInputSelector<Graph, In, Out,
-      typename enable_if<MapInputIndicator<In>, void>::type > 
+      typename enable_if<MapInputIndicator<In>, void>::type >
     {
       typedef typename In::Value Value;
@@ -202 +202 @@
         typedef std::vector<std::pair<MapArc, Value> > Sequence;
         Sequence seq;
-        
+
         for (MapArcIt it(graph); it != INVALID; ++it) {
           seq.push_back(std::make_pair(it, in[it]));
@@ -225 +225 @@
     template <typename Graph, typename In, typename Out>
     struct KruskalOutputSelector<Graph, In, Out,
-      typename enable_if<SequenceOutputIndicator<Out>, void>::type > 
+      typename enable_if<SequenceOutputIndicator<Out>, void>::type >
     {
       typedef typename In::value_type::second_type Value;
@@ -239 +239 @@
     template <typename Graph, typename In, typename Out>
     struct KruskalOutputSelector<Graph, In, Out,
-      typename enable_if<MapOutputIndicator<Out>, void>::type > 
+      typename enable_if<MapOutputIndicator<Out>, void>::type >
     {
       typedef typename In::value_type::second_type Value;
@@ -255 +255 @@
   /// 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
@@ -273 +273 @@
   /// along with the assigned cost. <em>They must be in a
   /// cost-ascending order.</em>
-  /// - 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.
   ///
@@ -293 +293 @@
   ///\endcode
   /// Or if we don't know in advance the size of the tree, we can
-  /// write this.  
+  /// write this.
   ///\code
   /// std::vector<Arc> tree;
-  /// kruskal(g,cost,std::back_inserter(tree)); 
+  /// kruskal(g,cost,std::back_inserter(tree));
   ///\endcode
   ///
@@ -308 +308 @@
   template <class Graph, class In, class Out>
   Value kruskal(GR const& g, const In& in, Out& out)
-#else 
+#else
   template <class Graph, class In, class Out>
-  inline typename _kruskal_bits::KruskalValueSelector<In>::Value 
-  kruskal(const Graph& graph, const In& in, Out& out) 
+  inline typename _kruskal_bits::KruskalValueSelector<In>::Value
+  kruskal(const Graph& graph, const In& in, Out& out)
 #endif
   {
@@ -318 +318 @@
   }
 
- 
-  
+
+
 
   template <class Graph, class In, class Out>
@@ -327 +327 @@
     return _kruskal_bits::KruskalInputSelector<Graph, In, const Out>::
       kruskal(graph, in, out);
-  }  
+  }
 
 } //namespace lemon