LEMON/LEMON-main Changeset - r104:b68a7e348e00

Repositories » LEMON » LEMON-main

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r104:b68a7e348e00

« 77:2de55e

105:e4948e »

r104:b68a7e348e00

Fri, 29 Feb 2008 12:01:39

[Not Reviewed]

0 comments (0 inline)

alpar (Alpar Juttner)
alpar@cs.elte.hu

Port kruskal() and UnionFind from svn -r3468 The class type interface of Kruskal has not been ported yet

0 2 4

default

6 files changed with 2386 insertions and 2 deletions:

lemon/kruskal.h

319

lemon/unionfind.h

1796

test/kruskal_test.cc

149

test/unionfind_test.cc

114

lemon/Makefile.am

test/Makefile.am

↑ Collapse diff ↑

lemon/kruskal.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
 		 * Copyright (C) 2003-2008
 		 * 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 <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>
 		///\ingroup spantree
 		///\file
 		///\brief Kruskal's algorithm to compute a minimum cost tree
 		///
 		///Kruskal's algorithm to compute a minimum cost tree.
 		///
 		namespace lemon {
 		  namespace _kruskal_bits {
 		    // Kruskal for directed graphs.
 		    template <typename Digraph, typename In, typename Out>
 		    typename disable_if<lemon::UndirectedTagIndicator<Digraph>,
 				       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);
 		      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))) {
 		          out.set(it->first, true);
 		          tree_value += it->second;
+		        }
 		        else {
 		          out.set(it->first, false);
+		        }
+		      }
 		      return tree_value;
+		    }
 		    // Kruskal for undirected graphs.
 		    template <typename Graph, typename In, typename Out>
 		    typename enable_if<lemon::UndirectedTagIndicator<Graph>,
 				       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);
 		      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))) {
 		          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 MapArc;
 		        typedef typename In::Value Value;
 		        typedef typename ItemSetTraits<Graph, MapArc>::ItemIt MapArcIt;
 		        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]));
+		        }
 		        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 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
 		  /// \ref concepts::Graph "undirected".
 		  /// 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 costs. It can be one
 		  /// of the following choices.
 		  /// - An STL compatible 'Forward Container' with
 		  /// <tt>std::pair<GR::Edge,X></tt> or
 		  /// <tt>std::pair<GR::Arc,X></tt> as its <tt>value_type</tt>, where
 		  /// \c X is the type of the costs. The pairs indicates the arcs
 		  /// along with the assigned cost. <em>They must be in a
 		  /// cost-ascending order.</em>
 		  /// - Any readable Arc map. The values of the map indicate the arc costs.
 		  ///
 		  /// \retval out Here we also have a choise.
 		  /// - It can be a writable \c bool arc map.  After running the
 		  /// algorithm this will contain the found minimum cost spanning
 		  /// tree: the value of an arc will be set to \c true if it belongs
 		  /// to the tree, otherwise it will be set to \c false. The value of
 		  /// each arc will be set exactly once.
 		  /// - It can also be an iteraror of an STL Container with
 		  /// <tt>GR::Edge</tt> or <tt>GR::Arc</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 arcs, then we can
 		  /// put its arcs into an STL vector \c tree with a code like this.
 		  ///\code
 		  /// std::vector<Arc> 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<Arc> tree;
 		  /// kruskal(g,cost,std::back_inserter(tree));
 		  ///\endcode
 		  ///
 		  /// \return The total cost of the found tree.
 		  ///
 		  /// \warning If kruskal runs on an be consistent of using the same
 		  /// Arc type for input and output.
 		  ///
 		#ifdef DOXYGEN
 		  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
+		  {
 		    return _kruskal_bits::KruskalInputSelector<Graph, In, Out>::
 		      kruskal(graph, in, out);
+		  }
 		  template <class Graph, class In, class Out>
 		  inline typename _kruskal_bits::KruskalValueSelector<In>::Value
 		  kruskal(const Graph& graph, const In& in, const Out& out)
+		  {
 		    return _kruskal_bits::KruskalInputSelector<Graph, In, const Out>::
 		      kruskal(graph, in, out);
+		  }
 		} //namespace lemon
 		#endif //LEMON_KRUSKAL_H

