Changeset 2424:95cd24940d00 in lemon-0.x

Timestamp:

04/19/07 17:11:58 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3260

Message:

Redesigned Kruskal algorithm

The interface of function type implementation is not changed
Additional class type implementation

Files:

• lemon/kruskal.h (modified) (3 diffs)
• test/kruskal_test.cc (modified) (7 diffs)

lemon/kruskal.h

@@ -23 +23 @@
 #include <vector>
 #include <lemon/unionfind.h>
+#include <lemon/graph_utils.h>
+#include <lemon/maps.h>
+
+#include <lemon/radix_sort.h>
+
 #include <lemon/bits/utility.h>
 #include <lemon/bits/traits.h>
@@ -35 +40 @@
 namespace lemon {
 
-  /// \addtogroup spantree
-  /// @{
-
-  /// Kruskal's algorithm to find a minimum cost tree of a graph.
-
+  namespace _kruskal_bits {
+
+    template <typename Map, typename Comp>
+    struct MappedComp {
+
+      typedef typename Map::Key Key;
+
+      const Map& map;
+      Comp comp;
+
+      MappedComp(const Map& _map) 
+        : map(_map), comp() {}
+
+      bool operator()(const Key& left, const Key& right) {
+        return comp(map[left], map[right]);
+      }
+
+    };
+  
+  }
+
+  /// \ingroup spantree
+  ///
+  /// \brief Default traits class of Kruskal class.
+  ///
+  /// Default traits class of Kruskal class.
+  /// \param _UGraph Undirected graph type.
+  /// \param _CostMap Type of cost map.
+  template <typename _UGraph, typename _CostMap>
+  struct KruskalDefaultTraits{
+
+    /// \brief The graph type the algorithm runs on. 
+    typedef _UGraph UGraph;
+
+    /// \brief The type of the map that stores the edge costs.
+    ///
+    /// The type of the map that stores the edge costs.
+    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
+    typedef _CostMap CostMap;
+
+    /// \brief The type of the cost of the edges.
+    typedef typename _CostMap::Value Value;
+
+    /// \brief The type of the map that stores whether an edge is in the
+    /// spanning tree or not.
+    ///
+    /// The type of the map that stores whether an edge is in the
+    /// spanning tree or not.
+    typedef typename _UGraph::template UEdgeMap<bool> TreeMap;
+
+    /// \brief Instantiates a TreeMap.
+    ///
+    /// This function instantiates a \ref TreeMap.
+    ///
+    /// The first parameter is the graph, to which
+    /// we would like to define the \ref TreeMap
+    static TreeMap *createTreeMap(const _UGraph& graph){
+      return new TreeMap(graph);
+    }
+
+    template <typename Iterator>
+    static void sort(Iterator begin, Iterator end, const CostMap& cost) {
+      _kruskal_bits::MappedComp<CostMap, std::less<Value> > comp(cost);
+      std::sort(begin, end, comp);
+    }
+
+  };
+
+  /// \brief Kruskal's algorithm to find a minimum cost tree of a graph.
+  ///
+  /// This class implements Kruskal's algorithm to find a minimum cost
+  /// spanning tree. The 
+  ///
+  /// \param _UGraph Undirected graph type.
+  /// \param _CostMap Type of cost map.
+  template <typename _UGraph, typename _CostMap,
+            typename _Traits = KruskalDefaultTraits<_UGraph, _CostMap> >
+  class Kruskal {
+  public:
+
+    typedef _Traits Traits;
+
+    typedef typename _Traits::UGraph UGraph;
+    typedef typename _Traits::CostMap CostMap;
+
+    typedef typename _Traits::TreeMap TreeMap;
+
+    typedef typename _Traits::Value Value;
+
+    template <typename Comp>
+    struct DefSortCompareTraits : public Traits {
+      template <typename Iterator>
+      static void sort(Iterator begin, Iterator end, const CostMap& cost) {
+        _kruskal_bits::MappedComp<CostMap, Comp> comp(cost, Comp());
+        std::sort(begin, end, comp);
+      }
+    };
+
+    /// \brief \ref named-templ-param "Named parameter" for setting the
+    /// comparator object of the standard sort
+    ///
+    /// \ref named-templ-param "Named parameter" for setting the
+    /// comparator object of the standard sort
+    template <typename Comp>
+    struct DefSortCompare
+      : public Kruskal<UGraph, CostMap, DefSortCompareTraits<Comp> > {
+      typedef Kruskal<UGraph, CostMap, DefSortCompareTraits<Comp> > Create;
+    };    
+
+    struct DefRadixSortTraits : public Traits {
+      template <typename Iterator>
+      static void sort(Iterator begin, Iterator end, const CostMap& cost) {
+        radixSort(begin, end, cost);
+      }
+    };
+
+    /// \brief \ref named-templ-param "Named parameter" for setting the
+    /// sort function to radix sort
+    ///
+    /// \brief \ref named-templ-param "Named parameter" for setting the
+    /// sort function to radix sort. The value type of the cost map should
+    /// be integral, of course. 
+    struct DefRadixSort
+      : public Kruskal<UGraph, CostMap, DefRadixSortTraits> {
+      typedef Kruskal<UGraph, CostMap, DefRadixSortTraits> Create;
+    };    
+
+    template <class TM>
+    struct DefTreeMapTraits : public Traits {
+      typedef TM TreeMap;
+      static TreeMap *createTreeMap(const UGraph &) {
+        throw UninitializedParameter();
+      }
+    };
+
+    /// \brief \ref named-templ-param "Named parameter" for setting
+    /// TreeMap
+    ///
+    /// \ref named-templ-param "Named parameter" for setting TreeMap
+    ///
+    template <class TM>
+    struct DefTreeMap
+      : public Kruskal< UGraph, CostMap, DefTreeMapTraits<TM> > {
+      typedef Kruskal< UGraph, CostMap, DefTreeMapTraits<TM> > Create;
+    };    
+    
+
+  private:
+
+    typedef typename UGraph::Node Node;
+    typedef typename UGraph::NodeIt NodeIt;
+
+    typedef typename UGraph::UEdge UEdge;
+    typedef typename UGraph::UEdgeIt UEdgeIt;
+
+    const UGraph& graph;
+    const CostMap& cost;
+    
+    std::vector<UEdge> edges;
+    
+    typedef typename UGraph::template NodeMap<int> UfIndex;
+    typedef UnionFind<UfIndex> Uf;
+    UfIndex *ufi;
+    Uf *uf;
+
+    int index;
+
+    void initStructures() {
+      if (!_tree) {
+        _tree = Traits::createTreeMap(graph);
+        local_tree = true;
+      }
+      if (!uf) {
+        ufi = new typename UGraph::template NodeMap<int>(graph);
+        uf = new UnionFind<typename UGraph::template NodeMap<int> >(*ufi);
+      }
+    }
+    
+    void initUnionFind() {
+      uf->clear();
+      for (NodeIt it(graph); it != INVALID; ++it) {
+        uf->insert(it);
+      }
+    }
+
+    bool local_tree;
+    TreeMap* _tree;
+
+  public:
+
+    /// \brief Constructor
+    ///
+    /// Constructor of the algorithm.
+    Kruskal(const UGraph& _graph, const CostMap& _cost) 
+      : graph(_graph), cost(_cost),
+        ufi(0), uf(0), local_tree(false), _tree(0) {}
+
+    /// \brief Destructor
+    ///
+    /// Destructor
+    ~Kruskal() {
+      if (local_tree) {
+        delete _tree;
+      }
+      if (uf) {
+        delete uf;
+        delete ufi;
+      }
+    }
+
+    /// \brief Sets the map storing the tree edges.
+    ///
+    /// Sets the map storing the tree edges.
+    /// If you don't use this function before calling \ref run(),
+    /// it will allocate one. The destuctor deallocates this
+    /// automatically allocated map, of course.
+    /// \return \c *this </tt>
+    Kruskal& treeMap(TreeMap &m){
+      if (local_tree) {
+        delete _tree;
+        local_tree = false;
+      }
+      _tree = &m;
+      return *this;
+    }
+
+    /// \brief Initialize the algorithm
+    ///
+    /// This member function initializes the unionfind data structure
+    /// and sorts the edges into ascending order
+    void init() {
+      initStructures();
+      initUnionFind();
+      for (UEdgeIt e(graph); e != INVALID; ++e) {
+        edges.push_back(e);
+        _tree->set(e, false);
+      }      
+      Traits::sort(edges.begin(), edges.end(), cost); 
+      index = 0;
+    }
+
+
+    /// \brief Initialize the algorithm
+    ///
+    /// This member function initializes the unionfind data structure
+    /// and sets the edge order to the given sequence. The given
+    /// sequence should be a valid STL range of undirected edges.
+    template <typename Iterator>
+    void initPresorted(Iterator begin, Iterator end) {
+      initStructures();
+      initUnionFind();
+      edges.clear();
+      std::copy(begin, end, std::back_inserter(edges));
+      index = 0;
+    }
+
+    /// \brief Initialize the algorithm
+    ///
+    /// This member function initializes the unionfind data structure
+    /// and sets the edge order to the given sequence. The given
+    /// sequence should be a valid STL range of undirected edges.
+    void reinit() {
+      initStructures();
+      initUnionFind();
+      for (UEdgeIt e(graph); e != INVALID; ++e) {
+        _tree->set(e, false);
+      }
+      index = 0;
+    }
+
+
+    /// \brief Executes the algorithm.
+    ///
+    /// Executes the algorithm.
+    ///
+    /// \pre init() must be called before using this function.
+    ///
+    /// This method runs the %Kruskal algorithm.
+    void start() {
+      while (index < int(edges.size())) {
+        if (uf->join(graph.target(edges[index]), graph.source(edges[index]))) {
+          _tree->set(edges[index], true);
+        }
+        ++index;
+      }
+    }
+
+    /// \brief Runs the prim algorithm until it find a new tree edge
+    ///
+    /// Runs the prim algorithm until it find a new tree edge. If it
+    /// does not next tree edge in the sequence it gives back \c INVALID.
+    UEdge findNextTreeEdge() {
+      while (index < int(edges.size())) {
+        if (uf->join(graph.target(edges[index]), graph.source(edges[index]))) {
+          _tree->set(edges[index], true);
+          return edges[index++];
+        }        
+        ++index;
+      }
+      return INVALID;
+    }
+      
+    /// \brief Processes the next edge in the sequence
+    ///
+    /// Processes the next edge in the sequence.
+    ///
+    /// \return The prcocessed edge.
+    ///
+    /// \warning The sequence must not be empty!
+    UEdge processNextEdge() {
+      UEdge edge = edges[index++];
+      processEdge(edge);
+      return edge;
+    }
+
+    /// \brief Processes an arbitrary edge
+    ///
+    /// Processes the next edge in the sequence.
+    ///
+    /// \return True when the edge is a tree edge.
+    bool processEdge(const UEdge& edge) {
+      if (uf->join(graph.target(edge), graph.source(edge))) {
+        _tree->set(edge, true);
+        return true;
+      } else {
+        return false;
+      }    
+    }
+
+    /// \brief Returns \c false if there are edge to be processed in
+    /// sequence
+    ///
+    /// Returns \c false if there are nodes to be processed in the
+    /// sequence
+    bool emptyQueue() {
+      return index == int(edges.size());
+    }
+
+    /// \brief Returns the next edge to be processed
+    ///
+    /// Returns the next edge to be processed
+    ///
+    UEdge nextEdge() const {
+      return edges[index];
+    }
+
+    /// \brief Runs %Kruskal algorithm.
+    ///
+    /// This method runs the %Kruskal algorithm in order to compute the
+    /// minimum spanning tree (or minimum spanning forest).  The
+    /// method also works on graphs that has more than one components.
+    /// In this case it computes the minimum spanning forest.
+    void run() {
+      init();
+      start();
+    }
+
+    /// \brief Returns a reference to the tree edges map
+    ///
+    /// Returns a reference to the TreeEdgeMap of the edges of the
+    /// minimum spanning tree. The value of the map is \c true only if
+    /// the edge is in the minimum spanning tree.
+    ///
+    const TreeMap &treeMap() const { return *_tree;}
+
+    /// \brief Returns the total cost of the tree
+    ///
+    /// Returns the total cost of the tree
+    Value treeValue() const {
+      Value value = 0;
+      for (UEdgeIt it(graph); it != INVALID; ++it) {
+        if ((*_tree)[it]) {
+          value += cost[it];
+        }
+      }
+      return value;
+    }
+
+    /// \brief Returns true when the given edge is tree edge
+    ///
+    /// Returns true when the given edge is tree edge
+    bool tree(UEdge e) const {
+      return (*_tree)[e];
+    }
+    
+    
+  };
+
+
+  namespace _kruskal_bits {
+
+    template <typename Graph, typename In, typename Out>
+    typename In::value_type::second_type
+    kruskal(const Graph& graph, const In& in, Out& out) {
+      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);
+      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.target(it->first),graph.source(it->first))) {
+          out.set(it->first, true);
+          tree_value += it->second;
+        }
+        else {
+          out.set(it->first, false);
+        }
+      }
+      return tree_value;
+    }
+
+
+    template <typename Sequence>
+    struct PairComp {
+      typedef typename Sequence::value_type Value;
+      bool operator()(const Value& left, const Value& right) {
+        return left.second < right.second;
+      }
+    };
+
+    template <typename In, typename Enable = void>
+    struct SequenceInputIndicator {
+      static const bool value = false;
+    };
+
+    template <typename In>
+    struct SequenceInputIndicator<In, 
+      typename exists<typename In::value_type::first_type>::type> {
+      static const bool value = true;
+    };
+
+    template <typename In, typename Enable = void>
+    struct MapInputIndicator {
+      static const bool value = false;
+    };
+
+    template <typename In>
+    struct MapInputIndicator<In, 
+      typename exists<typename In::Value>::type> {
+      static const bool value = true;
+    };
+
+    template <typename In, typename Enable = void>
+    struct SequenceOutputIndicator {
+      static const bool value = false;
+    };
+ 
+    template <typename Out>
+    struct SequenceOutputIndicator<Out, 
+      typename exists<typename Out::value_type>::type> {
+      static const bool value = true;
+    };
+
+    template <typename Out, typename Enable = void>
+    struct MapOutputIndicator {
+      static const bool value = false;
+    };
+
+    template <typename Out>
+    struct MapOutputIndicator<Out, 
+      typename exists<typename Out::Value>::type> {
+      static const bool value = true;
+    };
+
+    template <typename In, typename InEnable = void>
+    struct KruskalValueSelector {};
+
+    template <typename In>
+    struct KruskalValueSelector<In,
+      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> 
+    {
+      typedef typename In::Value Value;
+    };    
+    
+    template <typename Graph, typename In, typename Out,
+              typename InEnable = void>
+    struct KruskalInputSelector {};
+
+    template <typename Graph, typename In, typename Out,
+              typename InEnable = void>
+    struct KruskalOutputSelector {};
+    
+    template <typename Graph, typename In, typename Out>
+    struct KruskalInputSelector<Graph, In, Out,
+      typename enable_if<SequenceInputIndicator<In>, void>::type > 
+    {
+      typedef typename In::value_type::second_type Value;
+
+      static Value kruskal(const Graph& graph, const In& in, Out& out) {
+        return KruskalOutputSelector<Graph, In, Out>::
+          kruskal(graph, in, out);
+      }
+
+    };
+
+    template <typename Graph, typename In, typename Out>
+    struct KruskalInputSelector<Graph, In, Out,
+      typename enable_if<MapInputIndicator<In>, void>::type > 
+    {
+      typedef typename In::Value Value;
+      static Value kruskal(const Graph& graph, const In& in, Out& out) {
+        typedef typename In::Key MapEdge;
+        typedef typename In::Value Value;
+        typedef typename ItemSetTraits<Graph, MapEdge>::ItemIt MapEdgeIt;
+        typedef std::vector<std::pair<MapEdge, Value> > Sequence;
+        Sequence seq;
+        
+        for (MapEdgeIt it(graph); it != INVALID; ++it) {
+          seq.push_back(make_pair(it, in[it]));
+        }
+
+        std::sort(seq.begin(), seq.end(), PairComp<Sequence>());
+        return KruskalOutputSelector<Graph, Sequence, Out>::
+          kruskal(graph, seq, out);
+      }
+    };
+
+    template <typename Graph, typename In, typename Out>
+    struct KruskalOutputSelector<Graph, In, Out,
+      typename enable_if<SequenceOutputIndicator<Out>, void>::type > 
+    {
+      typedef typename In::value_type::second_type Value;
+
+      static Value kruskal(const Graph& graph, const In& in, Out& out) {
+        typedef StoreBoolMap<Out> Map;
+        Map map(out);
+        return _kruskal_bits::kruskal(graph, in, map);
+      }
+
+    };
+
+    template <typename Graph, typename In, typename Out>
+    struct KruskalOutputSelector<Graph, In, Out,
+      typename enable_if<MapOutputIndicator<Out>, void>::type > 
+    {
+      typedef typename In::value_type::second_type Value;
+
+      static Value kruskal(const Graph& graph, const In& in, Out& out) {
+        return _kruskal_bits::kruskal(graph, in, out);
+      }
+    };
+
+  }
+
+  /// \ingroup spantree
+  ///
+  /// \brief Kruskal's algorithm to find a minimum cost tree of a graph.
+  ///
   /// This function runs Kruskal's algorithm to find a minimum cost tree.
   /// Due to hard C++ hacking, it accepts various input and output types.
