diff -r d8475431bbbb -r 8e85e6bbefdf lemon/kruskal.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/kruskal.h	Mon May 23 04:48:14 2005 +0000
@@ -0,0 +1,348 @@
+/* -*- C++ -*-
+ * lemon/kruskal.h - Part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_KRUSKAL_H
+#define LEMON_KRUSKAL_H
+
+#include <algorithm>
+#include <lemon/unionfind.h>
+
+/**
+@defgroup spantree Minimum Cost Spanning Tree Algorithms
+@ingroup galgs
+\brief This group containes the algorithms for finding a minimum cost spanning
+tree in a graph
+
+This group containes the algorithms for finding a minimum cost spanning
+tree in a graph
+*/
+
+///\ingroup spantree
+///\file
+///\brief Kruskal's algorithm to compute a minimum cost tree
+///
+///Kruskal's algorithm to compute a minimum cost tree.
+
+namespace lemon {
+
+  /// \addtogroup spantree
+  /// @{
+
+  /// Kruskal's algorithm to find a minimum cost tree of a graph.
+
+  /// This function runs Kruskal's algorithm to find a minimum cost tree.
+  /// \param G The graph the algorithm runs on. The algorithm considers the
+  /// graph to be undirected, the direction of the edges are not used.
+  ///
+  /// \param in This object is used to describe the edge costs. It must
+  /// be an STL compatible 'Forward Container'
+  /// with <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>,
+  /// where X is the type of the costs. It must contain every edge in
+  /// cost-ascending order.
+  ///\par
+  /// For the sake of simplicity, there is a helper class KruskalMapInput,
+  /// which converts a
+  /// simple edge map to an input of this form. Alternatively, you can use
+  /// the function \ref kruskalEdgeMap to compute the minimum cost tree if
+  /// the edge costs are given by an edge map.
+  ///
+  /// \retval out This must be a writable \c bool edge map.
+  /// After running the algorithm
+  /// this will contain the found minimum cost spanning tree: the value of an
+  /// edge will be set to \c true if it belongs to the tree, otherwise it will
+  /// be set to \c false. The value of each edge will be set exactly once.
+  ///
+  /// \return The cost of the found tree.
+
+  template <class GR, class IN, class OUT>
+  typename IN::value_type::second_type
+  kruskal(GR const& G, IN const& in, 
+		 OUT& out)
+  {
+    typedef typename IN::value_type::second_type EdgeCost;
+    typedef typename GR::template NodeMap<int> NodeIntMap;
+    typedef typename GR::Node Node;
+
+    NodeIntMap comp(G, -1);
+    UnionFind<Node,NodeIntMap> uf(comp); 
+      
+    EdgeCost tot_cost = 0;
+    for (typename IN::const_iterator p = in.begin(); 
+	 p!=in.end(); ++p ) {
+      if ( uf.join(G.target((*p).first),
+		   G.source((*p).first)) ) {
+	out.set((*p).first, true);
+	tot_cost += (*p).second;
+      }
+      else {
+	out.set((*p).first, false);
+      }
+    }
+    return tot_cost;
+  }
+
+  /* A work-around for running Kruskal with const-reference bool maps... */
+
+  /// Helper class for calling kruskal with "constant" output map.
+
+  /// Helper class for calling kruskal with output maps constructed
+  /// on-the-fly.
+  ///
+  /// A typical examle is the following call:
+  /// <tt>kruskal(G, some_input, makeSequenceOutput(iterator))</tt>.
+  /// Here, the third argument is a temporary object (which wraps around an
+  /// iterator with a writable bool map interface), and thus by rules of C++
+  /// is a \c const object. To enable call like this exist this class and
+  /// the prototype of the \ref kruskal() function with <tt>const& OUT</tt>
+  /// third argument.
+  template<class Map>
+  class NonConstMapWr {
+    const Map &m;
+  public:
+    typedef typename Map::Value Value;
+
+    NonConstMapWr(const Map &_m) : m(_m) {}
+
+    template<class Key>
+    void set(Key const& k, Value const &v) const { m.set(k,v); }
+  };
+
+  template <class GR, class IN, class OUT>
+  inline
+  typename IN::value_type::second_type
+  kruskal(GR const& G, IN const& edges, OUT const& out_map)
+  {
+    NonConstMapWr<OUT> map_wr(out_map);
+    return kruskal(G, edges, map_wr);
+  }  
+
+  /* ** ** Input-objects ** ** */
+
+  /// Kruskal's input source.
+
+  /// Kruskal's input source.
+  ///
+  /// In most cases you possibly want to use the \ref kruskalEdgeMap() instead.
+  ///
+  /// \sa makeKruskalMapInput()
+  ///
+  ///\param GR The type of the graph the algorithm runs on.
+  ///\param Map An edge map containing the cost of the edges.
+  ///\par
+  ///The cost type can be any type satisfying
+  ///the STL 'LessThan comparable'
+  ///concept if it also has an operator+() implemented. (It is necessary for
+  ///computing the total cost of the tree).
+  ///
+  template<class GR, class Map>
+  class KruskalMapInput
+    : public std::vector< std::pair<typename GR::Edge,
+				    typename Map::Value> > {
+    
+  public:
+    typedef std::vector< std::pair<typename GR::Edge,
+				   typename Map::Value> > Parent;
+    typedef typename Parent::value_type value_type;
+
+  private:
+    class comparePair {
+    public:
+      bool operator()(const value_type& a,
+		      const value_type& b) {
+	return a.second < b.second;
+      }
+    };
+
+  public:
+
+    void sort() {
+      std::sort(this->begin(), this->end(), comparePair());
+    }
+
+    KruskalMapInput(GR const& G, Map const& m) {
+      typedef typename GR::EdgeIt EdgeIt;
+      
+      for(EdgeIt e(G);e!=INVALID;++e) push_back(value_type(e, m[e]));
+      sort();
+    }
+  };
+
+  /// Creates a KruskalMapInput object for \ref kruskal()
+
+  /// It makes easier to use 
+  /// \ref KruskalMapInput by making it unnecessary 
+  /// to explicitly give the type of the parameters.
+  ///
+  /// In most cases you possibly
+  /// want to use the function kruskalEdgeMap() instead.
+  ///
+  ///\param G The type of the graph the algorithm runs on.
+  ///\param m An edge map containing the cost of the edges.
+  ///\par
+  ///The cost type can be any type satisfying the
+  ///STL 'LessThan Comparable'
+  ///concept if it also has an operator+() implemented. (It is necessary for
+  ///computing the total cost of the tree).
+  ///
+  ///\return An appropriate input source for \ref kruskal().
+  ///
+  template<class GR, class Map>
+  inline
+  KruskalMapInput<GR,Map> makeKruskalMapInput(const GR &G,const Map &m)
+  {
+    return KruskalMapInput<GR,Map>(G,m);
+  }
+  
+  
+
+  /* ** ** Output-objects: simple writable bool maps ** ** */
+  
+
+
+  /// A writable bool-map that makes a sequence of "true" keys
+
+  /// A writable bool-map that creates a sequence out of keys that receives
+  /// the value "true".
+  ///
+  /// \sa makeKruskalSequenceOutput()
+  ///
+  /// Very often, when looking for a min cost spanning tree, we want as
+  /// output a container containing the edges of the found tree. For this
+  /// purpose exist this class that wraps around an STL iterator with a
+  /// writable bool map interface. When a key gets value "true" this key
+  /// is added to sequence pointed by the iterator.
+  ///
+  /// A typical usage:
+  /// \code
+  /// std::vector<Graph::Edge> v;
+  /// kruskal(g, input, makeKruskalSequenceOutput(back_inserter(v)));
+  /// \endcode
+  /// 
+  /// For the most common case, when the input is given by a simple edge
+  /// map and the output is a sequence of the tree edges, a special
+  /// wrapper function exists: \ref kruskalEdgeMap_IteratorOut().
+  ///
+  /// \warning Not a regular property map, as it doesn't know its Key
+
+  template<class Iterator>
+  class KruskalSequenceOutput {
+    mutable Iterator it;
+
+  public:
+    typedef bool Value;
+
+    KruskalSequenceOutput(Iterator const &_it) : it(_it) {}
+
+    template<typename Key>
+    void set(Key const& k, bool v) const { if(v) {*it=k; ++it;} }
+  };
+
+  template<class Iterator>
+  inline
+  KruskalSequenceOutput<Iterator>
+  makeKruskalSequenceOutput(Iterator it) {
+    return KruskalSequenceOutput<Iterator>(it);
+  }
+
+
+
+  /* ** ** Wrapper funtions ** ** */
+
+
+
+  /// \brief Wrapper function to kruskal().
+  /// Input is from an edge map, output is a plain bool map.
+  ///
+  /// Wrapper function to kruskal().
+  /// Input is from an edge map, output is a plain bool map.
+  ///
+  ///\param G The type of the graph the algorithm runs on.
+  ///\param in An edge map containing the cost of the edges.
+  ///\par
+  ///The cost type can be any type satisfying the
+  ///STL 'LessThan Comparable'
+  ///concept if it also has an operator+() implemented. (It is necessary for
+  ///computing the total cost of the tree).
+  ///
+  /// \retval out This must be a writable \c bool edge map.
+  /// After running the algorithm
+  /// this will contain the found minimum cost spanning tree: the value of an
+  /// edge will be set to \c true if it belongs to the tree, otherwise it will
+  /// be set to \c false. The value of each edge will be set exactly once.
+  ///
+  /// \return The cost of the found tree.
+
+  template <class GR, class IN, class RET>
+  inline
+  typename IN::Value
+  kruskalEdgeMap(GR const& G,
+		 IN const& in,
+		 RET &out) {
+    return kruskal(G,
+		   KruskalMapInput<GR,IN>(G,in),
+		   out);
+  }
+
+  /// \brief Wrapper function to kruskal().
+  /// Input is from an edge map, output is an STL Sequence.
+  ///
+  /// Wrapper function to kruskal().
+  /// Input is from an edge map, output is an STL Sequence.
+  ///
+  ///\param G The type of the graph the algorithm runs on.
+  ///\param in An edge map containing the cost of the edges.
+  ///\par
+  ///The cost type can be any type satisfying the
+  ///STL 'LessThan Comparable'
+  ///concept if it also has an operator+() implemented. (It is necessary for
+  ///computing the total cost of the tree).
+  ///
+  /// \retval out This must be an iteraror of an STL Container with
+  /// <tt>GR::Edge</tt> as its <tt>value_type</tt>.
+  /// The algorithm copies the elements of the found tree into this sequence.
+  /// For example, if we know that the spanning tree of the graph \c G has
+  /// say 53 edges then
+  /// we can put its edges into a STL vector \c tree with a code like this.
+  /// \code
+  /// std::vector<Edge> tree(53);
+  /// kruskalEdgeMap_IteratorOut(G,cost,tree.begin());
+  /// \endcode
+  /// Or if we don't know in advance the size of the tree, we can write this.
+  /// \code
+  /// std::vector<Edge> tree;
+  /// kruskalEdgeMap_IteratorOut(G,cost,std::back_inserter(tree));
+  /// \endcode
+  ///
+  /// \return The cost of the found tree.
+  ///
+  /// \bug its name does not follow the coding style.
+
+  template <class GR, class IN, class RET>
+  inline
+  typename IN::Value
+  kruskalEdgeMap_IteratorOut(const GR& G,
+			     const IN& in,
+			     RET out)
+  {
+    KruskalSequenceOutput<RET> _out(out);
+    return kruskal(G, KruskalMapInput<GR,IN>(G, in), _out);
+  }
+
+  /// @}
+
+} //namespace lemon
+
+#endif //LEMON_KRUSKAL_H