lemon/unionfind.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
 		 * Copyright (C) 2003-2008
 		 * 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_UNION_FIND_H
 		#define LEMON_UNION_FIND_H
 		//!\ingroup auxdat
 		//!\file
 		//!\brief Union-Find data structures.
 		//!
 		#include <vector>
 		#include <list>
 		#include <utility>
 		#include <algorithm>
 		#include <functional>
 		#include <lemon/bits/invalid.h>
 		namespace lemon {
 		  /// \ingroup auxdat
 		  ///
 		  /// \brief A \e Union-Find data structure implementation
 		  ///
 		  /// The class implements the \e Union-Find data structure.
 		  /// The union operation uses rank heuristic, while
 		  /// the find operation uses path compression.
 		  /// This is a very simple but efficient implementation, providing
 		  /// only four methods: join (union), find, insert and size.
 		  /// For more features see the \ref UnionFindEnum class.
 		  ///
 		  /// It is primarily used in Kruskal algorithm for finding minimal
 		  /// cost spanning tree in a graph.
 		  /// \sa kruskal()
 		  ///
 		  /// \pre You need to add all the elements by the \ref insert()
 		  /// method.
 		  template <typename _ItemIntMap>
 		  class UnionFind {
 		  public:
 		    typedef _ItemIntMap ItemIntMap;
 		    typedef typename ItemIntMap::Key Item;
 		  private:
 		    // If the items vector stores negative value for an item then
 		    // that item is root item and it has -items[it] component size.
 		    // Else the items[it] contains the index of the parent.
 		    std::vector<int> items;
 		    ItemIntMap& index;
 		    bool rep(int idx) const {
 		      return items[idx] < 0;
+		    }
 		    int repIndex(int idx) const {
 		      int k = idx;
 		      while (!rep(k)) {
 		        k = items[k] ;
+		      }
 		      while (idx != k) {
 		        int next = items[idx];
 		        const_cast<int&>(items[idx]) = k;
 		        idx = next;
+		      }
 		      return k;
+		    }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Constructor of the UnionFind class. You should give an item to
 		    /// integer map which will be used from the data structure. If you
 		    /// modify directly this map that may cause segmentation fault,
 		    /// invalid data structure, or infinite loop when you use again
 		    /// the union-find.
 		    UnionFind(ItemIntMap& m) : index(m) {}
 		    /// \brief Returns the index of the element's component.
 		    ///
 		    /// The method returns the index of the element's component.
 		    /// This is an integer between zero and the number of inserted elements.
 		    ///
 		    int find(const Item& a) {
 		      return repIndex(index[a]);
+		    }
 		    /// \brief Clears the union-find data structure
 		    ///
 		    /// Erase each item from the data structure.
 		    void clear() {
 		      items.clear();
+		    }
 		    /// \brief Inserts a new element into the structure.
 		    ///
 		    /// This method inserts a new element into the data structure.
 		    ///
 		    /// The method returns the index of the new component.
 		    int insert(const Item& a) {
 		      int n = items.size();
 		      items.push_back(-1);
 		      index.set(a,n);
 		      return n;
+		    }
 		    /// \brief Joining the components of element \e a and element \e b.
 		    ///
 		    /// This is the \e union operation of the Union-Find structure.
 		    /// Joins the component of element \e a and component of
 		    /// element \e b. If \e a and \e b are in the same component then
 		    /// it returns false otherwise it returns true.
 		    bool join(const Item& a, const Item& b) {
 		      int ka = repIndex(index[a]);
 		      int kb = repIndex(index[b]);
 		      if ( ka == kb )
 			return false;
 		      if (items[ka] < items[kb]) {
 			items[ka] += items[kb];
 			items[kb] = ka;
 		      } else {
 			items[kb] += items[ka];
 			items[ka] = kb;
+		      }
 		      return true;
+		    }
 		    /// \brief Returns the size of the component of element \e a.
 		    ///
 		    /// Returns the size of the component of element \e a.
 		    int size(const Item& a) {
 		      int k = repIndex(index[a]);
 		      return - items[k];
+		    }
 		  };
 		  /// \ingroup auxdat
 		  ///
 		  /// \brief A \e Union-Find data structure implementation which
 		  /// is able to enumerate the components.
 		  ///
 		  /// The class implements a \e Union-Find data structure
 		  /// which is able to enumerate the components and the items in
 		  /// a component. If you don't need this feature then perhaps it's
 		  /// better to use the \ref UnionFind class which is more efficient.
 		  ///
 		  /// The union operation uses rank heuristic, while
 		  /// the find operation uses path compression.
 		  ///
 		  /// \pre You need to add all the elements by the \ref insert()
 		  /// method.
 		  ///
 		  template <typename _ItemIntMap>
 		  class UnionFindEnum {
 		  public:
 		    typedef _ItemIntMap ItemIntMap;
 		    typedef typename ItemIntMap::Key Item;
 		  private:
 		    ItemIntMap& index;
 		    // If the parent stores negative value for an item then that item
 		    // is root item and it has ~(items[it].parent) component id.  Else
 		    // the items[it].parent contains the index of the parent.
 		    //
 		    // The \c next and \c prev provides the double-linked
 		    // cyclic list of one component's items.
 		    struct ItemT {
 		      int parent;
 		      Item item;
 		      int next, prev;
 		    };
 		    std::vector<ItemT> items;
 		    int firstFreeItem;
 		    struct ClassT {
 		      int size;
 		      int firstItem;
 		      int next, prev;
 		    };
 		    std::vector<ClassT> classes;
 		    int firstClass, firstFreeClass;
 		    int newClass() {
 		      if (firstFreeClass == -1) {
 			int cdx = classes.size();
 			classes.push_back(ClassT());
 			return cdx;
 		      } else {
 			int cdx = firstFreeClass;
 			firstFreeClass = classes[firstFreeClass].next;
 			return cdx;
+		      }
+		    }
 		    int newItem() {
 		      if (firstFreeItem == -1) {
 			int idx = items.size();
 			items.push_back(ItemT());
 			return idx;
 		      } else {
 			int idx = firstFreeItem;
 			firstFreeItem = items[firstFreeItem].next;
 			return idx;
+		      }
+		    }
 		    bool rep(int idx) const {
 		      return items[idx].parent < 0;
+		    }
 		    int repIndex(int idx) const {
 		      int k = idx;
 		      while (!rep(k)) {
 		        k = items[k].parent;
+		      }
 		      while (idx != k) {
 		        int next = items[idx].parent;
 		        const_cast<int&>(items[idx].parent) = k;
 		        idx = next;
+		      }
 		      return k;
+		    }
 		    int classIndex(int idx) const {
 		      return ~(items[repIndex(idx)].parent);
+		    }
 		    void singletonItem(int idx) {
 		      items[idx].next = idx;
 		      items[idx].prev = idx;
+		    }
 		    void laceItem(int idx, int rdx) {
 		      items[idx].prev = rdx;
 		      items[idx].next = items[rdx].next;
 		      items[items[rdx].next].prev = idx;
 		      items[rdx].next = idx;
+		    }
 		    void unlaceItem(int idx) {
 		      items[items[idx].prev].next = items[idx].next;
 		      items[items[idx].next].prev = items[idx].prev;
 		      items[idx].next = firstFreeItem;
 		      firstFreeItem = idx;
+		    }
 		    void spliceItems(int ak, int bk) {
 		      items[items[ak].prev].next = bk;
 		      items[items[bk].prev].next = ak;
 		      int tmp = items[ak].prev;
 		      items[ak].prev = items[bk].prev;
 		      items[bk].prev = tmp;
+		    }
 		    void laceClass(int cls) {
 		      if (firstClass != -1) {
 		        classes[firstClass].prev = cls;
+		      }
 		      classes[cls].next = firstClass;
 		      classes[cls].prev = -1;
 		      firstClass = cls;
+		    }
 		    void unlaceClass(int cls) {
 		      if (classes[cls].prev != -1) {
 		        classes[classes[cls].prev].next = classes[cls].next;
 		      } else {
 		        firstClass = classes[cls].next;
+		      }
 		      if (classes[cls].next != -1) {
 		        classes[classes[cls].next].prev = classes[cls].prev;
+		      }
 		      classes[cls].next = firstFreeClass;
 		      firstFreeClass = cls;
+		    }
 		  public:
 		    UnionFindEnum(ItemIntMap& _index)
 		      : index(_index), items(), firstFreeItem(-1),
 			firstClass(-1), firstFreeClass(-1) {}
 		    /// \brief Inserts the given element into a new component.
 		    ///
 		    /// This method creates a new component consisting only of the
 		    /// given element.
 		    ///
 		    int insert(const Item& item) {
 		      int idx = newItem();
 		      index.set(item, idx);
 		      singletonItem(idx);
 		      items[idx].item = item;
 		      int cdx = newClass();
 		      items[idx].parent = ~cdx;
 		      laceClass(cdx);
 		      classes[cdx].size = 1;
 		      classes[cdx].firstItem = idx;
 		      firstClass = cdx;
 		      return cdx;
+		    }
 		    /// \brief Inserts the given element into the component of the others.
 		    ///
 		    /// This methods inserts the element \e a into the component of the
 		    /// element \e comp.
 		    void insert(const Item& item, int cls) {
 		      int rdx = classes[cls].firstItem;
 		      int idx = newItem();
 		      index.set(item, idx);
 		      laceItem(idx, rdx);
 		      items[idx].item = item;
 		      items[idx].parent = rdx;
 		      ++classes[~(items[rdx].parent)].size;
+		    }
 		    /// \brief Clears the union-find data structure
 		    ///
 		    /// Erase each item from the data structure.
 		    void clear() {
 		      items.clear();
 		      firstClass = -1;
 		      firstFreeItem = -1;
+		    }
 		    /// \brief Finds the component of the given element.
 		    ///
 		    /// The method returns the component id of the given element.
 		    int find(const Item &item) const {
 		      return ~(items[repIndex(index[item])].parent);
+		    }
 		    /// \brief Joining the component of element \e a and element \e b.
 		    ///
 		    /// This is the \e union operation of the Union-Find structure.
 		    /// Joins the component of element \e a and component of
 		    /// element \e b. If \e a and \e b are in the same component then
 		    /// returns -1 else returns the remaining class.
 		    int join(const Item& a, const Item& b) {
 		      int ak = repIndex(index[a]);
 		      int bk = repIndex(index[b]);
 		      if (ak == bk) {
 			return -1;
+		      }
 		      int acx = ~(items[ak].parent);
 		      int bcx = ~(items[bk].parent);
 		      int rcx;
 		      if (classes[acx].size > classes[bcx].size) {
 			classes[acx].size += classes[bcx].size;
 			items[bk].parent = ak;
 		        unlaceClass(bcx);
 			rcx = acx;
 		      } else {
 			classes[bcx].size += classes[acx].size;
 			items[ak].parent = bk;
 		        unlaceClass(acx);
 			rcx = bcx;
+		      }
 		      spliceItems(ak, bk);
 		      return rcx;
+		    }
 		    /// \brief Returns the size of the class.
 		    ///
 		    /// Returns the size of the class.
 		    int size(int cls) const {
 		      return classes[cls].size;
+		    }
 		    /// \brief Splits up the component.
 		    ///
 		    /// Splitting the component into singleton components (component
 		    /// of size one).
 		    void split(int cls) {
 		      int fdx = classes[cls].firstItem;
 		      int idx = items[fdx].next;
 		      while (idx != fdx) {
 		        int next = items[idx].next;
 			singletonItem(idx);
 			int cdx = newClass();
 		        items[idx].parent = ~cdx;
 			laceClass(cdx);
 			classes[cdx].size = 1;
 			classes[cdx].firstItem = idx;
 		        idx = next;
+		      }
 		      items[idx].prev = idx;
 		      items[idx].next = idx;
 		      classes[~(items[idx].parent)].size = 1;
+		    }
 		    /// \brief Removes the given element from the structure.
 		    ///
 		    /// Removes the element from its component and if the component becomes
 		    /// empty then removes that component from the component list.
 		    ///
 		    /// \warning It is an error to remove an element which is not in
 		    /// the structure.
 		    /// \warning This running time of this operation is proportional to the
 		    /// number of the items in this class.
 		    void erase(const Item& item) {
 		      int idx = index[item];
 		      int fdx = items[idx].next;
 		      int cdx = classIndex(idx);
 		      if (idx == fdx) {
 			unlaceClass(cdx);
 			items[idx].next = firstFreeItem;
 			firstFreeItem = idx;
 			return;
 		      } else {
 			classes[cdx].firstItem = fdx;
 			--classes[cdx].size;
 			items[fdx].parent = ~cdx;
 			unlaceItem(idx);
 			idx = items[fdx].next;
 			while (idx != fdx) {
 			  items[idx].parent = fdx;
 			  idx = items[idx].next;
+			}
+		      }
+		    }
 		    /// \brief Gives back a representant item of the component.
 		    ///
 		    /// Gives back a representant item of the component.
 		    Item item(int cls) const {
 		      return items[classes[cls].firstItem].item;
+		    }
 		    /// \brief Removes the component of the given element from the structure.
 		    ///
 		    /// Removes the component of the given element from the structure.
 		    ///
 		    /// \warning It is an error to give an element which is not in the
 		    /// structure.
 		    void eraseClass(int cls) {
 		      int fdx = classes[cls].firstItem;
 		      unlaceClass(cls);
 		      items[items[fdx].prev].next = firstFreeItem;
 		      firstFreeItem = fdx;
+		    }
 		    /// \brief Lemon style iterator for the representant items.
 		    ///
 		    /// ClassIt is a lemon style iterator for the components. It iterates
 		    /// on the ids of the classes.
 		    class ClassIt {
 		    public:
 		      /// \brief Constructor of the iterator
 		      ///
 		      /// Constructor of the iterator
 		      ClassIt(const UnionFindEnum& ufe) : unionFind(&ufe) {
 		        cdx = unionFind->firstClass;
+		      }
 		      /// \brief Constructor to get invalid iterator
 		      ///
 		      /// Constructor to get invalid iterator
 		      ClassIt(Invalid) : unionFind(0), cdx(-1) {}
 		      /// \brief Increment operator
 		      ///
 		      /// It steps to the next representant item.
 		      ClassIt& operator++() {
 		        cdx = unionFind->classes[cdx].next;
 		        return *this;
+		      }
 		      /// \brief Conversion operator
 		      ///
 		      /// It converts the iterator to the current representant item.
 		      operator int() const {
 		        return cdx;
+		      }
 		      /// \brief Equality operator
 		      ///
 		      /// Equality operator
 		      bool operator==(const ClassIt& i) {
 		        return i.cdx == cdx;
+		      }
 		      /// \brief Inequality operator
 		      ///
 		      /// Inequality operator
 		      bool operator!=(const ClassIt& i) {
 		        return i.cdx != cdx;
+		      }
 		    private:
 		      const UnionFindEnum* unionFind;
 		      int cdx;
 		    };
 		    /// \brief Lemon style iterator for the items of a component.
 		    ///
 		    /// ClassIt is a lemon style iterator for the components. It iterates
 		    /// on the items of a class. By example if you want to iterate on
 		    /// each items of each classes then you may write the next code.
 		    ///\code
 		    /// for (ClassIt cit(ufe); cit != INVALID; ++cit) {
 		    ///   std::cout << "Class: ";
 		    ///   for (ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
 		    ///     std::cout << toString(iit) << ' ' << std::endl;
 		    ///   }
 		    ///   std::cout << std::endl;
 		    /// }
 		    ///\endcode
 		    class ItemIt {
 		    public:
 		      /// \brief Constructor of the iterator
 		      ///
 		      /// Constructor of the iterator. The iterator iterates
 		      /// on the class of the \c item.
 		      ItemIt(const UnionFindEnum& ufe, int cls) : unionFind(&ufe) {
 		        fdx = idx = unionFind->classes[cls].firstItem;
+		      }
 		      /// \brief Constructor to get invalid iterator
 		      ///
 		      /// Constructor to get invalid iterator
 		      ItemIt(Invalid) : unionFind(0), idx(-1) {}
 		      /// \brief Increment operator
 		      ///
 		      /// It steps to the next item in the class.
 		      ItemIt& operator++() {
 		        idx = unionFind->items[idx].next;
 		        if (idx == fdx) idx = -1;
 		        return *this;
+		      }
 		      /// \brief Conversion operator
 		      ///
 		      /// It converts the iterator to the current item.
 		      operator const Item&() const {
 		        return unionFind->items[idx].item;
+		      }
 		      /// \brief Equality operator
 		      ///
 		      /// Equality operator
 		      bool operator==(const ItemIt& i) {
 		        return i.idx == idx;
+		      }
 		      /// \brief Inequality operator
 		      ///
 		      /// Inequality operator
 		      bool operator!=(const ItemIt& i) {
 		        return i.idx != idx;
+		      }
 		    private:
 		      const UnionFindEnum* unionFind;
 		      int idx, fdx;
 		    };
 		  };
 		  /// \ingroup auxdat
 		  ///
 		  /// \brief A \e Extend-Find data structure implementation which
 		  /// is able to enumerate the components.
 		  ///
 		  /// The class implements an \e Extend-Find data structure which is
 		  /// able to enumerate the components and the items in a
 		  /// component. The data structure is a simplification of the
 		  /// Union-Find structure, and it does not allow to merge two components.
 		  ///
 		  /// \pre You need to add all the elements by the \ref insert()
 		  /// method.
 		  template <typename _ItemIntMap>
 		  class ExtendFindEnum {
 		  public:
 		    typedef _ItemIntMap ItemIntMap;
 		    typedef typename ItemIntMap::Key Item;
 		  private:
 		    ItemIntMap& index;
 		    struct ItemT {
 		      int cls;
 		      Item item;
 		      int next, prev;
 		    };
 		    std::vector<ItemT> items;
 		    int firstFreeItem;
 		    struct ClassT {
 		      int firstItem;
 		      int next, prev;
 		    };
 		    std::vector<ClassT> classes;
 		    int firstClass, firstFreeClass;
 		    int newClass() {
 		      if (firstFreeClass != -1) {
 			int cdx = firstFreeClass;
 			firstFreeClass = classes[cdx].next;
 			return cdx;
 		      } else {
 			classes.push_back(ClassT());
 			return classes.size() - 1;
+		      }
+		    }
 		    int newItem() {
 		      if (firstFreeItem != -1) {
 			int idx = firstFreeItem;
 			firstFreeItem = items[idx].next;
 			return idx;
 		      } else {
 			items.push_back(ItemT());
 			return items.size() - 1;
+		      }
+		    }
 		  public:
 		    /// \brief Constructor
 		    ExtendFindEnum(ItemIntMap& _index)
 		      : index(_index), items(), firstFreeItem(-1),
 			classes(), firstClass(-1), firstFreeClass(-1) {}
 		    /// \brief Inserts the given element into a new component.
 		    ///
 		    /// This method creates a new component consisting only of the
 		    /// given element.
 		    int insert(const Item& item) {
 		      int cdx = newClass();
 		      classes[cdx].prev = -1;
 		      classes[cdx].next = firstClass;
 		      if (firstClass != -1) {
 			classes[firstClass].prev = cdx;
+		      }
 		      firstClass = cdx;
 		      int idx = newItem();
 		      items[idx].item = item;
 		      items[idx].cls = cdx;
 		      items[idx].prev = idx;
 		      items[idx].next = idx;
 		      classes[cdx].firstItem = idx;
 		      index.set(item, idx);
 		      return cdx;
+		    }
 		    /// \brief Inserts the given element into the given component.
 		    ///
 		    /// This methods inserts the element \e item a into the \e cls class.
 		    void insert(const Item& item, int cls) {
 		      int idx = newItem();
 		      int rdx = classes[cls].firstItem;
 		      items[idx].item = item;
 		      items[idx].cls = cls;
 		      items[idx].prev = rdx;
 		      items[idx].next = items[rdx].next;
 		      items[items[rdx].next].prev = idx;
 		      items[rdx].next = idx;
 		      index.set(item, idx);
+		    }
 		    /// \brief Clears the union-find data structure
 		    ///
 		    /// Erase each item from the data structure.
 		    void clear() {
 		      items.clear();
 		      classes.clear;
 		      firstClass = firstFreeClass = firstFreeItem = -1;
+		    }
 		    /// \brief Gives back the class of the \e item.
 		    ///
 		    /// Gives back the class of the \e item.
 		    int find(const Item &item) const {
 		      return items[index[item]].cls;
+		    }
 		    /// \brief Gives back a representant item of the component.
 		    ///
 		    /// Gives back a representant item of the component.
 		    Item item(int cls) const {
 		      return items[classes[cls].firstItem].item;
+		    }
 		    /// \brief Removes the given element from the structure.
 		    ///
 		    /// Removes the element from its component and if the component becomes
 		    /// empty then removes that component from the component list.
 		    ///
 		    /// \warning It is an error to remove an element which is not in
 		    /// the structure.
 		    void erase(const Item &item) {
 		      int idx = index[item];
 		      int cdx = items[idx].cls;
 		      if (idx == items[idx].next) {
 			if (classes[cdx].prev != -1) {
 			  classes[classes[cdx].prev].next = classes[cdx].next;
 			} else {
 			  firstClass = classes[cdx].next;
+			}
 			if (classes[cdx].next != -1) {
 			  classes[classes[cdx].next].prev = classes[cdx].prev;
+			}
 			classes[cdx].next = firstFreeClass;
 			firstFreeClass = cdx;
 		      } else {
 			classes[cdx].firstItem = items[idx].next;
 			items[items[idx].next].prev = items[idx].prev;
 			items[items[idx].prev].next = items[idx].next;
+		      }
 		      items[idx].next = firstFreeItem;
 		      firstFreeItem = idx;
+		    }
 		    /// \brief Removes the component of the given element from the structure.
 		    ///
 		    /// Removes the component of the given element from the structure.
 		    ///
 		    /// \warning It is an error to give an element which is not in the
 		    /// structure.
 		    void eraseClass(int cdx) {
 		      int idx = classes[cdx].firstItem;
 		      items[items[idx].prev].next = firstFreeItem;
 		      firstFreeItem = idx;
 		      if (classes[cdx].prev != -1) {
 			classes[classes[cdx].prev].next = classes[cdx].next;
 		      } else {
 			firstClass = classes[cdx].next;
+		      }
 		      if (classes[cdx].next != -1) {
 			classes[classes[cdx].next].prev = classes[cdx].prev;
+		      }
 		      classes[cdx].next = firstFreeClass;
 		      firstFreeClass = cdx;
+		    }
 		    /// \brief Lemon style iterator for the classes.
 		    ///
 		    /// ClassIt is a lemon style iterator for the components. It iterates
 		    /// on the ids of classes.
 		    class ClassIt {
 		    public:
 		      /// \brief Constructor of the iterator
 		      ///
 		      /// Constructor of the iterator
 		      ClassIt(const ExtendFindEnum& ufe) : extendFind(&ufe) {
 		        cdx = extendFind->firstClass;
+		      }
 		      /// \brief Constructor to get invalid iterator
 		      ///
 		      /// Constructor to get invalid iterator
 		      ClassIt(Invalid) : extendFind(0), cdx(-1) {}
 		      /// \brief Increment operator
 		      ///
 		      /// It steps to the next representant item.
 		      ClassIt& operator++() {
 		        cdx = extendFind->classes[cdx].next;
 		        return *this;
+		      }
 		      /// \brief Conversion operator
 		      ///
 		      /// It converts the iterator to the current class id.
 		      operator int() const {
 		        return cdx;
+		      }
 		      /// \brief Equality operator
 		      ///
 		      /// Equality operator
 		      bool operator==(const ClassIt& i) {
 		        return i.cdx == cdx;
+		      }
 		      /// \brief Inequality operator
 		      ///
 		      /// Inequality operator
 		      bool operator!=(const ClassIt& i) {
 		        return i.cdx != cdx;
+		      }
 		    private:
 		      const ExtendFindEnum* extendFind;
 		      int cdx;
 		    };
 		    /// \brief Lemon style iterator for the items of a component.
 		    ///
 		    /// ClassIt is a lemon style iterator for the components. It iterates
 		    /// on the items of a class. By example if you want to iterate on
 		    /// each items of each classes then you may write the next code.
 		    ///\code
 		    /// for (ClassIt cit(ufe); cit != INVALID; ++cit) {
 		    ///   std::cout << "Class: ";
 		    ///   for (ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
 		    ///     std::cout << toString(iit) << ' ' << std::endl;
 		    ///   }
 		    ///   std::cout << std::endl;
 		    /// }
 		    ///\endcode
 		    class ItemIt {
 		    public:
 		      /// \brief Constructor of the iterator
 		      ///
 		      /// Constructor of the iterator. The iterator iterates
 		      /// on the class of the \c item.
 		      ItemIt(const ExtendFindEnum& ufe, int cls) : extendFind(&ufe) {
 		        fdx = idx = extendFind->classes[cls].firstItem;
+		      }
 		      /// \brief Constructor to get invalid iterator
 		      ///
 		      /// Constructor to get invalid iterator
 		      ItemIt(Invalid) : extendFind(0), idx(-1) {}
 		      /// \brief Increment operator
 		      ///
 		      /// It steps to the next item in the class.
 		      ItemIt& operator++() {
 		        idx = extendFind->items[idx].next;
 			if (fdx == idx) idx = -1;
 		        return *this;
+		      }
 		      /// \brief Conversion operator
 		      ///
 		      /// It converts the iterator to the current item.
 		      operator const Item&() const {
 		        return extendFind->items[idx].item;
+		      }
 		      /// \brief Equality operator
 		      ///
 		      /// Equality operator
 		      bool operator==(const ItemIt& i) {
 		        return i.idx == idx;
+		      }
 		      /// \brief Inequality operator
 		      ///
 		      /// Inequality operator
 		      bool operator!=(const ItemIt& i) {
 		        return i.idx != idx;
+		      }
 		    private:
 		      const ExtendFindEnum* extendFind;
 		      int idx, fdx;
 		    };
 		  };
 		  /// \ingroup auxdat
 		  ///
 		  /// \brief A \e Union-Find data structure implementation which
 		  /// is able to store a priority for each item and retrieve the minimum of
 		  /// each class.
 		  ///
 		  /// A \e Union-Find data structure implementation which is able to
 		  /// store a priority for each item and retrieve the minimum of each
 		  /// class. In addition, it supports the joining and splitting the
 		  /// components. If you don't need this feature then you makes
 		  /// better to use the \ref UnionFind class which is more efficient.
 		  ///
 		  /// The union-find data strcuture based on a (2, 16)-tree with a
 		  /// tournament minimum selection on the internal nodes. The insert
 		  /// operation takes O(1), the find, set, decrease and increase takes
 		  /// O(log(n)), where n is the number of nodes in the current
 		  /// component.  The complexity of join and split is O(log(n)*k),
 		  /// where n is the sum of the number of the nodes and k is the
 		  /// number of joined components or the number of the components
 		  /// after the split.
 		  ///
 		  /// \pre You need to add all the elements by the \ref insert()
 		  /// method.
 		  ///
 		  template <typename _Value, typename _ItemIntMap,
 		            typename _Comp = std::less<_Value> >
 		  class HeapUnionFind {
 		  public:
 		    typedef _Value Value;
 		    typedef typename _ItemIntMap::Key Item;
 		    typedef _ItemIntMap ItemIntMap;
 		    typedef _Comp Comp;
 		  private:
 		    static const int cmax = 16;
 		    ItemIntMap& index;
 		    struct ClassNode {
 		      int parent;
 		      int depth;
 		      int left, right;
 		      int next, prev;
 		    };
 		    int first_class;
 		    int first_free_class;
 		    std::vector<ClassNode> classes;
 		    int newClass() {
 		      if (first_free_class < 0) {
 		        int id = classes.size();
 		        classes.push_back(ClassNode());
 		        return id;
 		      } else {
 		        int id = first_free_class;
 		        first_free_class = classes[id].next;
 		        return id;
+		      }
+		    }
 		    void deleteClass(int id) {
 		      classes[id].next = first_free_class;
 		      first_free_class = id;
+		    }
 		    struct ItemNode {
 		      int parent;
 		      Item item;
 		      Value prio;
 		      int next, prev;
 		      int left, right;
 		      int size;
 		    };
 		    int first_free_node;
 		    std::vector<ItemNode> nodes;
 		    int newNode() {
 		      if (first_free_node < 0) {
 		        int id = nodes.size();
 		        nodes.push_back(ItemNode());
 		        return id;
 		      } else {
 		        int id = first_free_node;
 		        first_free_node = nodes[id].next;
 		        return id;
+		      }
+		    }
 		    void deleteNode(int id) {
 		      nodes[id].next = first_free_node;
 		      first_free_node = id;
+		    }
 		    Comp comp;
 		    int findClass(int id) const {
 		      int kd = id;
 		      while (kd >= 0) {
 		        kd = nodes[kd].parent;
+		      }
 		      return ~kd;
+		    }
 		    int leftNode(int id) const {
 		      int kd = ~(classes[id].parent);
 		      for (int i = 0; i < classes[id].depth; ++i) {
 		        kd = nodes[kd].left;
+		      }
 		      return kd;
+		    }
 		    int nextNode(int id) const {
 		      int depth = 0;
 		      while (id >= 0 && nodes[id].next == -1) {
 		        id = nodes[id].parent;
 		        ++depth;
+		      }
 		      if (id < 0) {
 		        return -1;
+		      }
 		      id = nodes[id].next;
 		      while (depth--) {
 		        id = nodes[id].left;
+		      }
 		      return id;
+		    }
 		    void setPrio(int id) {
 		      int jd = nodes[id].left;
 		      nodes[id].prio = nodes[jd].prio;
 		      nodes[id].item = nodes[jd].item;
 		      jd = nodes[jd].next;
 		      while (jd != -1) {
 		        if (comp(nodes[jd].prio, nodes[id].prio)) {
 		          nodes[id].prio = nodes[jd].prio;
 		          nodes[id].item = nodes[jd].item;
+		        }
 		        jd = nodes[jd].next;
+		      }
+		    }
 		    void push(int id, int jd) {
 		      nodes[id].size = 1;
 		      nodes[id].left = nodes[id].right = jd;
 		      nodes[jd].next = nodes[jd].prev = -1;
 		      nodes[jd].parent = id;
+		    }
 		    void pushAfter(int id, int jd) {
 		      int kd = nodes[id].parent;
 		      if (nodes[id].next != -1) {
 		        nodes[nodes[id].next].prev = jd;
 		        if (kd >= 0) {
 		          nodes[kd].size += 1;
+		        }
 		      } else {
 		        if (kd >= 0) {
 		          nodes[kd].right = jd;
 		          nodes[kd].size += 1;
+		        }
+		      }
 		      nodes[jd].next = nodes[id].next;
 		      nodes[jd].prev = id;
 		      nodes[id].next = jd;
 		      nodes[jd].parent = kd;
+		    }
 		    void pushRight(int id, int jd) {
 		      nodes[id].size += 1;
 		      nodes[jd].prev = nodes[id].right;
 		      nodes[jd].next = -1;
 		      nodes[nodes[id].right].next = jd;
 		      nodes[id].right = jd;
 		      nodes[jd].parent = id;
+		    }
 		    void popRight(int id) {
 		      nodes[id].size -= 1;
 		      int jd = nodes[id].right;
 		      nodes[nodes[jd].prev].next = -1;
 		      nodes[id].right = nodes[jd].prev;
+		    }
 		    void splice(int id, int jd) {
 		      nodes[id].size += nodes[jd].size;
 		      nodes[nodes[id].right].next = nodes[jd].left;
 		      nodes[nodes[jd].left].prev = nodes[id].right;
 		      int kd = nodes[jd].left;
 		      while (kd != -1) {
 		        nodes[kd].parent = id;
 		        kd = nodes[kd].next;
+		      }
 		      nodes[id].right = nodes[jd].right;
+		    }
 		    void split(int id, int jd) {
 		      int kd = nodes[id].parent;
 		      nodes[kd].right = nodes[id].prev;
 		      nodes[nodes[id].prev].next = -1;
 		      nodes[jd].left = id;
 		      nodes[id].prev = -1;
 		      int num = 0;
 		      while (id != -1) {
 		        nodes[id].parent = jd;
 		        nodes[jd].right = id;
 		        id = nodes[id].next;
 		        ++num;
+		      }
 		      nodes[kd].size -= num;
 		      nodes[jd].size = num;
+		    }
 		    void pushLeft(int id, int jd) {
 		      nodes[id].size += 1;
 		      nodes[jd].next = nodes[id].left;
 		      nodes[jd].prev = -1;
 		      nodes[nodes[id].left].prev = jd;
 		      nodes[id].left = jd;
 		      nodes[jd].parent = id;
+		    }
 		    void popLeft(int id) {
 		      nodes[id].size -= 1;
 		      int jd = nodes[id].left;
 		      nodes[nodes[jd].next].prev = -1;
 		      nodes[id].left = nodes[jd].next;
+		    }
 		    void repairLeft(int id) {
 		      int jd = ~(classes[id].parent);
 		      while (nodes[jd].left != -1) {
 			int kd = nodes[jd].left;
 			if (nodes[jd].size == 1) {
 			  if (nodes[jd].parent < 0) {
 			    classes[id].parent = ~kd;
 			    classes[id].depth -= 1;
 			    nodes[kd].parent = ~id;
 			    deleteNode(jd);
 			    jd = kd;
 			  } else {
 			    int pd = nodes[jd].parent;
 			    if (nodes[nodes[jd].next].size < cmax) {
 			      pushLeft(nodes[jd].next, nodes[jd].left);
 			      if (less(nodes[jd].left, nodes[jd].next)) {
 				nodes[nodes[jd].next].prio = nodes[nodes[jd].left].prio;
 				nodes[nodes[jd].next].item = nodes[nodes[jd].left].item;
+			      }
 			      popLeft(pd);
 			      deleteNode(jd);
 			      jd = pd;
 			    } else {
 			      int ld = nodes[nodes[jd].next].left;
 			      popLeft(nodes[jd].next);
 			      pushRight(jd, ld);
 			      if (less(ld, nodes[jd].left)) {
 				nodes[jd].item = nodes[ld].item;
 				nodes[jd].prio = nodes[jd].prio;
+			      }
 			      if (nodes[nodes[jd].next].item == nodes[ld].item) {
 				setPrio(nodes[jd].next);
+			      }
 			      jd = nodes[jd].left;
+			    }
+			  }
 			} else {
 			  jd = nodes[jd].left;
+			}
+		      }
+		    }
 		    void repairRight(int id) {
 		      int jd = ~(classes[id].parent);
 		      while (nodes[jd].right != -1) {
 			int kd = nodes[jd].right;
 			if (nodes[jd].size == 1) {
 			  if (nodes[jd].parent < 0) {
 			    classes[id].parent = ~kd;
 			    classes[id].depth -= 1;
 			    nodes[kd].parent = ~id;
 			    deleteNode(jd);
 			    jd = kd;
 			  } else {
 			    int pd = nodes[jd].parent;
 			    if (nodes[nodes[jd].prev].size < cmax) {
 			      pushRight(nodes[jd].prev, nodes[jd].right);
 			      if (less(nodes[jd].right, nodes[jd].prev)) {
 				nodes[nodes[jd].prev].prio = nodes[nodes[jd].right].prio;
 				nodes[nodes[jd].prev].item = nodes[nodes[jd].right].item;
+			      }
 			      popRight(pd);
 			      deleteNode(jd);
 			      jd = pd;
 			    } else {
 			      int ld = nodes[nodes[jd].prev].right;
 			      popRight(nodes[jd].prev);
 			      pushLeft(jd, ld);
 			      if (less(ld, nodes[jd].right)) {
 				nodes[jd].item = nodes[ld].item;
 				nodes[jd].prio = nodes[jd].prio;
+			      }
 			      if (nodes[nodes[jd].prev].item == nodes[ld].item) {
 				setPrio(nodes[jd].prev);
+			      }
 			      jd = nodes[jd].right;
+			    }
+			  }
 			} else {
 			  jd = nodes[jd].right;
+			}
+		      }
+		    }
 		    bool less(int id, int jd) const {
 		      return comp(nodes[id].prio, nodes[jd].prio);
+		    }
 		    bool equal(int id, int jd) const {
 		      return !less(id, jd) && !less(jd, id);
+		    }
 		  public:
 		    /// \brief Returns true when the given class is alive.
 		    ///
 		    /// Returns true when the given class is alive, ie. the class is
 		    /// not nested into other class.
 		    bool alive(int cls) const {
 		      return classes[cls].parent < 0;
+		    }
 		    /// \brief Returns true when the given class is trivial.
 		    ///
 		    /// Returns true when the given class is trivial, ie. the class
 		    /// contains just one item directly.
 		    bool trivial(int cls) const {
 		      return classes[cls].left == -1;
+		    }
 		    /// \brief Constructs the union-find.
 		    ///
 		    /// Constructs the union-find.
 		    /// \brief _index The index map of the union-find. The data
 		    /// structure uses internally for store references.
 		    HeapUnionFind(ItemIntMap& _index)
 		      : index(_index), first_class(-1),
 			first_free_class(-1), first_free_node(-1) {}
 		    /// \brief Insert a new node into a new component.
 		    ///
 		    /// Insert a new node into a new component.
 		    /// \param item The item of the new node.
 		    /// \param prio The priority of the new node.
 		    /// \return The class id of the one-item-heap.
 		    int insert(const Item& item, const Value& prio) {
 		      int id = newNode();
 		      nodes[id].item = item;
 		      nodes[id].prio = prio;
 		      nodes[id].size = 0;
 		      nodes[id].prev = -1;
 		      nodes[id].next = -1;
 		      nodes[id].left = -1;
 		      nodes[id].right = -1;
 		      nodes[id].item = item;
 		      index[item] = id;
 		      int class_id = newClass();
 		      classes[class_id].parent = ~id;
 		      classes[class_id].depth = 0;
 		      classes[class_id].left = -1;
 		      classes[class_id].right = -1;
 		      if (first_class != -1) {
 		        classes[first_class].prev = class_id;
+		      }
 		      classes[class_id].next = first_class;
 		      classes[class_id].prev = -1;
 		      first_class = class_id;
 		      nodes[id].parent = ~class_id;
 		      return class_id;
+		    }
 		    /// \brief The class of the item.
 		    ///
 		    /// \return The alive class id of the item, which is not nested into
 		    /// other classes.
 		    ///
 		    /// The time complexity is O(log(n)).
 		    int find(const Item& item) const {
 		      return findClass(index[item]);
+		    }
 		    /// \brief Joins the classes.
 		    ///
 		    /// The current function joins the given classes. The parameter is
 		    /// an STL range which should be contains valid class ids. The
 		    /// time complexity is O(log(n)*k) where n is the overall number
 		    /// of the joined nodes and k is the number of classes.
 		    /// \return The class of the joined classes.
 		    /// \pre The range should contain at least two class ids.
 		    template <typename Iterator>
 		    int join(Iterator begin, Iterator end) {
 		      std::vector<int> cs;
 		      for (Iterator it = begin; it != end; ++it) {
 		        cs.push_back(*it);
+		      }
 		      int class_id = newClass();
 		      { // creation union-find
 		        if (first_class != -1) {
 		          classes[first_class].prev = class_id;
+		        }
 		        classes[class_id].next = first_class;
 		        classes[class_id].prev = -1;
 		        first_class = class_id;
 		        classes[class_id].depth = classes[cs[0]].depth;
 		        classes[class_id].parent = classes[cs[0]].parent;
 		        nodes[~(classes[class_id].parent)].parent = ~class_id;
 		        int l = cs[0];
 		        classes[class_id].left = l;
 		        classes[class_id].right = l;
 		        if (classes[l].next != -1) {
 		          classes[classes[l].next].prev = classes[l].prev;
+		        }
 		        classes[classes[l].prev].next = classes[l].next;
 		        classes[l].prev = -1;
 		        classes[l].next = -1;
 		        classes[l].depth = leftNode(l);
 		        classes[l].parent = class_id;
+		      }
 		      { // merging of heap
 		        int l = class_id;
 		        for (int ci = 1; ci < int(cs.size()); ++ci) {
 		          int r = cs[ci];
 		          int rln = leftNode(r);
 		          if (classes[l].depth > classes[r].depth) {
 		            int id = ~(classes[l].parent);
 		            for (int i = classes[r].depth + 1; i < classes[l].depth; ++i) {
 		              id = nodes[id].right;
+		            }
 		            while (id >= 0 && nodes[id].size == cmax) {
 		              int new_id = newNode();
 		              int right_id = nodes[id].right;
 		              popRight(id);
 		              if (nodes[id].item == nodes[right_id].item) {
 		                setPrio(id);
+		              }
 		              push(new_id, right_id);
 		              pushRight(new_id, ~(classes[r].parent));
 		              setPrio(new_id);
 		              id = nodes[id].parent;
 		              classes[r].parent = ~new_id;
+		            }
 		            if (id < 0) {
 		              int new_parent = newNode();
 		              nodes[new_parent].next = -1;
 		              nodes[new_parent].prev = -1;
 		              nodes[new_parent].parent = ~l;
 		              push(new_parent, ~(classes[l].parent));
 		              pushRight(new_parent, ~(classes[r].parent));
 		              setPrio(new_parent);
 		              classes[l].parent = ~new_parent;
 		              classes[l].depth += 1;
 		            } else {
 		              pushRight(id, ~(classes[r].parent));
 		              while (id >= 0 && less(~(classes[r].parent), id)) {
 		                nodes[id].prio = nodes[~(classes[r].parent)].prio;
 		                nodes[id].item = nodes[~(classes[r].parent)].item;
 		                id = nodes[id].parent;
+		              }
+		            }
 		          } else if (classes[r].depth > classes[l].depth) {
 		            int id = ~(classes[r].parent);
 		            for (int i = classes[l].depth + 1; i < classes[r].depth; ++i) {
 		              id = nodes[id].left;
+		            }
 		            while (id >= 0 && nodes[id].size == cmax) {
 		              int new_id = newNode();
 		              int left_id = nodes[id].left;
 		              popLeft(id);
 		              if (nodes[id].prio == nodes[left_id].prio) {
 		                setPrio(id);
+		              }
 		              push(new_id, left_id);
 		              pushLeft(new_id, ~(classes[l].parent));
 		              setPrio(new_id);
 		              id = nodes[id].parent;
 		              classes[l].parent = ~new_id;
+		            }
 		            if (id < 0) {
 		              int new_parent = newNode();
 		              nodes[new_parent].next = -1;
 		              nodes[new_parent].prev = -1;
 		              nodes[new_parent].parent = ~l;
 		              push(new_parent, ~(classes[r].parent));
 		              pushLeft(new_parent, ~(classes[l].parent));
 		              setPrio(new_parent);
 		              classes[r].parent = ~new_parent;
 		              classes[r].depth += 1;
 		            } else {
 		              pushLeft(id, ~(classes[l].parent));
 		              while (id >= 0 && less(~(classes[l].parent), id)) {
 		                nodes[id].prio = nodes[~(classes[l].parent)].prio;
 		                nodes[id].item = nodes[~(classes[l].parent)].item;
 		                id = nodes[id].parent;
+		              }
+		            }
 		            nodes[~(classes[r].parent)].parent = ~l;
 		            classes[l].parent = classes[r].parent;
 		            classes[l].depth = classes[r].depth;
 		          } else {
 		            if (classes[l].depth != 0 &&
 		                nodes[~(classes[l].parent)].size +
 		                nodes[~(classes[r].parent)].size <= cmax) {
 		              splice(~(classes[l].parent), ~(classes[r].parent));
 		              deleteNode(~(classes[r].parent));
 		              if (less(~(classes[r].parent), ~(classes[l].parent))) {
 		                nodes[~(classes[l].parent)].prio =
 		                  nodes[~(classes[r].parent)].prio;
 		                nodes[~(classes[l].parent)].item =
 		                  nodes[~(classes[r].parent)].item;
+		              }
 		            } else {
 		              int new_parent = newNode();
 		              nodes[new_parent].next = nodes[new_parent].prev = -1;
 		              push(new_parent, ~(classes[l].parent));
 		              pushRight(new_parent, ~(classes[r].parent));
 		              setPrio(new_parent);
 		              classes[l].parent = ~new_parent;
 		              classes[l].depth += 1;
 		              nodes[new_parent].parent = ~l;
+		            }
+		          }
 		          if (classes[r].next != -1) {
 		            classes[classes[r].next].prev = classes[r].prev;
+		          }
 		          classes[classes[r].prev].next = classes[r].next;
 		          classes[r].prev = classes[l].right;
 		          classes[classes[l].right].next = r;
 		          classes[l].right = r;
 		          classes[r].parent = l;
 		          classes[r].next = -1;
 		          classes[r].depth = rln;
+		        }
+		      }
 		      return class_id;
+		    }
 		    /// \brief Split the class to subclasses.
 		    ///
 		    /// The current function splits the given class. The join, which
 		    /// made the current class, stored a reference to the
 		    /// subclasses. The \c splitClass() member restores the classes
 		    /// and creates the heaps. The parameter is an STL output iterator
 		    /// which will be filled with the subclass ids. The time
 		    /// complexity is O(log(n)*k) where n is the overall number of
 		    /// nodes in the splitted classes and k is the number of the
 		    /// classes.
 		    template <typename Iterator>
 		    void split(int cls, Iterator out) {
 		      std::vector<int> cs;
 		      { // splitting union-find
 		        int id = cls;
 		        int l = classes[id].left;
 		        classes[l].parent = classes[id].parent;
 		        classes[l].depth = classes[id].depth;
 		        nodes[~(classes[l].parent)].parent = ~l;
 		        *out++ = l;
 		        while (l != -1) {
 		          cs.push_back(l);
 		          l = classes[l].next;
+		        }
 		        classes[classes[id].right].next = first_class;
 		        classes[first_class].prev = classes[id].right;
 		        first_class = classes[id].left;
 		        if (classes[id].next != -1) {
 		          classes[classes[id].next].prev = classes[id].prev;
+		        }
 		        classes[classes[id].prev].next = classes[id].next;
 		        deleteClass(id);
+		      }
+		      {
 		        for (int i = 1; i < int(cs.size()); ++i) {
 		          int l = classes[cs[i]].depth;
 		          while (nodes[nodes[l].parent].left == l) {
 		            l = nodes[l].parent;
+		          }
 		          int r = l;
 		          while (nodes[l].parent >= 0) {
 		            l = nodes[l].parent;
 		            int new_node = newNode();
 		            nodes[new_node].prev = -1;
 		            nodes[new_node].next = -1;
 		            split(r, new_node);
 		            pushAfter(l, new_node);
 		            setPrio(l);
 		            setPrio(new_node);
 		            r = new_node;
+		          }
 		          classes[cs[i]].parent = ~r;
 		          classes[cs[i]].depth = classes[~(nodes[l].parent)].depth;
 		          nodes[r].parent = ~cs[i];
 		          nodes[l].next = -1;
 		          nodes[r].prev = -1;
 		          repairRight(~(nodes[l].parent));
 		          repairLeft(cs[i]);
 		          *out++ = cs[i];
+		        }
+		      }
+		    }
 		    /// \brief Gives back the priority of the current item.
 		    ///
 		    /// \return Gives back the priority of the current item.
 		    const Value& operator[](const Item& item) const {
 		      return nodes[index[item]].prio;
+		    }
 		    /// \brief Sets the priority of the current item.
 		    ///
 		    /// Sets the priority of the current item.
 		    void set(const Item& item, const Value& prio) {
 		      if (comp(prio, nodes[index[item]].prio)) {
 		        decrease(item, prio);
 		      } else if (!comp(prio, nodes[index[item]].prio)) {
 		        increase(item, prio);
+		      }
+		    }
 		    /// \brief Increase the priority of the current item.
 		    ///
 		    /// Increase the priority of the current item.
 		    void increase(const Item& item, const Value& prio) {
 		      int id = index[item];
 		      int kd = nodes[id].parent;
 		      nodes[id].prio = prio;
 		      while (kd >= 0 && nodes[kd].item == item) {
 		        setPrio(kd);
 		        kd = nodes[kd].parent;
+		      }
+		    }
 		    /// \brief Increase the priority of the current item.
 		    ///
 		    /// Increase the priority of the current item.
 		    void decrease(const Item& item, const Value& prio) {
 		      int id = index[item];
 		      int kd = nodes[id].parent;
 		      nodes[id].prio = prio;
 		      while (kd >= 0 && less(id, kd)) {
 		        nodes[kd].prio = prio;
 		        nodes[kd].item = item;
 		        kd = nodes[kd].parent;
+		      }
+		    }
 		    /// \brief Gives back the minimum priority of the class.
 		    ///
 		    /// \return Gives back the minimum priority of the class.
 		    const Value& classPrio(int cls) const {
 		      return nodes[~(classes[cls].parent)].prio;
+		    }
 		    /// \brief Gives back the minimum priority item of the class.
 		    ///
 		    /// \return Gives back the minimum priority item of the class.
 		    const Item& classTop(int cls) const {
 		      return nodes[~(classes[cls].parent)].item;
+		    }
 		    /// \brief Gives back a representant item of the class.
 		    ///
 		    /// The representant is indpendent from the priorities of the
 		    /// items.
 		    /// \return Gives back a representant item of the class.
 		    const Item& classRep(int id) const {
 		      int parent = classes[id].parent;
 		      return nodes[parent >= 0 ? classes[id].depth : leftNode(id)].item;
+		    }
 		    /// \brief Lemon style iterator for the items of a class.
 		    ///
 		    /// ClassIt is a lemon style iterator for the components. It iterates
 		    /// on the items of a class. By example if you want to iterate on
 		    /// each items of each classes then you may write the next code.
 		    ///\code
 		    /// for (ClassIt cit(huf); cit != INVALID; ++cit) {
 		    ///   std::cout << "Class: ";
 		    ///   for (ItemIt iit(huf, cit); iit != INVALID; ++iit) {
 		    ///     std::cout << toString(iit) << ' ' << std::endl;
 		    ///   }
 		    ///   std::cout << std::endl;
 		    /// }
 		    ///\endcode
 		    class ItemIt {
 		    private:
 		      const HeapUnionFind* _huf;
 		      int _id, _lid;
 		    public:
 		      /// \brief Default constructor
 		      ///
 		      /// Default constructor
 		      ItemIt() {}
 		      ItemIt(const HeapUnionFind& huf, int cls) : _huf(&huf) {
 		        int id = cls;
 		        int parent = _huf->classes[id].parent;
 		        if (parent >= 0) {
 		          _id = _huf->classes[id].depth;
 		          if (_huf->classes[id].next != -1) {
 		            _lid = _huf->classes[_huf->classes[id].next].depth;
 		          } else {
 		            _lid = -1;
+		          }
 		        } else {
 		          _id = _huf->leftNode(id);
 		          _lid = -1;
+		        }
+		      }
 		      /// \brief Increment operator
 		      ///
 		      /// It steps to the next item in the class.
 		      ItemIt& operator++() {
 		        _id = _huf->nextNode(_id);
 		        return *this;
+		      }
 		      /// \brief Conversion operator
 		      ///
 		      /// It converts the iterator to the current item.
 		      operator const Item&() const {
 		        return _huf->nodes[_id].item;
+		      }
 		      /// \brief Equality operator
 		      ///
 		      /// Equality operator
 		      bool operator==(const ItemIt& i) {
 		        return i._id == _id;
+		      }
 		      /// \brief Inequality operator
 		      ///
 		      /// Inequality operator
 		      bool operator!=(const ItemIt& i) {
 		        return i._id != _id;
+		      }
 		      /// \brief Equality operator
 		      ///
 		      /// Equality operator
 		      bool operator==(Invalid) {
 		        return _id == _lid;
+		      }
 		      /// \brief Inequality operator
 		      ///
 		      /// Inequality operator
 		      bool operator!=(Invalid) {
 		        return _id != _lid;
+		      }
 		    };
 		    /// \brief Class iterator
 		    ///
 		    /// The iterator stores
 		    class ClassIt {
 		    private:
 		      const HeapUnionFind* _huf;
 		      int _id;
 		    public:
 		      ClassIt(const HeapUnionFind& huf)
 		        : _huf(&huf), _id(huf.first_class) {}
 		      ClassIt(const HeapUnionFind& huf, int cls)
 		        : _huf(&huf), _id(huf.classes[cls].left) {}
 		      ClassIt(Invalid) : _huf(0), _id(-1) {}
 		      const ClassIt& operator++() {
 		        _id = _huf->classes[_id].next;
 			return *this;
+		      }
 		      /// \brief Equality operator
 		      ///
 		      /// Equality operator
 		      bool operator==(const ClassIt& i) {
 		        return i._id == _id;
+		      }
 		      /// \brief Inequality operator
 		      ///
 		      /// Inequality operator
 		      bool operator!=(const ClassIt& i) {
 		        return i._id != _id;
+		      }
 		      operator int() const {
 			return _id;
+		      }
 		    };
 		  };
 		  //! @}
 		} //namespace lemon
 		#endif //LEMON_UNION_FIND_H