@@ -51 +612 @@
   /// \param in This object is used to describe the edge costs. It can be one
   /// of the following choices.
-  /// - An STL compatible 'Forward Container'
-  /// with <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>,
-  /// where \c X is the type of the costs. The pairs indicates the edges along
-  /// with the assigned cost. <em>They must be in a
+  ///
+  /// - An STL compatible 'Forward Container' with
+  /// <tt>std::pair<GR::UEdge,X></tt> or
+  /// <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>, where
+  /// \c X is the type of the costs. The pairs indicates the edges
+  /// along with the assigned cost. <em>They must be in a
   /// cost-ascending order.</em>
   /// - Any readable Edge map. The values of the map indicate the edge costs.
   ///
   /// \retval out Here we also have a choise.
-  /// - It can 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.
+  /// - It can 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.
   /// - It can also 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 an STL vector \c tree with a code like this.
+  /// <tt>GR::UEdge</tt> or <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 an STL vector \c tree with a code like this.
   ///\code
   /// std::vector<Edge> tree(53);
   /// kruskal(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;
-  /// kruskal(g,cost,std::back_inserter(tree));
+  /// Or if we don't know in advance the size of the tree, we can
+  /// write this.  
+  ///\code std::vector<Edge> tree;
+  /// kruskal(g,cost,std::back_inserter(tree)); 
   ///\endcode
   ///
-  /// \return The cost of the found tree.
-  ///
-  /// \warning If kruskal runs on an
-  /// \ref lemon::concepts::UGraph "undirected graph", be sure that the
-  /// map storing the tree is also undirected
-  /// (e.g. ListUGraph::UEdgeMap<bool>, otherwise the values of the
-  /// half of the edges will not be set.
+  /// \return The total cost of the found tree.
+  ///
+  /// \warning If kruskal runs on an be consistent of using the same
+  /// Edge type for input and output.
   ///
 
 #ifdef DOXYGEN
-  template <class GR, class IN, class OUT>
-  CostType
-  kruskal(GR const& g, IN const& in, 
-          OUT& out)
-#else
-  template <class GR, class IN, class OUT>
-  typename IN::value_type::second_type
-  kruskal(GR const& g, IN const& in, 
-          OUT& out,
-//        typename IN::value_type::first_type = typename GR::Edge()
-//        ,typename OUT::Key = OUT::Key()
-//        //,typename OUT::Key = typename GR::Edge()
-          const typename IN::value_type::first_type * = 
-          reinterpret_cast<const typename IN::value_type::first_type*>(0),
-          const typename OUT::Key * = 
-          reinterpret_cast<const typename OUT::Key*>(0)
-          )
+  template <class Graph, class In, class Out>
+  Value kruskal(GR const& g, const In& in, Out& out)
+#else 
+  template <class Graph, class In, class Out>
+  inline typename _kruskal_bits::KruskalValueSelector<In>::Value 
+  kruskal(const Graph& graph, const In& in, Out& out) 
 #endif
   {
-    typedef typename IN::value_type::second_type EdgeCost;
-    typedef typename GR::template NodeMap<int> NodeIntMap;
-    typedef typename GR::Node Node;
-
-    NodeIntMap comp(g);
-    UnionFind<NodeIntMap> uf(comp);
-    for (typename GR::NodeIt it(g); it != INVALID; ++it) {
-      uf.insert(it);
-    }
-      
-    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;
+    return _kruskal_bits::KruskalInputSelector<Graph, In, Out>::
+      kruskal(graph, in, out);
   }
 
  