test/kruskal_test.cc

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
 		 * Copyright (C) 2003-2008
 		 * 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.
+		 *
 		 */
 		#include <iostream>
 		#include <vector>
 		#include "test_tools.h"
 		#include <lemon/maps.h>
 		#include <lemon/kruskal.h>
 		#include <lemon/list_graph.h>
 		#include <lemon/concepts/maps.h>
 		#include <lemon/concepts/digraph.h>
 		#include <lemon/concepts/graph.h>
 		using namespace std;
 		using namespace lemon;
 		void checkCompileKruskal()
+		{
 		  concepts::WriteMap<concepts::Digraph::Arc,bool> w;
 		  concepts::WriteMap<concepts::Graph::Edge,bool> uw;
 		  concepts::ReadMap<concepts::Digraph::Arc,int> r;
 		  concepts::ReadMap<concepts::Graph::Edge,int> ur;
 		  concepts::Digraph g;
 		  concepts::Graph ug;
 		  kruskal(g, r, w);
 		  kruskal(ug, ur, uw);
 		  std::vector<std::pair<concepts::Digraph::Arc, int> > rs;
 		  std::vector<std::pair<concepts::Graph::Edge, int> > urs;
 		  kruskal(g, rs, w);
 		  kruskal(ug, urs, uw);
 		  std::vector<concepts::Digraph::Arc> ws;
 		  std::vector<concepts::Graph::Edge> uws;
 		  kruskal(g, r, ws.begin());
 		  kruskal(ug, ur, uws.begin());
+		}
 		int main() {
 		  typedef ListGraph::Node Node;
 		  typedef ListGraph::Edge Edge;
 		  typedef ListGraph::NodeIt NodeIt;
 		  typedef ListGraph::ArcIt ArcIt;
 		  ListGraph G;
 		  Node s=G.addNode();
 		  Node v1=G.addNode();
 		  Node v2=G.addNode();
 		  Node v3=G.addNode();
 		  Node v4=G.addNode();
 		  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);
 		  typedef ListGraph::EdgeMap<int> ECostMap;
 		  typedef ListGraph::EdgeMap<bool> EBoolMap;
 		  ECostMap edge_cost_map(G, 2);
 		  EBoolMap tree_map(G);
 		  //Test with const map.
 		  check(kruskal(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10,
 			"Total cost should be 10");
 		  //Test with a edge map (filled with uniform costs).
 		  check(kruskal(G, edge_cost_map, tree_map)==10,
 			"Total cost should be 10");
 		  edge_cost_map.set(e1, -10);
 		  edge_cost_map.set(e2, -9);
 		  edge_cost_map.set(e3, -8);
 		  edge_cost_map.set(e4, -7);
 		  edge_cost_map.set(e5, -6);
 		  edge_cost_map.set(e6, -5);
 		  edge_cost_map.set(e7, -4);
 		  edge_cost_map.set(e8, -3);
 		  edge_cost_map.set(e9, -2);
 		  edge_cost_map.set(e10, -1);
 		  vector<Edge> tree_edge_vec(5);
 		  //Test with a edge map and inserter.
 		  check(kruskal(G, edge_cost_map,
 				 tree_edge_vec.begin())
 			==-31,
 			"Total cost should be -31.");
 		  tree_edge_vec.clear();
 		  check(kruskal(G, edge_cost_map,
 				back_inserter(tree_edge_vec))
 			==-31,
 			"Total cost should be -31.");
 		//   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.");
 		  check(tree_edge_vec.size()==5,"The tree should have 5 edges.");
 		  check(tree_edge_vec[0]==e1 &&
 			tree_edge_vec[1]==e2 &&
 			tree_edge_vec[2]==e5 &&
 			tree_edge_vec[3]==e7 &&
 			tree_edge_vec[4]==e9,
 			"Wrong tree.");
 		  return 0;
+		}

test/unionfind_test.cc

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
 		 * Copyright (C) 2003-2008
 		 * 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.
+		 *
 		 */
 		#include <iostream>
 		#include <lemon/maps.h>
 		#include <lemon/unionfind.h>
 		#include "test_tools.h"
 		using namespace lemon;
 		using namespace std;
 		typedef UnionFindEnum<StdMap<int, int> > UFE;
 		void print(UFE const &ufe) {
 		  cout << "Print the classes of the structure:" << endl;
 		  int i = 1;
 		  for (UFE::ClassIt cit(ufe); cit != INVALID; ++cit) {
 		    cout << "  " << i << " (" << cit << "):" << flush;
 		    for (UFE::ItemIt iit(ufe, cit); iit != INVALID; ++iit) {
 		      cout << " " << iit << flush;
+		    }
 		    cout << endl;
 		    i++;
+		  }
 		  cout << "done" << endl;
+		}
 		int main() {
 		  StdMap<int, int> base;
 		  UFE U(base);
 		  U.insert(1);
 		  U.insert(2);
 		  check(U.join(1,2) != -1,"Test failed.");
 		  U.insert(3);
 		  U.insert(4);
 		  U.insert(5);
 		  U.insert(6);
 		  U.insert(7);
 		  check(U.join(1,4) != -1,"Test failed.");
 		  check(U.join(2,4) == -1,"Test failed.");
 		  check(U.join(3,5) != -1,"Test failed.");
 		  U.insert(8,U.find(5));
 		  check(U.size(U.find(4)) == 3,"Test failed.");
 		  check(U.size(U.find(5)) == 3,"Test failed.");
 		  check(U.size(U.find(6)) == 1,"Test failed.");
 		  check(U.size(U.find(2)) == 3,"Test failed.");
 		  U.insert(9);
 		  U.insert(10,U.find(9));
 		  check(U.join(8,10) != -1,"Test failed.");
 		  check(U.size(U.find(4)) == 3,"Test failed.");
 		  check(U.size(U.find(9)) == 5,"Test failed.");
 		  check(U.size(U.find(8)) == 5,"Test failed.");
 		  U.erase(9);
 		  U.erase(1);
 		  check(U.size(U.find(10)) == 4,"Test failed.");
 		  check(U.size(U.find(2)) == 2,"Test failed.");
 		  U.erase(6);
 		  U.split(U.find(8));
 		  check(U.size(U.find(4)) == 2,"Test failed.");
 		  check(U.size(U.find(3)) == 1,"Test failed.");
 		  check(U.size(U.find(2)) == 2,"Test failed.");
 		  check(U.join(3,4) != -1,"Test failed.");
 		  check(U.join(2,4) == -1,"Test failed.");
 		  check(U.size(U.find(4)) == 3,"Test failed.");
 		  check(U.size(U.find(3)) == 3,"Test failed.");
 		  check(U.size(U.find(2)) == 3,"Test failed.");
 		  U.eraseClass(U.find(4));
 		  U.eraseClass(U.find(7));
 		  return 0;
+		}