-  /// @}
-
   
-  /* 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::Key Key;
-    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,
-//        typename IN::value_type::first_type = typename GR::Edge(),
-//        typename OUT::Key = GR::Edge()
-          const typename IN::value_type::first_type * = 
-          reinterpret_cast<const typename IN::value_type::first_type*>(0),
-          const typename OUT::Key * = 
-          reinterpret_cast<const typename OUT::Key*>(0)
-          )
+
+  template <class Graph, class In, class Out>
+  inline typename _kruskal_bits::KruskalValueSelector<In>::Value
+  kruskal(const Graph& graph, const In& in, const Out& out)
   {
-    NonConstMapWr<OUT> map_wr(out_map);
-    return kruskal(g, edges, map_wr);
+    return _kruskal_bits::KruskalInputSelector<Graph, In, const Out>::
+      kruskal(graph, in, out);
   }  
 
-  /* ** ** Input-objects ** ** */
-
-  /// Kruskal's input source.
- 
-  /// Kruskal's input source.
-  ///
-  /// In most cases you possibly want to use the \ref kruskal() 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;
-      }
-    };
-
-    template<class _GR>
-    typename enable_if<UndirectedTagIndicator<_GR>,void>::type
-    fillWithEdges(const _GR& g, const Map& m,dummy<0> = 0) 
-    {
-      for(typename GR::UEdgeIt e(g);e!=INVALID;++e) 
-        push_back(value_type(g.direct(e, true), m[e]));
-    }
-
-    template<class _GR>
-    typename disable_if<UndirectedTagIndicator<_GR>,void>::type
-    fillWithEdges(const _GR& g, const Map& m,dummy<1> = 1) 
-    {
-      for(typename GR::EdgeIt e(g);e!=INVALID;++e) 
-        push_back(value_type(e, m[e]));
-    }
-    
-    
-  public:
-
-    void sort() {
-      std::sort(this->begin(), this->end(), comparePair());
-    }
-
-    KruskalMapInput(GR const& g, Map const& m) {
-      fillWithEdges(g,m); 
-      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 \ref kruskal() 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 typename std::iterator_traits<Iterator>::value_type Key;
-    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
-  kruskal(GR const& g,
-          IN const& in,
-          RET &out,
-          //      typename IN::Key = typename GR::Edge(),
-          //typename IN::Key = typename IN::Key (),
-          //      typename RET::Key = typename GR::Edge()
-          const typename IN::Key * = 
-          reinterpret_cast<const typename IN::Key*>(0),
-          const typename RET::Key * = 
-          reinterpret_cast<const typename RET::Key*>(0)
-          )
-  {
-    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 an STL vector \c tree with a code like this.
-//\code
-//   std::vector<Edge> tree(53);
-//   kruskal(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;
-//   kruskal(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
-  kruskal(const GR& g,
-          const IN& in,
-          RET out,
-          const typename RET::value_type * = 
-          reinterpret_cast<const typename RET::value_type*>(0)
-          )
-  {
-    KruskalSequenceOutput<RET> _out(out);
-    return kruskal(g, KruskalMapInput<GR,IN>(g, in), _out);
-  }
- 
-  template <class GR, class IN, class RET>
-  inline
-  typename IN::Value
-  kruskal(const GR& g,
-          const IN& in,
-          RET *out
-          )
-  {
-    KruskalSequenceOutput<RET*> _out(out);
-    return kruskal(g, KruskalMapInput<GR,IN>(g, in), _out);
-  }
- 
-  /// @}
-
 } //namespace lemon
 

test/kruskal_test.cc

@@ -24 +24 @@
 #include <lemon/kruskal.h>
 #include <lemon/list_graph.h>
+
 #include <lemon/concepts/maps.h>
 #include <lemon/concepts/graph.h>
+#include <lemon/concepts/ugraph.h>
 
 
@@ -34 +36 @@
 {
   concepts::WriteMap<concepts::Graph::Edge,bool> w;
+  concepts::WriteMap<concepts::UGraph::UEdge,bool> uw;
+
+  concepts::ReadMap<concepts::Graph::Edge,int> r;
+  concepts::ReadMap<concepts::UGraph::UEdge,int> ur;
 
   concepts::Graph g;
-  kruskal(g,
-          concepts::ReadMap<concepts::Graph::Edge,int>(),
-          w);
+  concepts::UGraph ug;
+
+  kruskal(g, r, w);
+  kruskal(ug, ur, uw);
+
+  std::vector<std::pair<concepts::Graph::Edge, int> > rs;
+  std::vector<std::pair<concepts::UGraph::UEdge, int> > urs;
+
+  kruskal(g, rs, w);
+  kruskal(ug, urs, uw);
+
+  std::vector<concepts::Graph::Edge> ws;
+  std::vector<concepts::UGraph::UEdge> uws;
+
+  kruskal(g, r, ws.begin());
+  kruskal(ug, ur, uws.begin());
+
+  Kruskal<concepts::UGraph,concepts::ReadMap<concepts::UGraph::UEdge,int> >
+    alg(ug, ur);
+
+  alg.init();
+  alg.initPresorted(uws.begin(), uws.end());
+  alg.reinit();
+  
+  alg.emptyQueue();
+  
+  alg.nextEdge();
+  alg.processNextEdge();
+  alg.processEdge(concepts::UGraph::UEdge());
+
+  alg.run();
+  
+  alg.treeMap();
+  alg.tree(concepts::UGraph::UEdge());
 }
 
 int main() {
 
-  typedef ListGraph::Node Node;
-  typedef ListGraph::Edge Edge;
-  typedef ListGraph::NodeIt NodeIt;
-  typedef ListGraph::EdgeIt EdgeIt;
+  typedef ListUGraph::Node Node;
+  typedef ListUGraph::UEdge UEdge;
+  typedef ListUGraph::NodeIt NodeIt;
+  typedef ListUGraph::EdgeIt EdgeIt;
 
-  ListGraph G;
+  ListUGraph G;
 
   Node s=G.addNode();
@@ -57 +94 @@
   Node t=G.addNode();
   
-  Edge e1 = G.addEdge(s, v1);
-  Edge e2 = G.addEdge(s, v2);
-  Edge e3 = G.addEdge(v1, v2);
-  Edge e4 = G.addEdge(v2, v1);
-  Edge e5 = G.addEdge(v1, v3);
-  Edge e6 = G.addEdge(v3, v2);
-  Edge e7 = G.addEdge(v2, v4);
-  Edge e8 = G.addEdge(v4, v3);
-  Edge e9 = G.addEdge(v3, t);
-  Edge e10 = G.addEdge(v4, t);
+  UEdge e1 = G.addEdge(s, v1);
+  UEdge e2 = G.addEdge(s, v2);
+  UEdge e3 = G.addEdge(v1, v2);
+  UEdge e4 = G.addEdge(v2, v1);
+  UEdge e5 = G.addEdge(v1, v3);
+  UEdge e6 = G.addEdge(v3, v2);
+  UEdge e7 = G.addEdge(v2, v4);
+  UEdge e8 = G.addEdge(v4, v3);
+  UEdge e9 = G.addEdge(v3, t);
+  UEdge e10 = G.addEdge(v4, t);
 
-  typedef ListGraph::EdgeMap<int> ECostMap;
-  typedef ListGraph::EdgeMap<bool> EBoolMap;
+  typedef ListUGraph::UEdgeMap<int> ECostMap;
+  typedef ListUGraph::UEdgeMap<bool> EBoolMap;
 
   ECostMap edge_cost_map(G, 2);
@@ -76 +113 @@
 
   //Test with const map.
-  check(kruskal(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10,
+  check(kruskal(G, ConstMap<ListUGraph::UEdge,int>(2), tree_map)==10,
         "Total cost should be 10");
   //Test with a edge map (filled with uniform costs).
@@ -93 +130 @@
   edge_cost_map.set(e10, -1);
 
-  vector<Edge> tree_edge_vec(5);
+  vector<UEdge> tree_edge_vec(5);
 
   //Test with a edge map and inserter.
@@ -108 +145 @@
         "Total cost should be -31.");
   
-  tree_edge_vec.clear();
+//   tree_edge_vec.clear();
   
-  //The above test could also be coded like this:
-  check(kruskal(G,
-                makeKruskalMapInput(G, edge_cost_map),
-                makeKruskalSequenceOutput(back_inserter(tree_edge_vec)))
-        ==-31,
-        "Total cost should be -31.");
+//   //The above test could also be coded like this:
+//   check(kruskal(G,
+//              makeKruskalMapInput(G, edge_cost_map),
+//              makeKruskalSequenceOutput(back_inserter(tree_edge_vec)))
+//      ==-31,
+//      "Total cost should be -31.");
 
   check(tree_edge_vec.size()==5,"The tree should have 5 edges.");
@@ -126 +163 @@
         "Wrong tree.");
 
+  Kruskal<ListUGraph, ECostMap> ka(G, edge_cost_map);
+  
+  ka.run();
+  
+  check(ka.tree(e1) && 
+        ka.tree(e2) &&
+        ka.tree(e5) &&
+        ka.tree(e7) &&
+        ka.tree(e9),
+        "Wrong tree.");
+
+  check(ka.treeValue() == -31,
+        "Total cost should be -31.");
+
   return 0;
 }