lemon/Makefile.am

Show inline comments

 		EXTRA_DIST += \
 			lemon/Makefile \
 			lemon/lemon.pc.in
 		pkgconfig_DATA += lemon/lemon.pc
 		lib_LTLIBRARIES += lemon/libemon.la
 		lemon_libemon_la_SOURCES = \
 		        lemon/base.cc \
 		        lemon/random.cc
 		lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS)
 		lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS)
 		lemon_HEADERS += \
 		        lemon/concept_check.h \
 		        lemon/dim2.h \
 			lemon/error.h \
 			lemon/kruskal.h \
 			lemon/list_graph.h \
 			lemon/maps.h \
 			lemon/math.h \
 		        lemon/random.h \
 		        lemon/tolerance.h
+		        lemon/tolerance.h \
 			lemon/unionfind.h
 		bits_HEADERS += \
 			lemon/bits/alteration_notifier.h \
 			lemon/bits/array_map.h \
 			lemon/bits/base_extender.h \
 			lemon/bits/default_map.h \
 			lemon/bits/graph_extender.h \
 		        lemon/bits/invalid.h \
 			lemon/bits/map_extender.h \
 			lemon/bits/traits.h \
 		        lemon/bits/utility.h \
 			lemon/bits/vector_map.h
 		concept_HEADERS += \
 			lemon/concept_check.h \
 			lemon/concepts/digraph.h \
 			lemon/concepts/graph.h \
 			lemon/concepts/maps.h \
 			lemon/concepts/graph_components.h

test/Makefile.am

Show inline comments

 		EXTRA_DIST += \
 			test/Makefile
 		noinst_HEADERS += \
 			test/digraph_test.h \
 			test/map_test.h \
 		        test/test_tools.h
 		check_PROGRAMS += \
 			test/digraph_test \
 		        test/dim_test \
 			test/graph_test \
 			test/kruskal_test \
 		        test/maps_test \
 		        test/random_test \
 		        test/test_tools_fail \
 		        test/test_tools_pass
+		        test/test_tools_pass \
 			test/unionfind_test
 		TESTS += $(check_PROGRAMS)
 		XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
 		test_digraph_test_SOURCES = test/digraph_test.cc
 		test_dim_test_SOURCES = test/dim_test.cc
 		#test_error_test_SOURCES = test/error_test.cc
 		test_graph_test_SOURCES = test/graph_test.cc
 		test_kruskal_test_SOURCES = test/kruskal_test.cc
 		test_maps_test_SOURCES = test/maps_test.cc
 		test_random_test_SOURCES = test/random_test.cc
 		test_test_tools_fail_SOURCES = test/test_tools_fail.cc
 		test_test_tools_pass_SOURCES = test/test_tools_pass.cc
 		test_unionfind_test_SOURCES = test/unionfind_test.cc

0 comments (0 inline)

RhodeCode

Login to your account