# HG changeset patch
# User ladanyi
# Date 1083849684 0
# Node ID fb261e3a9a0faffb06eb33cfa6a7636a5da57401
# Parent  d8863141824dfd3634fd217a4338e623050102cf
Rename 'include' to 'hugo' (for automake)

diff -r d8863141824d -r fb261e3a9a0f src/hugo/bin_heap.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/hugo/bin_heap.h	Thu May 06 13:21:24 2004 +0000
@@ -0,0 +1,246 @@
+// -*- C++ -*- //
+
+/* FIXME: Copyright ... 
+ *
+ * This implementation is heavily based on STL's heap functions and
+ * the similar class by Alpar Juttner in IKTA...
+ */
+
+/******
+ *
+ * BinHeap<ItemType, PrioType, ItemIntMap, [PrioCompare]>
+ *
+ * Ez az osztaly item-prioritas parok tarolasara alkalmas binaris kupacot
+ * valosit meg.
+ * A kupacban legfolul mindig az a par talalhato, amiben a prioritas a
+ * legkisebb. (Gondolj a Dijkstra pont-tavolsag kupacara; igazabol ahhoz
+ * lett keszitve...)
+ *
+ * Megjegyzes: a kupacos temakorokben a prioritast kulcsnak szoktak nevezni,
+ * de mivel ez zavaro tud lenni a property-map-es kulcs-ertek szohasznalata
+ * miatt, megprobaltunk valami semleges elnevezeseket kitalalni.
+ *
+ * A hasznalatahoz szukseg van egy irhato/olvashato property_map-re, ami
+ * az itemekhez egy int-et tud tarolni (ezzel tudom megkeresni az illeto
+ * elemet a kupacban a csokkentes es hasonlo muveletekhez).
+ * A map-re csak referenciat tarol, ugy hogy a kupac elete folyan a map-nek
+ * is elnie kell. (???)
+ *
+ * Ketfele modon hasznalhato:
+ * Lusta mod:
+ * set(Item, Prio) metodussal pakolunk a kupacba,
+ * aztan o majd eldonti, hogy ez az elem mar benne van-e es ha igen, akkor
+ * csokkentettunk-e rajta, vagy noveltunk.
+ * Ehhez nagyon fontos, hogy az atadott property map inicializalva legyen
+ * minden szobajovo kulcs ertekre, -1 -es ertekkel!
+ * Es ilyen esetben a kulcsokrol lekerdezheto az allapotuk a state metodussal:
+ * (nem jart meg a kupacban PRE_HEAP=-1, epp a kupacban van IN_HEAP=0,
+ *  mar kikerult a kupacbol POST_HEAP=-2).
+ * Szoval ebben a modban a kupac nagyjabol hasznalhato property_map-kent, csak
+ * meg meg tudja mondani a "legkisebb" prioritasu elemet. De csak nagyjabol,
+ * hiszen a kupacbol kikerult elemeknek elvesz az ertekuk...
+ *
+ * Kozvetlen mod:
+ * push(Item, Prio) metodussal belerakunk a kupacba (ha az illeto kulcs mar
+ * benn volt, akkor gaz).
+ * increase/decrease(Item i, Prio new_prio) metodusokkal lehet
+ * novelni/csokkenteni az illeto elemhez tartozo prioritast. (Ha nem volt
+ * megbenne a kupacban az illeto elem, vagy nem abba az iranyba valtoztattad
+ * az erteket, amerre mondtad -- gaz).
+ *
+ * Termeszetesen a fenti ket modot ertelemszeruen lehet keverni.
+ * Ja es mindig nagyon gaz, ha belepiszkalsz a map-be, amit a kupac
+ * hasznal. :-))
+ *
+ *
+ * Bocs, most faradt vagyok, majd egyszer leforditom. (Misi)
+ *
+ */
+
+
+#ifndef BIN_HEAP_HH
+#define BIN_HEAP_HH
+
+///\ingroup auxdat
+///\file
+///\brief Binary Heap implementation.
+
+#include <vector>
+#include <utility>
+#include <functional>
+
+namespace hugo {
+
+  /// \addtogroup auxdat
+  /// @{
+
+   /// A Binary Heap implementation.
+  template <typename Item, typename Prio, typename ItemIntMap,
+	    typename Compare = std::less<Prio> >
+  class BinHeap {
+
+  public:
+    typedef Item                             ItemType;
+    // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...
+    typedef Prio                             PrioType;
+    typedef std::pair<ItemType,PrioType>     PairType;
+    typedef ItemIntMap                       ItemIntMapType;
+    typedef Compare                          PrioCompare;
+
+    /**
+     * Each Item element have a state associated to it. It may be "in heap",
+     * "pre heap" or "post heap". The later two are indifferent from the
+     * heap's point of view, but may be useful to the user.
+     *
+     * The ItemIntMap _should_ be initialized in such way, that it maps
+     * PRE_HEAP (-1) to any element to be put in the heap...
+     */
+    ///\todo it is used nowhere
+    ///
+    enum state_enum {
+      IN_HEAP = 0,
+      PRE_HEAP = -1,
+      POST_HEAP = -2
+    };
+
+  private:
+    std::vector<PairType> data;
+    Compare comp;
+    // FIXME: jo ez igy???
+    ItemIntMap &iim;
+
+  public:
+    BinHeap(ItemIntMap &_iim) : iim(_iim) {}
+    BinHeap(ItemIntMap &_iim, const Compare &_comp) : comp(_comp), iim(_iim) {}
+
+
+    int size() const { return data.size(); }
+    bool empty() const { return data.empty(); }
+
+  private:
+    static int parent(int i) { return (i-1)/2; }
+    static int second_child(int i) { return 2*i+2; }
+    bool less(const PairType &p1, const PairType &p2) const {
+      return comp(p1.second, p2.second);
+    }
+
+    int bubble_up(int hole, PairType p);
+    int bubble_down(int hole, PairType p, int length);
+
+    void move(const PairType &p, int i) {
+      data[i] = p;
+      iim.set(p.first, i);
+    }
+
+    void rmidx(int h) {
+      int n = data.size()-1;
+      if( h>=0 && h<=n ) {
+	iim.set(data[h].first, POST_HEAP);
+	if ( h<n ) {
+	  bubble_down(h, data[n], n);
+	}
+	data.pop_back();
+      }
+    }
+
+  public:
+    void push(const PairType &p) {
+      int n = data.size();
+      data.resize(n+1);
+      bubble_up(n, p);
+    }
+    void push(const Item &i, const Prio &p) { push(PairType(i,p)); }
+
+    Item top() const {
+      return data[0].first;
+    }
+    /// Returns the prio of the top element of the heap.
+    Prio prio() const {
+      return data[0].second;
+    }
+
+    void pop() {
+      rmidx(0);
+    }
+
+    void erase(const Item &i) {
+      rmidx(iim[i]);
+    }
+
+    Prio operator[](const Item &i) const {
+      int idx = iim[i];
+      return data[idx].second;
+    }
+
+    void set(const Item &i, const Prio &p) {
+      int idx = iim[i];
+      if( idx < 0 ) {
+	push(i,p);
+      }
+      else if( comp(p, data[idx].second) ) {
+	bubble_up(idx, PairType(i,p));
+      }
+      else {
+	bubble_down(idx, PairType(i,p), data.size());
+      }
+    }
+
+    void decrease(const Item &i, const Prio &p) {
+      int idx = iim[i];
+      bubble_up(idx, PairType(i,p));
+    }
+    void increase(const Item &i, const Prio &p) {
+      int idx = iim[i];
+      bubble_down(idx, PairType(i,p), data.size());
+    }
+
+    state_enum state(const Item &i) const {
+      int s = iim[i];
+      if( s>=0 )
+	s=0;
+      return state_enum(s);
+    }
+
+  }; // class BinHeap
+
+  
+  template <typename K, typename V, typename M, typename C>
+  int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) {
+    int par = parent(hole);
+    while( hole>0 && less(p,data[par]) ) {
+      move(data[par],hole);
+      hole = par;
+      par = parent(hole);
+    }
+    move(p, hole);
+    return hole;
+  }
+
+  template <typename K, typename V, typename M, typename C>
+  int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) {
+    int child = second_child(hole);
+    while(child < length) {
+      if( less(data[child-1], data[child]) ) {
+	--child;
+      }
+      if( !less(data[child], p) )
+	goto ok;
+      move(data[child], hole);
+      hole = child;
+      child = second_child(hole);
+    }
+    child--;
+    if( child<length && less(data[child], p) ) {
+      move(data[child], hole);
+      hole=child;
+    }
+  ok:
+    move(p, hole);
+    return hole;
+  }
+
+  ///@}
+
+} // namespace hugo
+
+#endif // BIN_HEAP_HH
diff -r d8863141824d -r fb261e3a9a0f src/hugo/dijkstra.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/hugo/dijkstra.h	Thu May 06 13:21:24 2004 +0000
@@ -0,0 +1,208 @@
+// -*- C++ -*-
+#ifndef HUGO_DIJKSTRA_H
+#define HUGO_DIJKSTRA_H
+
+///\ingroup galgs
+///\file
+///\brief Dijkstra algorithm.
+
+#include <bin_heap.h>
+#include <invalid.h>
+
+namespace hugo {
+
+/// \addtogroup galgs
+/// @{
+
+  ///%Dijkstra algorithm class.
+
+  ///This class provides an efficient implementation of %Dijkstra algorithm.
+  ///The edge lengths are passed to the algorithm using a
+  ///\ref ReadMapSkeleton "readable map",
+  ///so it is easy to change it to any kind of length.
+  ///
+  ///The type of the length is determined by the \c ValueType of the length map.
+  ///
+  ///It is also possible to change the underlying priority heap.
+  ///
+  ///\param Graph The graph type the algorithm runs on.
+  ///\param LengthMap This read-only
+  ///EdgeMap
+  ///determines the
+  ///lengths of the edges. It is read once for each edge, so the map
+  ///may involve in relatively time consuming process to compute the edge
+  ///length if it is necessary. The default map type is
+  ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
+  ///\param Heap The heap type used by the %Dijkstra
+  ///algorithm. The default
+  ///is using \ref BinHeap "binary heap".
+  ///
+  ///\author Jacint Szabo
+#ifdef DOXYGEN
+  template <typename Graph,
+	    typename LengthMap,
+	    typename Heap>
+#else
+  template <typename Graph,
+	    typename LengthMap=typename Graph::template EdgeMap<int>,
+	    template <class,class,class,class> class Heap = BinHeap >
+#endif
+  class Dijkstra{
+  public:
+    typedef typename Graph::Node Node;
+    typedef typename Graph::NodeIt NodeIt;
+    typedef typename Graph::Edge Edge;
+    typedef typename Graph::OutEdgeIt OutEdgeIt;
+    
+    typedef typename LengthMap::ValueType ValueType;
+    typedef typename Graph::template NodeMap<Edge> PredMap;
+    typedef typename Graph::template NodeMap<Node> PredNodeMap;
+    typedef typename Graph::template NodeMap<ValueType> DistMap;
+
+  private:
+    const Graph& G;
+    const LengthMap& length;
+    PredMap predecessor;
+    PredNodeMap pred_node;
+    DistMap distance;
+    
+  public :
+    
+    Dijkstra(const Graph& _G, const LengthMap& _length) :
+      G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { }
+    
+    void run(Node s);
+    
+    ///The distance of a node from the root.
+
+    ///Returns the distance of a node from the root.
+    ///\pre \ref run() must be called before using this function.
+    ///\warning If node \c v in unreachable from the root the return value
+    ///of this funcion is undefined.
+    ValueType dist(Node v) const { return distance[v]; }
+
+    ///Returns the previous edge of the shortest path tree.
+
+    ///For a node \c v it returns the previous edge of the shortest path tree,
+    ///i.e. it returns the last edge from a shortest path from the root to \c
+    ///v. It is INVALID if \c v is unreachable from the root or if \c v=s. The
+    ///shortest path tree used here is equal to the shortest path tree used in
+    ///\ref predNode(Node v).  \pre \ref run() must be called before using
+    ///this function.
+    Edge pred(Node v) const { return predecessor[v]; }
+
+    ///Returns the previous node of the shortest path tree.
+
+    ///For a node \c v it returns the previous node of the shortest path tree,
+    ///i.e. it returns the last but one node from a shortest path from the
+    ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
+    ///\c v=s. The shortest path tree used here is equal to the shortest path
+    ///tree used in \ref pred(Node v).  \pre \ref run() must be called before
+    ///using this function.
+    Node predNode(Node v) const { return pred_node[v]; }
+    
+    ///Returns a reference to the NodeMap of distances.
+
+    ///Returns a reference to the NodeMap of distances. \pre \ref run() must
+    ///be called before using this function.
+    const DistMap &distMap() const { return distance;}
+ 
+    ///Returns a reference to the shortest path tree map.
+
+    ///Returns a reference to the NodeMap of the edges of the
+    ///shortest path tree.
+    ///\pre \ref run() must be called before using this function.
+    const PredMap &predMap() const { return predecessor;}
+ 
+    ///Returns a reference to the map of nodes of shortest paths.
+
+    ///Returns a reference to the NodeMap of the last but one nodes of the
+    ///shortest path tree.
+    ///\pre \ref run() must be called before using this function.
+    const PredNodeMap &predNodeMap() const { return pred_node;}
+
+    ///Checks if a node is reachable from the root.
+
+    ///Returns \c true if \c v is reachable from the root.
+    ///\warning the root node is reported to be unreached!
+    ///\todo Is this what we want?
+    ///\pre \ref run() must be called before using this function.
+    ///
+    bool reached(Node v) { return G.valid(predecessor[v]); }
+    
+  };
+  
+
+  // **********************************************************************
+  //  IMPLEMENTATIONS
+  // **********************************************************************
+
+  ///Runs %Dijkstra algorithm from node the root.
+
+  ///This method runs the %Dijkstra algorithm from a root node \c s
+  ///in order to
+  ///compute the
+  ///shortest path to each node. The algorithm computes
+  ///- The shortest path tree.
+  ///- The distance of each node from the root.
+  template <typename Graph, typename LengthMap,
+	    template<class,class,class,class> class Heap >
+  void Dijkstra<Graph,LengthMap,Heap>::run(Node s) {
+    
+    NodeIt u;
+    for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
+      predecessor.set(u,INVALID);
+      pred_node.set(u,INVALID);
+    }
+    
+    typename Graph::template NodeMap<int> heap_map(G,-1);
+    
+    typedef Heap<Node, ValueType, typename Graph::template NodeMap<int>,
+      std::less<ValueType> > 
+      HeapType;
+    
+    HeapType heap(heap_map);
+    
+    heap.push(s,0); 
+    
+      while ( !heap.empty() ) {
+	
+	Node v=heap.top(); 
+	ValueType oldvalue=heap[v];
+	heap.pop();
+	distance.set(v, oldvalue);
+	
+	{ //FIXME this bracket is for e to be local
+	  OutEdgeIt e;
+	for(G.first(e, v);
+	    G.valid(e); G.next(e)) {
+	  Node w=G.bNode(e); 
+	  
+	  switch(heap.state(w)) {
+	  case HeapType::PRE_HEAP:
+	    heap.push(w,oldvalue+length[e]); 
+	    predecessor.set(w,e);
+	    pred_node.set(w,v);
+	    break;
+	  case HeapType::IN_HEAP:
+	    if ( oldvalue+length[e] < heap[w] ) {
+	      heap.decrease(w, oldvalue+length[e]); 
+	      predecessor.set(w,e);
+	      pred_node.set(w,v);
+	    }
+	    break;
+	  case HeapType::POST_HEAP:
+	    break;
+	  }
+	}
+      } //FIXME tis bracket
+      }
+  }
+
+/// @}
+  
+} //END OF NAMESPACE HUGO
+
+#endif
+
+
diff -r d8863141824d -r fb261e3a9a0f src/hugo/dimacs.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/hugo/dimacs.h	Thu May 06 13:21:24 2004 +0000
@@ -0,0 +1,206 @@
+// -*- c++ -*-
+#ifndef HUGO_DIMACS_H
+#define HUGO_DIMACS_H
+
+#include <iostream>
+#include <string>
+#include <vector>
+#include <maps.h>
+
+/// \file
+/// \brief Dimacs file format reader.
+
+namespace hugo {
+
+  /// Dimacs flow file format reader function.
+
+  /// This function reads a flow instance from dimacs flow format.
+  /// At the beginning \c g is cleared by \c g.clear().
+  /// If the data coming from \c is is a max flow problem instance, then 
+  /// \c s and \c t will be respectively the source and target nodes 
+  /// and \c capacity will contain the edge capacities.
+  /// If the data is a shortest path problem instance then \c s will be the 
+  /// source node and \c capacity will contain the edge lengths.
+  ///
+  ///\author Marton Makai
+  template<typename Graph, typename CapacityMap>
+  void readDimacsMaxFlow(std::istream& is, Graph &g, 
+			 typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) {
+    g.clear();
+    int cap;
+    char d;
+    std::string problem;
+    char c;
+    int i, j;
+    std::string str;
+    int n, m; 
+    typename Graph::Edge e;
+    std::vector<typename Graph::Node> nodes;
+    while (is>>c) {
+      switch (c) {
+      case 'c': //comment
+	getline(is, str);
+	break;
+      case 'p': //problem definition
+	is >> problem >> n >> m;
+	getline(is, str);
+	nodes.resize(n+1);
+	for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
+	break;
+      case 'n': //node definition
+	if (problem=="sp") { //shortest path problem
+	  is >> i;
+	  getline(is, str);
+	  s=nodes[i];
+	}
+	if (problem=="max") { //max flow problem
+	  is >> i >> d;
+	  getline(is, str);
+	  if (d=='s') s=nodes[i];
+	  if (d=='t') t=nodes[i];
+	}
+	break;
+      case 'a':
+	is >> i >> j >> cap;
+	getline(is, str);
+	e=g.addEdge(nodes[i], nodes[j]);
+	capacity.update();
+	capacity.set(e, cap);
+	break;
+      }
+    }
+  }
+
+  /// matching problem
+  template<typename Graph>
+  void readDimacs(std::istream& is, Graph &g) {
+    typename Graph::Node u;
+    NullMap<typename Graph::Edge, int> n;
+    readDimacs(is, g, n, u, u, n);
+    std::cout<<"igen en.";
+  }
+
+  /// sg problem
+  template<typename Graph, typename CapacityMap>
+  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
+    typename Graph::Node u;
+    NullMap<typename Graph::Edge, int> n;
+    readDimacs(is, g, capacity, u, u, n);
+  }
+
+  /// shortest path problem
+  template<typename Graph, typename CapacityMap>
+  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 
+		  typename Graph::Node &s) {
+    NullMap<typename Graph::Edge, int> n;
+    readDimacs(is, g, capacity, s, s, n);
+  }
+
+  /// max flow problem
+  template<typename Graph, typename CapacityMap>
+  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 
+		  typename Graph::Node &s, typename Graph::Node &t) {
+    NullMap<typename Graph::Edge, int> n;
+    readDimacs(is, g, capacity, s, t, n);
+  }
+
+  /// min cost flow problem
+  template<typename Graph, typename CapacityMap, typename CostMap>
+  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 
+		  typename Graph::Node &s, typename Graph::Node &t, 
+		  CostMap& cost) {
+    g.clear();
+    typename CapacityMap::ValueType _cap;
+    typename CostMap::ValueType _cost;
+    char d;
+    std::string problem;
+    char c;
+    int i, j;
+    std::string str;
+    int n, m; 
+    typename Graph::Edge e;
+    std::vector<typename Graph::Node> nodes;
+    while (is>>c) {
+      switch (c) {
+      case 'c': //comment
+	getline(is, str);
+	break;
+      case 'p': //problem definition
+	is >> problem >> n >> m;
+	getline(is, str);
+	nodes.resize(n+1);
+	for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
+	break;
+      case 'n': //node definition
+	if (problem=="sp") { //shortest path problem
+	  is >> i;
+	  getline(is, str);
+	  s=nodes[i];
+	}
+	if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem
+	  is >> i >> d;
+	  getline(is, str);
+	  if (d=='s') s=nodes[i];
+	  if (d=='t') t=nodes[i];
+	}
+	break;
+      case 'a':
+	if ( problem == "mat" ) {
+	  is >> i >> j;
+	  getline(is, str);
+	  g.addEdge(nodes[i], nodes[j]);
+	}
+	if ( problem == "max" || problem == "sp") {
+	  is >> i >> j >> _cap;
+	  getline(is, str);
+	  e=g.addEdge(nodes[i], nodes[j]);
+	  capacity.update();
+	  capacity.set(e, _cap);
+	}
+	if ( problem == "min" ) {
+	  is >> i >> j >> _cap >> _cost;
+	  getline(is, str);
+	  e=g.addEdge(nodes[i], nodes[j]);
+	  capacity.update();
+	  capacity.set(e, _cap);
+	  cost.update();
+	  cost.set(e, _cost);
+	}
+	break;
+      }
+    }
+  }
+
+
+  
+  /// write matching problem
+  template<typename Graph>
+  void writeDimacs(std::ostream& os, const Graph &g) {
+    typedef typename Graph::NodeIt NodeIt;
+    typedef typename Graph::EdgeIt EdgeIt;  
+    
+    typename Graph::template NodeMap<int> nodes(g);
+
+    os << "c matching problem" << std::endl;
+
+    int i=1;
+    NodeIt v;
+    for(g.first(v); g.valid(v); g.next(v)) {
+      nodes.set(v, i);
+      ++i;
+    }    
+    
+    os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
+
+    EdgeIt e;
+    for(g.first(e); g.valid(e); g.next(e)) {
+      os << "a " << nodes[g.tail(e)] << " " << nodes[g.head(e)] << std::endl; 
+    }
+
+  }
+
+
+
+} //namespace hugo
+
+#endif //HUGO_DIMACS_H
diff -r d8863141824d -r fb261e3a9a0f src/hugo/error.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/hugo/error.h	Thu May 06 13:21:24 2004 +0000
@@ -0,0 +1,68 @@
+// -*- C++ -*- //
+
+#ifndef HUGO_ERROR_H
+#define HUGO_ERROR_H
+
+//! \ingroup misc
+//! \file
+//! \brief Basic error handling (signaling) routines.
+
+#include <exception>
+#include <string>
+#include <sstream>
+
+
+namespace hugo {
+
+  /**
+   * \brief Generic exception class.
+   *
+   * \todo Do we need this?
+   *
+   * \todo Don't we need different kind of exceptions for different kind
+   * of errors?
+   * Shouldn't we use \<stdexcept\> instead?
+   */
+  class Exception : public std::exception {
+  protected:
+    std::ostringstream buf;
+  public:
+    Exception() {}
+    explicit Exception(const std::string &s) { buf << s; }
+    Exception(const Exception &e) : std::exception() {
+      buf << e.buf.str();
+    }
+    virtual ~Exception() throw() {}
+    
+    virtual const char* what() const throw() {
+      return buf.str().c_str();
+    }
+
+    Exception& operator<<(std::string const& s) { buf << s; return *this; }
+    Exception& operator<<(char const *s) { buf << s; return *this; }
+    Exception& operator<<(int i) { buf << i; return *this; }
+  };
+
+  /**
+   * \brief Generic error signaling function.
+   *
+   * \todo Do we really need this? Is it helpful?
+   */
+  inline void fault(const std::string &msg) {
+    throw Exception(msg);
+  }
+
+  /**
+   * \brief Macro for mark not yet implemented features.
+   *
+   * \todo Is this the right place for this? It should be used only in
+   * modules under development.
+   */
+
+# define FIXME(msg) \
+    do { throw ::hugo::Exception() << "FIXME: " msg " (in: "    \
+      __FILE__ ", " << __LINE__ << ")";                         \
+    } while(false)
+
+}
+#endif // HUGO_ERROR_H
diff -r d8863141824d -r fb261e3a9a0f src/hugo/fib_heap.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/hugo/fib_heap.h	Thu May 06 13:21:24 2004 +0000
@@ -0,0 +1,500 @@
+// -*- C++ -*-
+
+#ifndef HUGO_FIB_HEAP_H
+#define HUGO_FIB_HEAP_H
+
+///\ingroup auxdat
+///\file
+///\brief Fibonacci Heap implementation.
+
+#include <vector>
+#include <functional>
+#include <math.h>
+
+namespace hugo {
+  
+  /// \addtogroup auxdat
+  /// @{
+
+  /// An implementation of the Fibonacci Heap.
+
+  /**
+     This class implements the \e Fibonacci \e heap data structure. A \e heap
+     is a data structure for storing items with specified values called \e
+     priorities, such that finding the item with minimum priority with respect
+     to \e Compare is efficient. In a heap one can change the priority of an
+     item, add or erase an item, etc.
+
+     The methods \ref increase and \ref erase are not efficient in a Fibonacci
+     heap. In case of many calls to these operations, it is better to use a
+     \e binary \e heap.
+     
+     \param Item The type of the items to be stored.  
+     \param Prio The type of the priority of the items.
+     \param ItemIntMap A read and writable Item int map, for the usage of
+     the heap.
+     \param Compare A class for the comparison of the priorities. The
+     default is \c std::less<Prio>.
+
+  */
+
+#ifdef DOXYGEN
+  template <typename Item, 
+	    typename Prio, 
+	    typename ItemIntMap, 
+	    typename Compare>
+#else
+  template <typename Item, 
+	    typename Prio, 
+	    typename ItemIntMap, 
+	    typename Compare = std::less<Prio> >
+#endif
+  class FibHeap {
+  public:     
+    typedef Prio PrioType;
+    
+  private:
+    class store;
+    
+    std::vector<store> container;
+    int minimum;
+    ItemIntMap &iimap;
+    Compare comp;
+    int num_items;
+    
+  public:
+    enum state_enum {
+      IN_HEAP = 0,
+      PRE_HEAP = -1,
+      POST_HEAP = -2
+    };
+    
+    FibHeap(ItemIntMap &_iimap) : minimum(0), iimap(_iimap), num_items() {} 
+    FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0), 
+      iimap(_iimap), comp(_comp), num_items() {}
+    
+    ///The number of items stored in the heap.
+
+    /**
+       Returns the number of items stored in the heap.
+    */
+    int size() const { return num_items; }
+
+    ///Checks if the heap stores no items.
+    
+    /**
+       Returns \c true iff the heap stores no items.
+    */
+    bool empty() const { return num_items==0; }
+
+    ///\c item gets to the heap with priority \c value independently if \c item was already there.
+
+    /**
+       This method calls \ref push(\c item, \c value) if \c item is not
+       stored in the heap and it calls \ref decrease(\c item, \c value) or
+       \ref increase(\c item, \c value) otherwise.
+    */
+    void set (Item const item, PrioType const value); 
+    
+    ///Adds \c item to the heap with priority \c value. 
+    
+    /**
+       Adds \c item to the heap with priority \c value. 
+       \pre \c item must not be stored in the heap. 
+    */
+    void push (Item const item, PrioType const value);
+    
+    
+    ///Returns the item having the minimum priority w.r.t.  Compare.
+    
+    /**
+       This method returns the item having the minimum priority w.r.t.  Compare. 
+       \pre The heap must be nonempty.
+    */
+    Item top() const { return container[minimum].name; }
+    
+
+    ///Returns the minimum priority w.r.t.  Compare.
+
+    /**
+       It returns the minimum priority w.r.t.  Compare.
+       \pre The heap must be nonempty.
+    */
+    PrioType prio() const { return container[minimum].prio; }
+    
+
+    ///Returns the priority of \c item.
+
+    /**
+       It returns the priority of \c item.
+       \pre \c item must be in the heap.
+    */
+    PrioType& operator[](const Item& item) { 
+      return container[iimap[item]].prio; 
+    }
+    
+    ///Returns the priority of \c item.
+    
+    /**
+       It returns the priority of \c item.
+       \pre \c item must be in the heap.
+    */
+    const PrioType& operator[](const Item& item) const { 
+      return container[iimap[item]].prio; 
+    }
+
+
+    ///Deletes the item with minimum priority w.r.t.  Compare.
+
+    /**
+    This method deletes the item with minimum priority w.r.t. 
+    Compare from the heap.
+    \pre The heap must be non-empty.
+    */
+    void pop();
+
+    ///Deletes \c item from the heap.
+
+    /**
+       This method deletes \c item from the heap, if \c item was already
+       stored in the heap. It is quite inefficient in Fibonacci heaps.
+    */
+    void erase (const Item& item); 
+
+    ///Decreases the priority of \c item to \c value.
+
+    /**
+       This method decreases the priority of \c item to \c value.
+       \pre \c item must be stored in the heap with priority at least \c
+       value w.r.t.  Compare.
+    */
+    void decrease (Item item, PrioType const value); 
+
+
+    ///Increases the priority of \c item to \c value.
+
+    /**
+       This method sets the priority of \c item to \c value. Though
+       there is no precondition on the priority of \c item, this
+       method should be used only if there is a need to really \e increase
+       (w.r.t.  Compare) the priority of \c item, because this
+       method is inefficient.
+    */
+    void increase (Item item, PrioType const value) {
+      erase(item);
+      push(item, value);
+    }
+
+
+    ///Tells if \c item is in, was already in, or has never been in the heap.
+
+    /**
+       This method returns PRE_HEAP if \c item has never been in the
+       heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
+       otherwise. In the latter case it is possible that \c item will
+       get back to the heap again.
+    */
+    state_enum state(const Item &item) const {
+      int i=iimap[item];
+      if( i>=0 ) {
+	if ( container[i].in ) i=0;
+	else i=-2; 
+      }
+      return state_enum(i);
+    }    
+    
+  private:
+    
+    void balance();
+    void makeroot(int c);
+    void cut(int a, int b);
+    void cascade(int a);
+    void fuse(int a, int b);
+    void unlace(int a);
+
+
+    class store {
+      friend class FibHeap;
+      
+      Item name;
+      int parent;
+      int left_neighbor;
+      int right_neighbor;
+      int child;
+      int degree;  
+      bool marked;
+      bool in;
+      PrioType prio;
+      
+      store() : parent(-1), child(-1), degree(), marked(false), in(true) {} 
+    };
+  };    
+ 
+
+
+    // **********************************************************************
+    //  IMPLEMENTATIONS
+    // **********************************************************************
+    
+  template <typename Item, typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Item, Prio, ItemIntMap, Compare>::set 
+  (Item const item, PrioType const value) 
+  {
+    int i=iimap[item];
+    if ( i >= 0 && container[i].in ) {
+      if ( comp(value, container[i].prio) ) decrease(item, value); 
+      if ( comp(container[i].prio, value) ) increase(item, value); 
+    } else push(item, value);
+  }
+    
+  template <typename Item, typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Item, Prio, ItemIntMap, Compare>::push 
+  (Item const item, PrioType const value) {
+      int i=iimap[item];      
+      if ( i < 0 ) {
+	int s=container.size();
+	iimap.set( item, s );	
+	store st;
+	st.name=item;
+	container.push_back(st);
+	i=s;
+      } else {
+	container[i].parent=container[i].child=-1;
+	container[i].degree=0;
+	container[i].in=true;
+	container[i].marked=false;
+      }
+
+      if ( num_items ) {
+	container[container[minimum].right_neighbor].left_neighbor=i;
+	container[i].right_neighbor=container[minimum].right_neighbor;
+	container[minimum].right_neighbor=i;
+	container[i].left_neighbor=minimum;
+	if ( comp( value, container[minimum].prio) ) minimum=i; 
+      } else {
+	container[i].right_neighbor=container[i].left_neighbor=i;
+	minimum=i;	
+      }
+      container[i].prio=value;
+      ++num_items;
+    }
+    
+  template <typename Item, typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Item, Prio, ItemIntMap, Compare>::pop() {
+      /*The first case is that there are only one root.*/
+      if ( container[minimum].left_neighbor==minimum ) {
+	container[minimum].in=false;
+	if ( container[minimum].degree!=0 ) { 
+	  makeroot(container[minimum].child);
+	  minimum=container[minimum].child;
+	  balance();
+	}
+      } else {
+	int right=container[minimum].right_neighbor;
+	unlace(minimum);
+	container[minimum].in=false;
+	if ( container[minimum].degree > 0 ) {
+	  int left=container[minimum].left_neighbor;
+	  int child=container[minimum].child;
+	  int last_child=container[child].left_neighbor;
+	
+	  makeroot(child);
+	  
+	  container[left].right_neighbor=child;
+	  container[child].left_neighbor=left;
+	  container[right].left_neighbor=last_child;
+	  container[last_child].right_neighbor=right;
+	}
+	minimum=right;
+	balance();
+      } // the case where there are more roots
+      --num_items;   
+    }
+
+
+  template <typename Item, typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Item, Prio, ItemIntMap, Compare>::erase 
+  (const Item& item) {
+      int i=iimap[item];
+      
+      if ( i >= 0 && container[i].in ) { 	
+	if ( container[i].parent!=-1 ) {
+	  int p=container[i].parent;
+	  cut(i,p);	    
+	  cascade(p);
+	}
+	minimum=i;     //As if its prio would be -infinity
+	pop();
+      }
+  }
+    
+  template <typename Item, typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease 
+  (Item item, PrioType const value) {
+      int i=iimap[item];
+      container[i].prio=value;
+      int p=container[i].parent;
+      
+      if ( p!=-1 && comp(value, container[p].prio) ) {
+	cut(i,p);	    
+	cascade(p);
+      }      
+      if ( comp(value, container[minimum].prio) ) minimum=i; 
+  }
+ 
+
+  template <typename Item, typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() {      
+
+    int maxdeg=int( floor( 2.08*log(double(container.size()))))+1;
+  
+    std::vector<int> A(maxdeg,-1); 
+    
+    /*
+     *Recall that now minimum does not point to the minimum prio element.
+     *We set minimum to this during balance().
+     */
+    int anchor=container[minimum].left_neighbor; 
+    int next=minimum; 
+    bool end=false; 
+    	
+       do {
+	int active=next;
+	if ( anchor==active ) end=true;
+	int d=container[active].degree;
+	next=container[active].right_neighbor;
+
+	while (A[d]!=-1) {	  
+	  if( comp(container[active].prio, container[A[d]].prio) ) {
+	    fuse(active,A[d]); 
+	  } else { 
+	    fuse(A[d],active);
+	    active=A[d];
+	  } 
+	  A[d]=-1;
+	  ++d;
+	}	
+	A[d]=active;
+       } while ( !end );
+
+
+       while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;
+       int s=minimum;
+       int m=minimum;
+       do {  
+	 if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
+	 s=container[s].right_neighbor;
+       } while ( s != m );
+    }
+
+  template <typename Item, typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot 
+  (int c) {
+      int s=c;
+      do {  
+	container[s].parent=-1;
+	s=container[s].right_neighbor;
+      } while ( s != c );
+    }
+  
+  
+  template <typename Item, typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Item, Prio, ItemIntMap, Compare>::cut 
+  (int a, int b) {    
+    /*
+     *Replacing a from the children of b.
+     */
+    --container[b].degree;
+    
+    if ( container[b].degree !=0 ) {
+      int child=container[b].child;
+      if ( child==a ) 
+	container[b].child=container[child].right_neighbor;
+      unlace(a);
+    }
+    
+    
+    /*Lacing a to the roots.*/
+    int right=container[minimum].right_neighbor;
+    container[minimum].right_neighbor=a;
+    container[a].left_neighbor=minimum;
+    container[a].right_neighbor=right;
+    container[right].left_neighbor=a;
+    
+    container[a].parent=-1;
+    container[a].marked=false;
+  }
+  
+
+  template <typename Item, typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade 
+  (int a) 
+    {
+      if ( container[a].parent!=-1 ) {
+	int p=container[a].parent;
+	
+	if ( container[a].marked==false ) container[a].marked=true;
+	else {
+	  cut(a,p);
+	  cascade(p);
+	}
+      }
+    }
+
+
+  template <typename Item, typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse 
+  (int a, int b) {
+      unlace(b);
+      
+      /*Lacing b under a.*/
+      container[b].parent=a;
+
+      if (container[a].degree==0) {
+	container[b].left_neighbor=b;
+	container[b].right_neighbor=b;
+	container[a].child=b;	
+      } else {
+	int child=container[a].child;
+	int last_child=container[child].left_neighbor;
+	container[child].left_neighbor=b;
+	container[b].right_neighbor=child;
+	container[last_child].right_neighbor=b;
+	container[b].left_neighbor=last_child;
+      }
+
+      ++container[a].degree;
+      
+      container[b].marked=false;
+    }
+
+  
+  /*
+   *It is invoked only if a has siblings.
+   */
+  template <typename Item, typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace 
+  (int a) {      
+      int leftn=container[a].left_neighbor;
+      int rightn=container[a].right_neighbor;
+      container[leftn].right_neighbor=rightn;
+      container[rightn].left_neighbor=leftn;
+  }
+  
+  ///@}
+
+} //namespace hugo
+
+#endif //HUGO_FIB_HEAP_H
+
diff -r d8863141824d -r fb261e3a9a0f src/hugo/invalid.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/hugo/invalid.h	Thu May 06 13:21:24 2004 +0000
@@ -0,0 +1,38 @@
+// -*- mode:C++ -*-
+
+#ifndef HUGO_INVALID_H
+#define HUGO_INVALID_H
+
+///\file
+///\brief Definition of INVALID.
+
+namespace hugo {
+
+  /// Dummy type to make it easier to make invalid iterators.
+  
+  /// See \ref INVALID, how to use it.
+  
+  struct Invalid {
+  public:
+    bool operator==(Invalid) { return true;  }
+    bool operator!=(Invalid) { return false; }
+    bool operator< (Invalid) { return false; }
+  };
+  
+  /// Invalid iterators.
+  
+  /// \ref Invalid is a global type that converts to each iterator
+  /// in such a way that the value of the target iterator will be invalid.
+
+  // It is also used to convert the \c INVALID constant to the
+  // node iterator that makes is possible to write 
+
+  //extern Invalid INVALID;
+
+  //const Invalid &INVALID = *(Invalid *)0;
+  const Invalid INVALID = Invalid();
+
+} //namespace hugo
+
+#endif
+  
diff -r d8863141824d -r fb261e3a9a0f src/hugo/maps.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/hugo/maps.h	Thu May 06 13:21:24 2004 +0000
@@ -0,0 +1,129 @@
+// -*- C++ -*- //
+#ifndef HUGO_MAPS_H
+#define HUGO_MAPS_H
+
+///\file
+///\brief Miscellaneous property maps
+///
+///\todo This file has the same name as the concept file in skeletons,
+/// and this is not easily detectable in docs...
+
+#include <map>
+
+namespace hugo {
+
+  /// Null map. (aka DoNothingMap)
+
+  /// If you have to provide a map only for its type definitions,
+  /// or if you have to provide a writable map, but will not use the
+  /// data written to it...
+  template<typename K, typename T>
+  class NullMap
+  {
+  public:
+    typedef K KeyType;
+    typedef T ValueType;
+
+    T operator[](const K&) const { return T(); }
+    void set(const K&, const T&) {}
+    ///\bug when update is removed from map concepts by being dynamic
+    ///stuffs, this line have to be removed.
+    void update() { }
+  };
+
+
+  /// Constant map.
+
+  /// This is a readable map which assignes a specified value to each key.
+  /// In other aspects it is equivalent to the \ref NullMap
+  template<typename K, typename T>
+  class ConstMap
+  {
+    T v;
+  public:
+    typedef K KeyType;
+    typedef T ValueType;
+
+    ConstMap() {}
+    ConstMap(const T &_v) : v(_v) {}
+
+    T operator[](const K&) const { return v; }
+    void set(const K&, const T&) {}
+
+    template<typename T1>
+    struct rebind {
+      typedef ConstMap<K,T1> other;
+    };
+
+    template<typename T1>
+    ConstMap(const ConstMap<K,T1> &, const T &_v) : v(_v) {}
+  };
+
+
+
+  /// \c std::map wrapper
+
+  /// This is essentially a wrapper for \c std::map. With addition that
+  /// you can specify a default value different from \c ValueType() .
+  ///
+  /// \todo Provide allocator parameter...
+  template <typename Key, typename T, typename Compare = std::less<Key> >
+  class StdMap : public std::map<Key,T,Compare> {
+    typedef std::map<Key,T,Compare> parent;
+    T v;
+    typedef typename parent::value_type PairType;
+
+  public:
+    typedef Key KeyType;
+    typedef T ValueType;
+    typedef T& ReferenceType;
+    typedef const T& ConstReferenceType;
+
+
+    StdMap() : v() {}
+    /// Constructor with specified default value
+    StdMap(const T& _v) : v(_v) {}
+
+    /// \brief Constructs the map from an appropriate std::map.
+    ///
+    /// \warning Inefficient: copies the content of \c m !
+    StdMap(const parent &m) : parent(m) {}
+    /// \brief Constructs the map from an appropriate std::map, and explicitly
+    /// specifies a default value.
+    ///
+    /// \warning Inefficient: copies the content of \c m !
+    StdMap(const parent &m, const T& _v) : parent(m), v(_v) {}
+    
+    template<typename T1, typename Comp1>
+    StdMap(const StdMap<Key,T1,Comp1> &m, const T &_v) { 
+      //FIXME; 
+    }
+
+    ReferenceType operator[](const Key &k) {
+      return insert(PairType(k,v)).first -> second;
+    }
+    ConstReferenceType operator[](const Key &k) const {
+      typename parent::iterator i = lower_bound(k);
+      if (i == parent::end() || parent::key_comp()(k, (*i).first))
+	return v;
+      return (*i).second;
+    }
+    void set(const Key &k, const T &t) {
+      parent::operator[](k) = t;
+    }
+
+    /// Changes the default value of the map.
+    /// \return Returns the previous default value.
+    ///
+    /// \warning The value of some keys (which has alredy been queried, but
+    /// the value has been unchanged from the default) may change!
+    T setDefault(const T &_v) { T old=v; v=_v; return old; }
+
+    template<typename T1>
+    struct rebind {
+      typedef StdMap<Key,T1,Compare> other;
+    };
+  };
+  
+}
+#endif // HUGO_MAPS_H
diff -r d8863141824d -r fb261e3a9a0f src/hugo/skeletons/graph.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/hugo/skeletons/graph.h	Thu May 06 13:21:24 2004 +0000
@@ -0,0 +1,399 @@
+// -*- c++ -*-
+#ifndef HUGO_SKELETON_GRAPH_H
+#define HUGO_SKELETON_GRAPH_H
+
+///\file
+///\brief Declaration of GraphSkeleton.
+
+#include <invalid.h>
+
+/// The namespace of HugoLib
+namespace hugo {
+
+  // @defgroup empty_graph The GraphSkeleton class
+  // @{
+
+  /// An empty graph class.
+  
+  /// This class provides all the common features of a graph structure,
+  /// however completely without implementations and real data structures
+  /// behind the interface.
+  /// All graph algorithms should compile with this class, but it will not
+  /// run properly, of course.
+  ///
+  /// It can be used for checking the interface compatibility,
+  /// or it can serve as a skeleton of a new graph structure.
+  /// 
+  /// Also, you will find here the full documentation of a certain graph
+  /// feature, the documentation of a real graph imlementation
+  /// like @ref ListGraph or
+  /// @ref SmartGraph will just refer to this structure.
+  class GraphSkeleton
+  {
+  public:
+    /// Defalult constructor.
+    GraphSkeleton() {}
+    ///Copy consructor.
+
+    ///\todo It is not clear, what we expect from a copy constructor.
+    ///E.g. How to assign the nodes/edges to each other? What about maps?
+    GraphSkeleton(const GraphSkeleton &G) {}
+
+    /// The base type of the node iterators.
+
+    /// This is the base type of each node iterators,
+    /// thus each kind of node iterator will convert to this.
+    class Node {
+    public:
+      /// @warning The default constructor sets the iterator
+      /// to an undefined value.
+      Node() {}   //FIXME
+      /// Invalid constructor \& conversion.
+
+      /// This constructor initializes the iterator to be invalid.
+      /// \sa Invalid for more details.
+
+      Node(Invalid) {}
+      //Node(const Node &) {}
+
+      /// Two iterators are equal if and only if they point to the
+      /// same object or both are invalid.
+      bool operator==(Node) const { return true; }
+
+      /// \sa \ref operator==(Node n)
+      ///
+      bool operator!=(Node) const { return true; }
+
+      bool operator<(Node) const { return true; }
+    };
+    
+    /// This iterator goes through each node.
+
+    /// This iterator goes through each node.
+    /// Its usage is quite simple, for example you can count the number
+    /// of nodes in graph \c G of type \c Graph like this:
+    /// \code
+    ///int count=0;
+    ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++;
+    /// \endcode
+    class NodeIt : public Node {
+    public:
+      /// @warning The default constructor sets the iterator
+      /// to an undefined value.
+      NodeIt() {} //FIXME
+      /// Invalid constructor \& conversion.
+
+      /// Initialize the iterator to be invalid
+      /// \sa Invalid for more details.
+      NodeIt(Invalid) {}
+      /// Sets the iterator to the first node of \c G.
+      NodeIt(const GraphSkeleton &) {}
+      /// @warning The default constructor sets the iterator
+      /// to an undefined value.
+      NodeIt(const NodeIt &n) : Node(n) {}
+    };
+    
+    
+    /// The base type of the edge iterators.
+    class Edge {
+    public:
+      /// @warning The default constructor sets the iterator
+      /// to an undefined value.
+      Edge() {}   //FIXME
+      /// Initialize the iterator to be invalid
+      Edge(Invalid) {}
+      /// Two iterators are equal if and only if they point to the
+      /// same object or both are invalid.
+      bool operator==(Edge) const { return true; }
+      bool operator!=(Edge) const { return true; }
+      bool operator<(Edge) const { return true; }
+    };
+    
+    /// This iterator goes trough the outgoing edges of a node.
+
+    /// This iterator goes trough the \e outgoing edges of a certain node
+    /// of a graph.
+    /// Its usage is quite simple, for example you can count the number
+    /// of outgoing edges of a node \c n
+    /// in graph \c G of type \c Graph as follows.
+    /// \code
+    ///int count=0;
+    ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
+    /// \endcode
+    
+    class OutEdgeIt : public Edge {
+    public:
+      /// @warning The default constructor sets the iterator
+      /// to an undefined value.
+      OutEdgeIt() {}
+      /// Initialize the iterator to be invalid
+      OutEdgeIt(Invalid) {}
+      /// This constructor sets the iterator to first outgoing edge.
+    
+      /// This constructor set the iterator to the first outgoing edge of
+      /// node
+      ///@param n the node
+      ///@param G the graph
+      OutEdgeIt(const GraphSkeleton &, Node) {}
+    };
+
+    /// This iterator goes trough the incoming edges of a node.
+
+    /// This iterator goes trough the \e incoming edges of a certain node
+    /// of a graph.
+    /// Its usage is quite simple, for example you can count the number
+    /// of outgoing edges of a node \c n
+    /// in graph \c G of type \c Graph as follows.
+    /// \code
+    ///int count=0;
+    ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
+    /// \endcode
+
+    class InEdgeIt : public Edge {
+    public:
+      /// @warning The default constructor sets the iterator
+      /// to an undefined value.
+      InEdgeIt() {}
+      /// Initialize the iterator to be invalid
+      InEdgeIt(Invalid) {}
+      InEdgeIt(const GraphSkeleton &, Node) {}    
+    };
+    //  class SymEdgeIt : public Edge {};
+
+    /// This iterator goes through each edge.
+
+    /// This iterator goes through each edge of a graph.
+    /// Its usage is quite simple, for example you can count the number
+    /// of edges in a graph \c G of type \c Graph as follows:
+    /// \code
+    ///int count=0;
+    ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++;
+    /// \endcode
+    class EdgeIt : public Edge {
+    public:
+      /// @warning The default constructor sets the iterator
+      /// to an undefined value.
+      EdgeIt() {}
+      /// Initialize the iterator to be invalid
+      EdgeIt(Invalid) {}
+      EdgeIt(const GraphSkeleton &) {}
+    };
+
+    /// First node of the graph.
+
+    /// \retval i the first node.
+    /// \return the first node.
+    ///
+    NodeIt &first(NodeIt &i) const { return i;}
+
+    /// The first incoming edge.
+    InEdgeIt &first(InEdgeIt &i, Node) const { return i;}
+    /// The first outgoing edge.
+    OutEdgeIt &first(OutEdgeIt &i, Node) const { return i;}
+    //  SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
+    /// The first edge of the Graph.
+    EdgeIt &first(EdgeIt &i) const { return i;}
+
+//     Node getNext(Node) const {}
+//     InEdgeIt getNext(InEdgeIt) const {}
+//     OutEdgeIt getNext(OutEdgeIt) const {}
+//     //SymEdgeIt getNext(SymEdgeIt) const {}
+//     EdgeIt getNext(EdgeIt) const {}
+
+    /// Go to the next node.
+    NodeIt &next(NodeIt &i) const { return i;}
+    /// Go to the next incoming edge.
+    InEdgeIt &next(InEdgeIt &i) const { return i;}
+    /// Go to the next outgoing edge.
+    OutEdgeIt &next(OutEdgeIt &i) const { return i;}
+    //SymEdgeIt &next(SymEdgeIt &) const {}
+    /// Go to the next edge.
+    EdgeIt &next(EdgeIt &i) const { return i;}
+
+    ///Gives back the head node of an edge.
+    Node head(Edge) const { return INVALID; }
+    ///Gives back the tail node of an edge.
+    Node tail(Edge) const { return INVALID; }
+  
+    //   Node aNode(InEdgeIt) const {}
+    //   Node aNode(OutEdgeIt) const {}
+    //   Node aNode(SymEdgeIt) const {}
+
+    //   Node bNode(InEdgeIt) const {}
+    //   Node bNode(OutEdgeIt) const {}
+    //   Node bNode(SymEdgeIt) const {}
+
+    /// Checks if a node iterator is valid
+
+    ///\todo Maybe, it would be better if iterator converted to
+    ///bool directly, as Jacint prefers.
+    bool valid(const Node&) const { return true;}
+    /// Checks if an edge iterator is valid
+
+    ///\todo Maybe, it would be better if iterator converted to
+    ///bool directly, as Jacint prefers.
+    bool valid(const Edge&) const { return true;}
+
+    ///Gives back the \e id of a node.
+
+    ///\warning Not all graph structures provide this feature.
+    ///
+    int id(const Node&) const { return 0;}
+    ///Gives back the \e id of an edge.
+
+    ///\warning Not all graph structures provide this feature.
+    ///
+    int id(const Edge&) const { return 0;}
+
+    //void setInvalid(Node &) const {};
+    //void setInvalid(Edge &) const {};
+  
+    ///Add a new node to the graph.
+
+    /// \return the new node.
+    ///
+    Node addNode() { return INVALID;}
+    ///Add a new edge to the graph.
+
+    ///Add a new edge to the graph with tail node \c tail
+    ///and head node \c head.
+    ///\return the new edge.
+    Edge addEdge(Node, Node) { return INVALID;}
+    
+    /// Resets the graph.
+
+    /// This function deletes all edges and nodes of the graph.
+    /// It also frees the memory allocated to store them.
+    void clear() {}
+
+    int nodeNum() const { return 0;}
+    int edgeNum() const { return 0;}
+
+    ///Read/write/reference map of the nodes to type \c T.
+
+    ///Read/write/reference map of the nodes to type \c T.
+    /// \sa MemoryMapSkeleton
+    /// \todo We may need copy constructor
+    /// \todo We may need conversion from other nodetype
+    /// \todo We may need operator=
+    /// \warning Making maps that can handle bool type (NodeMap<bool>)
+    /// needs extra attention!
+
+    template<class T> class NodeMap
+    {
+    public:
+      typedef T ValueType;
+      typedef Node KeyType;
+
+      NodeMap(const GraphSkeleton &) {}
+      NodeMap(const GraphSkeleton &, T) {}
+
+      template<typename TT> NodeMap(const NodeMap<TT> &) {}
+
+      /// Sets the value of a node.
+
+      /// Sets the value associated with node \c i to the value \c t.
+      ///
+      void set(Node, T) {}
+      // Gets the value of a node.
+      //T get(Node i) const {return *(T*)0;}  //FIXME: Is it necessary?
+      T &operator[](Node) {return *(T*)0;}
+      const T &operator[](Node) const {return *(T*)0;}
+
+      /// Updates the map if the graph has been changed
+
+      /// \todo Do we need this?
+      ///
+      void update() {}
+      void update(T a) {}   //FIXME: Is it necessary
+    };
+
+    ///Read/write/reference map of the edges to type \c T.
+
+    ///Read/write/reference map of the edges to type \c T.
+    ///It behaves exactly in the same way as \ref NodeMap.
+    /// \sa NodeMap
+    /// \sa MemoryMapSkeleton
+    /// \todo We may need copy constructor
+    /// \todo We may need conversion from other edgetype
+    /// \todo We may need operator=
+    template<class T> class EdgeMap
+    {
+    public:
+      typedef T ValueType;
+      typedef Edge KeyType;
+
+      EdgeMap(const GraphSkeleton &) {}
+      EdgeMap(const GraphSkeleton &, T ) {}
+    
+      ///\todo It can copy between different types.
+      ///
+      template<typename TT> EdgeMap(const EdgeMap<TT> &) {}
+
+      void set(Edge, T) {}
+      //T get(Edge) const {return *(T*)0;}
+      T &operator[](Edge) {return *(T*)0;}
+      const T &operator[](Edge) const {return *(T*)0;}
+    
+      void update() {}
+      void update(T a) {}   //FIXME: Is it necessary
+    };
+  };
+
+  /// An empty eraseable graph class.
+  
+  /// This class provides all the common features of an \e eraseable graph
+  /// structure,
+  /// however completely without implementations and real data structures
+  /// behind the interface.
+  /// All graph algorithms should compile with this class, but it will not
+  /// run properly, of course.
+  ///
+  /// \todo This blabla could be replaced by a sepatate description about
+  /// Skeletons.
+  ///
+  /// It can be used for checking the interface compatibility,
+  /// or it can serve as a skeleton of a new graph structure.
+  /// 
+  /// Also, you will find here the full documentation of a certain graph
+  /// feature, the documentation of a real graph imlementation
+  /// like @ref ListGraph or
+  /// @ref SmartGraph will just refer to this structure.
+  class EraseableGraphSkeleton : public GraphSkeleton
+  {
+  public:
+    /// Deletes a node.
+    void erase(Node n) {}
+    /// Deletes an edge.
+    void erase(Edge e) {}
+
+    /// Defalult constructor.
+    EraseableGraphSkeleton() {}
+    ///Copy consructor.
+    EraseableGraphSkeleton(const GraphSkeleton &G) {}
+  };
+
+  
+  // @}
+
+} //namespace hugo
+
+
+
+// class EmptyBipGraph : public Graph Skeleton
+// {
+//   class ANode {};
+//   class BNode {};
+
+//   ANode &next(ANode &) {}
+//   BNode &next(BNode &) {}
+
+//   ANode &getFirst(ANode &) const {}
+//   BNode &getFirst(BNode &) const {}
+
+//   enum NodeClass { A = 0, B = 1 };
+//   NodeClass getClass(Node n) {}
+
+// }
+
+#endif // HUGO_SKELETON_GRAPH_H
diff -r d8863141824d -r fb261e3a9a0f src/hugo/skeletons/maps.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/hugo/skeletons/maps.h	Thu May 06 13:21:24 2004 +0000
@@ -0,0 +1,130 @@
+// -*- c++ -*-
+#ifndef HUGO_MAPSKELETON_H
+#define HUGO_MAPSKELETON_H
+
+///\file
+///\brief Map concepts checking classes for testing and documenting.
+
+namespace hugo {
+
+  /// The namespace of HUGOlib concepts and concept checking classes
+  namespace skeleton {
+  
+    /// Readable map concept
+    template<typename K, typename T>
+    class ReadableMap
+    {
+    public:
+      /// Map's key type.
+      typedef K KeyType;    
+      /// Map's value type. (The type of objects associated with the keys).
+      typedef T ValueType;
+
+      /// Returns the value associated with a key.
+      ValueType operator[](const KeyType &k) const {return ValueType();}
+
+      /// Copy contsructor. (optional)
+      ReadableMap(const ReadableMap&) {}
+      /// Assignment operator. (optional)
+      ReadableMap& operator=(const ReadableMap&) {return *this;}
+
+      ReadableMap() {}
+    };
+
+
+    /// Writable map concept
+    template<typename K, typename T>
+    class WritableMap
+    {
+    public:
+      /// Map's key type.
+      typedef K KeyType;    
+      /// Map's value type. (The type of objects associated with the keys).
+      typedef T ValueType;
+
+      /// Sets the value associated with a key.
+      void set(const KeyType &k,const ValueType &t) {}
+
+      WritableMap() {}
+    };
+
+    ///Read/Writeable map concept
+    template<typename K, typename T>
+    class ReadWritableMap : public ReadableMap<K,T>,
+			    public WritableMap<K,T>
+    {
+    public:
+      /// Map's key type.
+      typedef K KeyType;    
+      /// Map's value type. (The type of objects associated with the keys).
+      typedef T ValueType;
+
+      /// Returns the value associated with a key.
+      ValueType operator[](const KeyType &k) const {return ValueType();}
+      /// Sets the value associated with a key.
+      void set(const KeyType &k,const ValueType &t) {}
+
+      /// Copy contsructor. (optional)
+      ReadWritableMap(const ReadWritableMap&) {}
+      /// Assignment operator. (optional)
+      ReadWritableMap& operator=(const ReadWritableMap&) {return *this;}
+
+      /// Facility to define a map with an other value type (optional)
+      template<typename T1>
+      struct rebind {
+	/// The type of a map with the given value type
+	typedef ReadWritableMap<K,T1> other;
+      };
+      /// @brief Constructor that copies all keys from the other map and
+      /// assigns to them a default value (optional)
+      template<typename T1>
+      ReadWritableMap(const ReadWritableMap<K,T1> &map, const ValueType &v) {}
+
+      ReadWritableMap() {}
+    };
+  
+  
+    ///Dereferable map concept
+    template<typename K, typename T>
+    class DereferableMap : public ReadWritableMap<K,T>
+    {
+    public:
+      /// Map's key type.
+      typedef K KeyType;    
+      /// Map's value type. (The type of objects associated with the keys).
+      typedef T ValueType;
+      /// Map's reference type. (Reference to an object associated with a key)
+      typedef ValueType& ReferenceType;
+      /// Map's const reference type.
+      typedef const ValueType& ConstReferenceType;
+
+      ///Returns a reference to the value associated to a key.
+      ReferenceType operator[](const KeyType &i);
+      ///Returns a const reference to the value associated to a key.
+      ConstReferenceType operator[](const KeyType &i) const;
+      /// Sets the value associated with a key.
+      void set(const KeyType &k,const ValueType &t) { operator[](k)=t; }
+
+      /// Copy contsructor. (optional)
+      DereferableMap(const DereferableMap&) {}
+      /// Assignment operator. (optional)
+      DereferableMap& operator=(const DereferableMap&) {return *this;}
+
+      /// Facility to define a map with an other value type (optional)
+      template<typename T1>
+      struct rebind {
+	/// The type of a map with the given value type
+	typedef DereferableMap<K,T1> other;
+      };
+      /// @brief Constructor that copies all keys from the other map and
+      /// assigns to them a default value (optional)
+      template<typename T1>
+      DereferableMap(const DereferableMap<K,T1> &map, const ValueType &v) {}
+
+      DereferableMap() {}
+    };
+
+
+  }
+}
+#endif // HUGO_MAPSKELETON_H
diff -r d8863141824d -r fb261e3a9a0f src/hugo/smart_graph.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/hugo/smart_graph.h	Thu May 06 13:21:24 2004 +0000
@@ -0,0 +1,614 @@
+// -*- mode:C++ -*-
+
+#ifndef HUGO_SMART_GRAPH_H
+#define HUGO_SMART_GRAPH_H
+
+///\ingroup graphs
+///\file
+///\brief SmartGraph and SymSmartGraph classes.
+
+#include <vector>
+#include <limits.h>
+
+#include "invalid.h"
+
+namespace hugo {
+
+/// \addtogroup graphs
+/// @{
+  class SymSmartGraph;
+
+  ///A smart graph class.
+
+  ///This is a simple and fast graph implementation.
+  ///It is also quite memory efficient, but at the price
+  ///that <b> it does not support node and edge deletion</b>.
+  ///It conforms to the graph interface documented under
+  ///the description of \ref GraphSkeleton.
+  ///\sa \ref GraphSkeleton.
+  ///
+  ///\todo Some member functions could be \c static.
+  ///\author Alpar Juttner
+  class SmartGraph {
+
+    struct NodeT 
+    {
+      int first_in,first_out;      
+      NodeT() : first_in(-1), first_out(-1) {}
+    };
+    struct EdgeT 
+    {
+      int head, tail, next_in, next_out;      
+      //FIXME: is this necessary?
+      EdgeT() : next_in(-1), next_out(-1) {}  
+    };
+
+    std::vector<NodeT> nodes;
+
+    std::vector<EdgeT> edges;
+    
+    protected:
+    
+    template <typename Key> class DynMapBase
+    {
+    protected:
+      const SmartGraph* G; 
+    public:
+      virtual void add(const Key k) = 0;
+      virtual void erase(const Key k) = 0;
+      DynMapBase(const SmartGraph &_G) : G(&_G) {}
+      virtual ~DynMapBase() {}
+      friend class SmartGraph;
+    };
+    
+  public:
+    template <typename T> class EdgeMap;
+    template <typename T> class EdgeMap;
+
+    class Node;
+    class Edge;
+
+    //  protected:
+    // HELPME:
+  protected:
+    ///\bug It must be public because of SymEdgeMap.
+    ///
+    mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
+    ///\bug It must be public because of SymEdgeMap.
+    ///
+    mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
+    
+  public:
+
+
+    class NodeIt;
+    class EdgeIt;
+    class OutEdgeIt;
+    class InEdgeIt;
+    
+    template <typename T> class NodeMap;
+    template <typename T> class EdgeMap;
+    
+  public:
+
+    SmartGraph() : nodes(), edges() { }
+    SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
+    
+    ~SmartGraph()
+    {
+      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
+	  i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
+      for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
+	  i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
+    }
+
+    int nodeNum() const { return nodes.size(); }  //FIXME: What is this?
+    int edgeNum() const { return edges.size(); }  //FIXME: What is this?
+
+    ///\bug This function does something different than
+    ///its name would suggests...
+    int maxNodeId() const { return nodes.size(); }  //FIXME: What is this?
+    ///\bug This function does something different than
+    ///its name would suggests...
+    int maxEdgeId() const { return edges.size(); }  //FIXME: What is this?
+
+    Node tail(Edge e) const { return edges[e.n].tail; }
+    Node head(Edge e) const { return edges[e.n].head; }
+
+    Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
+    Node aNode(InEdgeIt e) const { return edges[e.n].head; }
+
+    Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
+    Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
+
+    NodeIt& first(NodeIt& v) const { 
+      v=NodeIt(*this); return v; }
+    EdgeIt& first(EdgeIt& e) const { 
+      e=EdgeIt(*this); return e; }
+    OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 
+      e=OutEdgeIt(*this,v); return e; }
+    InEdgeIt& first(InEdgeIt& e, const Node v) const { 
+      e=InEdgeIt(*this,v); return e; }
+
+//     template< typename It >
+//     It first() const { It e; first(e); return e; }
+
+//     template< typename It >
+//     It first(Node v) const { It e; first(e,v); return e; }
+
+    bool valid(Edge e) const { return e.n!=-1; }
+    bool valid(Node n) const { return n.n!=-1; }
+    
+    ///\deprecated Use
+    ///\code
+    ///  e=INVALID;
+    ///\endcode
+    ///instead.
+    void setInvalid(Edge &e) { e.n=-1; }
+    ///\deprecated Use
+    ///\code
+    ///  e=INVALID;
+    ///\endcode
+    ///instead.
+    void setInvalid(Node &n) { n.n=-1; }
+    
+    template <typename It> It getNext(It it) const
+    { It tmp(it); return next(tmp); }
+
+    NodeIt& next(NodeIt& it) const { 
+      it.n=(it.n+2)%(nodes.size()+1)-1; 
+      return it; 
+    }
+    OutEdgeIt& next(OutEdgeIt& it) const
+    { it.n=edges[it.n].next_out; return it; }
+    InEdgeIt& next(InEdgeIt& it) const
+    { it.n=edges[it.n].next_in; return it; }
+    EdgeIt& next(EdgeIt& it) const { --it.n; return it; }
+
+    int id(Node v) const { return v.n; }
+    int id(Edge e) const { return e.n; }
+
+    Node addNode() {
+      Node n; n.n=nodes.size();
+      nodes.push_back(NodeT()); //FIXME: Hmmm...
+
+      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
+	  i!=dyn_node_maps.end(); ++i) (**i).add(n);
+
+      return n;
+    }
+    
+    Edge addEdge(Node u, Node v) {
+      Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
+      edges[e.n].tail=u.n; edges[e.n].head=v.n;
+      edges[e.n].next_out=nodes[u.n].first_out;
+      edges[e.n].next_in=nodes[v.n].first_in;
+      nodes[u.n].first_out=nodes[v.n].first_in=e.n;
+
+      for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
+	  i!=dyn_edge_maps.end(); ++i) (**i).add(e);
+
+      return e;
+    }
+
+    void clear() {nodes.clear();edges.clear();}
+
+    class Node {
+      friend class SmartGraph;
+      template <typename T> friend class NodeMap;
+      
+      friend class Edge;
+      friend class OutEdgeIt;
+      friend class InEdgeIt;
+      friend class SymEdge;
+
+    protected:
+      int n;
+      friend int SmartGraph::id(Node v) const; 
+      Node(int nn) {n=nn;}
+    public:
+      Node() {}
+      Node (Invalid) { n=-1; }
+      bool operator==(const Node i) const {return n==i.n;}
+      bool operator!=(const Node i) const {return n!=i.n;}
+      bool operator<(const Node i) const {return n<i.n;}
+    };
+    
+    class NodeIt : public Node {
+      friend class SmartGraph;
+    public:
+      NodeIt() : Node() { }
+      NodeIt(Invalid i) : Node(i) { }
+      NodeIt(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { }
+    };
+
+    class Edge {
+      friend class SmartGraph;
+      template <typename T> friend class EdgeMap;
+
+      //template <typename T> friend class SymSmartGraph::SymEdgeMap;      
+      //friend Edge SymSmartGraph::opposite(Edge) const;
+      
+      friend class Node;
+      friend class NodeIt;
+    protected:
+      int n;
+      friend int SmartGraph::id(Edge e) const;
+
+      Edge(int nn) {n=nn;}
+    public:
+      Edge() { }
+      Edge (Invalid) { n=-1; }
+      bool operator==(const Edge i) const {return n==i.n;}
+      bool operator!=(const Edge i) const {return n!=i.n;}
+      bool operator<(const Edge i) const {return n<i.n;}
+      ///\bug This is a workaround until somebody tells me how to
+      ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
+      int &idref() {return n;}
+      const int &idref() const {return n;}
+    };
+    
+    class EdgeIt : public Edge {
+      friend class SmartGraph;
+    public:
+      EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { }
+      EdgeIt (Invalid i) : Edge(i) { }
+      EdgeIt() : Edge() { }
+      ///\bug This is a workaround until somebody tells me how to
+      ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
+      int &idref() {return n;}
+    };
+    
+    class OutEdgeIt : public Edge {
+      friend class SmartGraph;
+    public: 
+      OutEdgeIt() : Edge() { }
+      OutEdgeIt (Invalid i) : Edge(i) { }
+
+      OutEdgeIt(const SmartGraph& G,const Node v)
+	: Edge(G.nodes[v.n].first_out) {}
+    };
+    
+    class InEdgeIt : public Edge {
+      friend class SmartGraph;
+    public: 
+      InEdgeIt() : Edge() { }
+      InEdgeIt (Invalid i) : Edge(i) { }
+      InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
+    };
+
+    template <typename T> class NodeMap : public DynMapBase<Node>
+    {
+      std::vector<T> container;
+
+    public:
+      typedef T ValueType;
+      typedef Node KeyType;
+
+      NodeMap(const SmartGraph &_G) :
+	DynMapBase<Node>(_G), container(_G.maxNodeId())
+      {
+	G->dyn_node_maps.push_back(this);
+      }
+      NodeMap(const SmartGraph &_G,const T &t) :
+	DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
+      {
+	G->dyn_node_maps.push_back(this);
+      }
+      
+      NodeMap(const NodeMap<T> &m) :
+ 	DynMapBase<Node>(*m.G), container(m.container)
+      {
+ 	G->dyn_node_maps.push_back(this);
+      }
+
+      template<typename TT> friend class NodeMap;
+ 
+      ///\todo It can copy between different types.
+      ///
+      template<typename TT> NodeMap(const NodeMap<TT> &m) :
+	DynMapBase<Node>(*m.G)
+      {
+	G->dyn_node_maps.push_back(this);
+	typename std::vector<TT>::const_iterator i;
+	for(typename std::vector<TT>::const_iterator i=m.container.begin();
+	    i!=m.container.end();
+	    i++)
+	  container.push_back(*i);
+      }
+      ~NodeMap()
+      {
+	if(G) {
+	  std::vector<DynMapBase<Node>* >::iterator i;
+	  for(i=G->dyn_node_maps.begin();
+	      i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
+	  //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
+	  //A better way to do that: (Is this really important?)
+	  if(*i==this) {
+	    *i=G->dyn_node_maps.back();
+	    G->dyn_node_maps.pop_back();
+	  }
+	}
+      }
+
+      void add(const Node k) 
+      {
+	if(k.n>=int(container.size())) container.resize(k.n+1);
+      }
+
+      void erase(const Node) { }
+      
+      void set(Node n, T a) { container[n.n]=a; }
+      //'T& operator[](Node n)' would be wrong here
+      typename std::vector<T>::reference
+      operator[](Node n) { return container[n.n]; }
+      //'const T& operator[](Node n)' would be wrong here
+      typename std::vector<T>::const_reference 
+      operator[](Node n) const { return container[n.n]; }
+
+      ///\warning There is no safety check at all!
+      ///Using operator = between maps attached to different graph may
+      ///cause serious problem.
+      ///\todo Is this really so?
+      ///\todo It can copy between different types.
+      const NodeMap<T>& operator=(const NodeMap<T> &m)
+      {
+	container = m.container;
+	return *this;
+      }
+      template<typename TT>
+      const NodeMap<T>& operator=(const NodeMap<TT> &m)
+      {
+	std::copy(m.container.begin(), m.container.end(), container.begin());
+	return *this;
+      }
+      
+      void update() {}    //Useless for Dynamic Maps
+      void update(T a) {}  //Useless for Dynamic Maps
+    };
+    
+    template <typename T> class EdgeMap : public DynMapBase<Edge>
+    {
+      std::vector<T> container;
+
+    public:
+      typedef T ValueType;
+      typedef Edge KeyType;
+
+      EdgeMap(const SmartGraph &_G) :
+	DynMapBase<Edge>(_G), container(_G.maxEdgeId())
+      {
+	//FIXME: What if there are empty Id's?
+	//FIXME: Can I use 'this' in a constructor?
+	G->dyn_edge_maps.push_back(this);
+      }
+      EdgeMap(const SmartGraph &_G,const T &t) :
+	DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
+      {
+	G->dyn_edge_maps.push_back(this);
+      } 
+      EdgeMap(const EdgeMap<T> &m) :
+ 	DynMapBase<Edge>(*m.G), container(m.container)
+      {
+ 	G->dyn_edge_maps.push_back(this);
+      }
+
+      template<typename TT> friend class EdgeMap;
+
+      ///\todo It can copy between different types.
+      ///
+      template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
+	DynMapBase<Edge>(*m.G)
+      {
+	G->dyn_edge_maps.push_back(this);
+	typename std::vector<TT>::const_iterator i;
+	for(typename std::vector<TT>::const_iterator i=m.container.begin();
+	    i!=m.container.end();
+	    i++)
+	  container.push_back(*i);
+      }
+      ~EdgeMap()
+      {
+	if(G) {
+	  std::vector<DynMapBase<Edge>* >::iterator i;
+	  for(i=G->dyn_edge_maps.begin();
+	      i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
+	  //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
+	  //A better way to do that: (Is this really important?)
+	  if(*i==this) {
+	    *i=G->dyn_edge_maps.back();
+	    G->dyn_edge_maps.pop_back();
+	  }
+	}
+      }
+      
+      void add(const Edge k) 
+      {
+	if(k.n>=int(container.size())) container.resize(k.n+1);
+      }
+      void erase(const Edge) { }
+      
+      void set(Edge n, T a) { container[n.n]=a; }
+      //T get(Edge n) const { return container[n.n]; }
+      typename std::vector<T>::reference
+      operator[](Edge n) { return container[n.n]; }
+      typename std::vector<T>::const_reference
+      operator[](Edge n) const { return container[n.n]; }
+
+      ///\warning There is no safety check at all!
+      ///Using operator = between maps attached to different graph may
+      ///cause serious problem.
+      ///\todo Is this really so?
+      ///\todo It can copy between different types.
+      const EdgeMap<T>& operator=(const EdgeMap<T> &m)
+      {
+	container = m.container;
+	return *this;
+      }
+      template<typename TT>
+      const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
+      {
+	std::copy(m.container.begin(), m.container.end(), container.begin());
+	return *this;
+      }
+      
+      void update() {}    //Useless for DynMaps
+      void update(T a) {}  //Useless for DynMaps
+    };
+
+  };
+
+  ///Graph for bidirectional edges.
+
+  ///The purpose of this graph structure is to handle graphs
+  ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
+  ///of oppositely directed edges.
+  ///There is a new edge map type called
+  ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"
+  ///that complements this
+  ///feature by
+  ///storing shared values for the edge pairs. The usual
+  ///\ref GraphSkeleton::EdgeMap "EdgeMap"
+  ///can be used
+  ///as well.
+  ///
+  ///The oppositely directed edge can also be obtained easily
+  ///using \ref opposite.
+  ///\warning It shares the similarity with \ref SmartGraph that
+  ///it is not possible to delete edges or nodes from the graph.
+  //\sa \ref SmartGraph.
+
+  class SymSmartGraph : public SmartGraph
+  {
+  public:
+    template<typename T> class SymEdgeMap;
+    template<typename T> friend class SymEdgeMap;
+
+    SymSmartGraph() : SmartGraph() { }
+    SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
+    ///Adds a pair of oppositely directed edges to the graph.
+    Edge addEdge(Node u, Node v)
+    {
+      Edge e = SmartGraph::addEdge(u,v);
+      SmartGraph::addEdge(v,u);
+      return e;
+    }
+
+    ///The oppositely directed edge.
+
+    ///Returns the oppositely directed
+    ///pair of the edge \c e.
+    Edge opposite(Edge e) const
+    {
+      Edge f;
+      f.idref() = e.idref() - 2*(e.idref()%2) + 1;
+      return f;
+    }
+    
+    ///Common data storage for the edge pairs.
+
+    ///This map makes it possible to store data shared by the oppositely
+    ///directed pairs of edges.
+    template <typename T> class SymEdgeMap : public DynMapBase<Edge>
+    {
+      std::vector<T> container;
+      
+    public:
+      typedef T ValueType;
+      typedef Edge KeyType;
+
+      SymEdgeMap(const SymSmartGraph &_G) :
+	DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
+      {
+	static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.push_back(this);
+      }
+      SymEdgeMap(const SymSmartGraph &_G,const T &t) :
+	DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
+      {
+	G->dyn_edge_maps.push_back(this);
+      }
+
+      SymEdgeMap(const SymEdgeMap<T> &m) :
+ 	DynMapBase<SymEdge>(*m.G), container(m.container)
+      {
+ 	G->dyn_node_maps.push_back(this);
+      }
+
+      //      template<typename TT> friend class SymEdgeMap;
+
+      ///\todo It can copy between different types.
+      ///
+
+      template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :
+	DynMapBase<SymEdge>(*m.G)
+      {
+	G->dyn_node_maps.push_back(this);
+	typename std::vector<TT>::const_iterator i;
+	for(typename std::vector<TT>::const_iterator i=m.container.begin();
+	    i!=m.container.end();
+	    i++)
+	  container.push_back(*i);
+      }
+ 
+      ~SymEdgeMap()
+      {
+	if(G) {
+	  std::vector<DynMapBase<Edge>* >::iterator i;
+	  for(i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.begin();
+	      i!=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.end()
+		&& *i!=this; ++i) ;
+	  //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
+	  //A better way to do that: (Is this really important?)
+	  if(*i==this) {
+	    *i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.back();
+	    static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.pop_back();
+	  }
+	}
+      }
+      
+      void add(const Edge k) 
+      {
+	if(!k.idref()%2&&k.idref()/2>=int(container.size()))
+	  container.resize(k.idref()/2+1);
+      }
+      void erase(const Edge k) { }
+      
+      void set(Edge n, T a) { container[n.idref()/2]=a; }
+      //T get(Edge n) const { return container[n.idref()/2]; }
+      typename std::vector<T>::reference
+      operator[](Edge n) { return container[n.idref()/2]; }
+      typename std::vector<T>::const_reference
+      operator[](Edge n) const { return container[n.idref()/2]; }
+
+      ///\warning There is no safety check at all!
+      ///Using operator = between maps attached to different graph may
+      ///cause serious problem.
+      ///\todo Is this really so?
+      ///\todo It can copy between different types.
+      const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
+      {
+	container = m.container;
+	return *this;
+      }
+      template<typename TT>
+      const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
+      {
+	std::copy(m.container.begin(), m.container.end(), container.begin());
+	return *this;
+      }
+      
+      void update() {}    //Useless for DynMaps
+      void update(T a) {}  //Useless for DynMaps
+
+    };
+
+  };
+  
+  /// @}  
+
+} //namespace hugo
+
+
+
+
+#endif //SMART_GRAPH_H
diff -r d8863141824d -r fb261e3a9a0f src/hugo/time_measure.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/hugo/time_measure.h	Thu May 06 13:21:24 2004 +0000
@@ -0,0 +1,208 @@
+// -*- c++ -*-
+#ifndef HUGO_TIME_MEASURE_H
+#define HUGO_TIME_MEASURE_H
+
+///\ingroup misc
+///\file
+///\brief Tools for measuring cpu usage
+
+#include <sys/time.h>
+#include <sys/times.h>
+#include <fstream>
+#include <iostream>
+#include <unistd.h>
+
+namespace hugo {
+
+  /// \addtogroup misc
+  /// @{
+
+  /// A class to store (cpu)time instances.
+
+  /// This class stores five time values.
+  /// - a real time
+  /// - a user cpu time
+  /// - a system cpu time
+  /// - a user cpu time of children
+  /// - a system cpu time of children
+  ///
+  /// TimeStamp's can be added to or substracted from each other and
+  /// they can be pushed to a stream.
+  ///
+  /// In most cases, perhaps \ref Timer class is what you want to use instead.
+  ///
+  ///\author Alpar Juttner
+
+  class TimeStamp
+  {
+    tms ts;
+    double real_time;
+  
+  public:
+
+    tms &getTms() {return ts;}
+    const tms &getTms() const {return ts;}
+    ///Read the current time values of the process
+    void stamp()
+    {
+      timeval tv;
+      times(&ts);
+      gettimeofday(&tv, 0);real_time=tv.tv_sec+double(tv.tv_usec)/1e6;
+    }
+  
+    /// Constructor initializing with zero
+    TimeStamp()
+    { ts.tms_utime=ts.tms_stime=ts.tms_cutime=ts.tms_cstime=0; real_time=0;}
+    ///Constructor initializing with the current time values of the process
+    TimeStamp(void *) { stamp();}
+  
+    ///
+    TimeStamp &operator+=(const TimeStamp &b)
+    {
+      ts.tms_utime+=b.ts.tms_utime;
+      ts.tms_stime+=b.ts.tms_stime;
+      ts.tms_cutime+=b.ts.tms_cutime;
+      ts.tms_cstime+=b.ts.tms_cstime;
+      real_time+=b.real_time;
+      return *this;
+    }
+    ///
+    TimeStamp operator+(const TimeStamp &b) const
+    {
+      TimeStamp t(*this);
+      return t+=b;
+    }
+    ///
+    TimeStamp &operator-=(const TimeStamp &b)
+    {
+      ts.tms_utime-=b.ts.tms_utime;
+      ts.tms_stime-=b.ts.tms_stime;
+      ts.tms_cutime-=b.ts.tms_cutime;
+      ts.tms_cstime-=b.ts.tms_cstime;
+      real_time-=b.real_time;
+      return *this;
+    }
+    ///
+    TimeStamp operator-(const TimeStamp &b) const
+    {
+      TimeStamp t(*this);
+      return t-=b;
+    }
+
+    ///The time ellapsed since the last call of stamp()
+    TimeStamp ellapsed() const
+    {
+      TimeStamp t(NULL);
+      return t-*this;
+    }
+  
+    friend std::ostream& operator<<(std::ostream& os,const TimeStamp &t);
+  
+    ///Gives back the user time of the process
+    double getUserTime() const
+    {
+      return double(ts.tms_utime)/sysconf(_SC_CLK_TCK);
+    }
+    ///Gives back the system time of the process
+    double getSystemTime() const
+    {
+      return double(ts.tms_stime)/sysconf(_SC_CLK_TCK);
+    }
+    ///Gives back the user time of the process' children
+    double getCUserTime() const
+    {
+      return double(ts.tms_cutime)/sysconf(_SC_CLK_TCK);
+    }
+    ///Gives back the user time of the process' children
+    double getCSystemTime() const
+    {
+      return double(ts.tms_cstime)/sysconf(_SC_CLK_TCK);
+    }
+    ///Gives back the real time of the process
+    double getRealTime() const {return real_time;}
+  };
+
+  ///Class measuring the cpu time and real time usage of the process
+
+  ///Class measuring the cpu time and real time usage of the process.
+  ///It is quite easy-to-use, here is a short example.
+  ///\code
+  ///int main()
+  ///{
+  ///
+  ///  ...
+  ///
+  ///  Timer T();
+  ///  doSomething();
+  ///  cout << T;
+  ///  T.reset();
+  ///  doSomethingElse();
+  ///  cout << T;
+  ///
+  ///  ...
+  ///
+  ///}
+  ///\endcode
+  ///
+  ///\todo This shouldn't be Unix (Linux) specific.
+  ///
+  ///\author Alpar Juttner
+  class Timer
+  {
+    TimeStamp start_time;
+
+    void _reset() {start_time.stamp();}
+  
+  public: 
+    ///Constructor. It starts with zero time counters
+    Timer() {_reset();}
+
+    ///Computes the ellapsed time
+
+    ///This conversion computes the ellapsed time
+    ///since the construction of \c t or since
+    ///the last \c t.reset().
+    operator TimeStamp ()
+    {
+      TimeStamp t;
+      t.stamp();
+      return t-start_time;
+    }
+
+    ///Resets the time counters
+    TimeStamp reset()
+    {
+      TimeStamp t(start_time);
+      _reset();
+      return start_time-t;
+    }
+  };
+
+  ///Prints the time counters
+
+  ///Prints the time counters in the following form:
+  ///
+  /// <tt>u: XX.XXs s: XX.XXs cu: XX.XXs cs: XX.XXs real: XX.XXs</tt>
+  ///
+  /// where the values are the
+  /// \li \c u: user cpu time,
+  /// \li \c s: system cpu time,
+  /// \li \c cu: user cpu time of children,
+  /// \li \c cs: system cpu time of children,
+  /// \li \c real: real time.
+  inline std::ostream& operator<<(std::ostream& os,const TimeStamp &t)
+  {
+    long cls = sysconf(_SC_CLK_TCK);
+    os << "u: " << double(t.getTms().tms_utime)/cls <<
+      "s, s: " << double(t.getTms().tms_stime)/cls <<
+      "s, cu: " << double(t.getTms().tms_cutime)/cls <<
+      "s, cs: " << double(t.getTms().tms_cstime)/cls <<
+      "s, real: " << t.getRealTime() << "s";
+    return os;
+  }
+
+  /// @}  
+
+} //namespace hugo
+
+#endif //HUGO_TIME_MEASURE_H
diff -r d8863141824d -r fb261e3a9a0f src/hugo/unionfind.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/hugo/unionfind.h	Thu May 06 13:21:24 2004 +0000
@@ -0,0 +1,700 @@
+// -*- c++ -*- //
+#ifndef HUGO_UNION_FIND_H
+#define HUGO_UNION_FIND_H
+
+//!\ingroup auxdat
+//!\file
+//!\brief Union-Find data structures.
+
+
+#include <vector>
+#include <list>
+#include <utility>
+#include <algorithm>
+
+#include <invalid.h>
+
+namespace hugo {
+
+  //! \addtogroup 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 compresson.
+   * 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.
+   *
+   * \pre The elements are automatically added only if the map 
+   * given to the constructor was filled with -1's. Otherwise you
+   * need to add all the elements by the \ref insert() method.
+   */
+
+  template <typename T, typename TIntMap>
+  class UnionFind {
+    
+  public:
+    typedef T ElementType;
+    typedef std::pair<int,int> PairType;
+
+  private:
+    std::vector<PairType> data;
+    TIntMap& map;
+
+  public:
+    UnionFind(TIntMap& m) : map(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(T a)
+    {
+      int comp0 = map[a];
+      if (comp0 < 0) {
+	return insert(a);
+      }
+      int comp = comp0;
+      int next;
+      while ( (next = data[comp].first) != comp) {
+	comp = next;
+      }
+      while ( (next = data[comp0].first) != comp) {
+	data[comp0].first = comp;
+	comp0 = next;
+      }
+
+      return comp;
+    }
+
+    /**
+     * \brief Insert a new element into the structure.
+     *
+     * This method inserts a new element into the data structure. 
+     *
+     * It is not required to use this method:
+     * if the map given to the constructor was filled 
+     * with -1's then it is called automatically
+     * on the first \ref find or \ref join.
+     *
+     * The method returns the index of the new component.
+     */
+
+    int insert(T a)
+    {
+      int n = data.size();
+      data.push_back(std::make_pair(n, 1));
+      map.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 elemenent \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(T a, T b)
+    {
+      int ca = find(a);
+      int cb = find(b);
+
+      if ( ca == cb ) 
+	return false;
+
+      if ( data[ca].second > data[cb].second ) {
+	data[cb].first = ca;
+	data[ca].second += data[cb].second;
+      }
+      else {
+	data[ca].first = cb;
+	data[cb].second += data[ca].second;
+      }
+      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(T a)
+    {
+      int ca = find(a);
+      return data[ca].second;
+    }
+
+  };
+
+
+
+
+  /*******************************************************/
+
+
+#ifdef DEVELOPMENT_DOCS
+
+  /**
+   * \brief The auxiliary class for the \ref UnionFindEnum class.
+   *
+   * In the \ref UnionFindEnum class all components are represented as
+   * a std::list. 
+   * Items of these lists are UnionFindEnumItem structures.
+   *
+   * The class has four fields:
+   *  - T me - the actual element 
+   *  - IIter parent - the parent of the element in the union-find structure
+   *  - int size - the size of the component of the element. 
+   *            Only valid if the element
+   *            is the leader of the component.
+   *  - CIter my_class - pointer into the list of components 
+   *            pointing to the component of the element.
+   *            Only valid if the element is the leader of the component.
+   */
+
+#endif
+
+  template <typename T>
+  struct UnionFindEnumItem {
+
+    typedef std::list<UnionFindEnumItem> ItemList;
+    typedef std::list<ItemList> ClassList;
+    typedef typename ItemList::iterator IIter;
+    typedef typename ClassList::iterator CIter;
+
+    T me;
+    IIter parent;
+    int size;
+    CIter my_class;
+
+    UnionFindEnumItem() {}
+    UnionFindEnumItem(const T &_me, CIter _my_class): 
+      me(_me), size(1), my_class(_my_class) {}
+  };
+
+
+  /**
+   * \brief A \e Union-Find data structure implementation which
+   * is able to enumerate the components.
+   *
+   * The class implements an \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 compresson.
+   *
+   * \pre You
+   * need to add all the elements by the \ref insert() method.
+   */
+
+
+  template <typename T, template <typename Item> class Map>
+  class UnionFindEnum {
+
+    typedef std::list<UnionFindEnumItem<T> > ItemList;
+    typedef std::list<ItemList> ClassList;
+    typedef typename ItemList::iterator IIter;
+    typedef typename ItemList::const_iterator IcIter;
+    typedef typename ClassList::iterator CIter;
+    typedef typename ClassList::const_iterator CcIter;
+
+  public:
+    typedef T ElementType;
+    typedef UnionFindEnumItem<T> ItemType;
+    typedef Map< IIter > MapType;
+
+  private:
+    MapType& m;
+    ClassList classes;
+
+    IIter _find(IIter a) const {
+      IIter comp = a;
+      IIter next;
+      while( (next = comp->parent) != comp ) {
+	comp = next;
+      }
+
+      IIter comp1 = a;
+      while( (next = comp1->parent) != comp ) {
+	comp1->parent = comp->parent;
+	comp1 = next;
+      }
+      return comp;
+    }
+
+  public:
+    UnionFindEnum(MapType& _m) : m(_m) {}
+
+
+    /**
+     * \brief Insert the given element into a new component.
+     *
+     * This method creates a new component consisting only of the
+     * given element.
+     */
+
+    void insert(const T &a)
+    {
+
+
+      classes.push_back(ItemList());
+      CIter aclass = classes.end();
+      --aclass;
+
+      ItemList &alist = *aclass;
+      alist.push_back(ItemType(a, aclass));
+      IIter ai = alist.begin();
+
+      ai->parent = ai;
+      m.set(a, ai);
+
+    }
+
+    /**
+     * \brief Insert the given element into the component of the others.
+     *
+     * This methods insert the element \e a into the component of the
+     * element \e comp. 
+     */
+
+    void insert(const T &a, const T &comp) {
+      
+      IIter clit = _find(m[comp]);
+      ItemList &c = *clit->my_class;
+      c.push_back(ItemType(a,0));
+      IIter ai = c.end();
+      --ai;
+      ai->parent = clit;
+      m.set(a, ai);
+      ++clit->size;
+    }
+
+
+    /**
+     * \brief Find the leader of the component of the given element.
+     *
+     * The method returns the leader of the component of the given element.
+     */
+
+    T find(const T &a) const {
+      return _find(m[a])->me;
+    }
+
+
+    /**
+     * \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 elemenent \e a and component of
+     * element \e b. If \e a and \e b are in the same component then
+     * returns false else returns true.
+     */
+
+    bool join(T a, T b) {
+
+      IIter ca = _find(m[a]);
+      IIter cb = _find(m[b]);
+
+      if ( ca == cb ) {
+	return false;
+      }
+
+      if ( ca->size > cb->size ) {
+
+	cb->parent = ca->parent;
+	ca->size += cb->size;
+	
+	ItemList &alist = *ca->my_class;
+	alist.splice(alist.end(),*cb->my_class);
+
+	classes.erase(cb->my_class);
+	cb->my_class = 0;
+      }
+      else {
+
+	ca->parent = cb->parent;
+	cb->size += ca->size;
+	
+	ItemList &blist = *cb->my_class;
+	blist.splice(blist.end(),*ca->my_class);
+
+	classes.erase(ca->my_class);
+	ca->my_class = 0;
+      }
+
+      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 T &a) const {
+      return _find(m[a])->size;
+    }
+
+
+    /**
+     * \brief Split up the component of the element. 
+     *
+     * Splitting the component of the element into sigleton
+     * components (component of size one).
+     */
+
+    void split(const T &a) {
+
+      IIter ca = _find(m[a]);
+ 
+      if ( ca->size == 1 )
+	return;
+      
+      CIter aclass = ca->my_class;
+
+      for(IIter curr = ca; ++curr != aclass->end(); curr=ca) {
+	classes.push_back(ItemList());
+	CIter nl = --classes.end();
+	nl->splice(nl->end(), *aclass, curr);
+
+	curr->size=1;
+	curr->parent=curr;
+	curr->my_class = nl;
+      }
+
+      ca->size=1;
+      return;
+    }
+
+
+    /**
+     * \brief Set the given element to the leader element of its component.
+     *
+     * Set the given element to the leader element of its component.
+     */
+
+    void makeRep(const T &a) {
+
+      IIter ia = m[a];
+      IIter la = _find(ia);
+      if (la == ia) return;
+
+      ia->my_class = la->my_class;
+      la->my_class = 0;
+
+      ia->size = la->size;
+
+      CIter l = ia->my_class;
+      l->splice(l->begin(),*l,ia);
+
+      ia->parent = ia;
+      la->parent = ia;
+    }
+
+    /**
+     * \brief Move the given element to an other component.
+     *
+     * This method moves the element \e a from its component
+     * to the component of \e comp.
+     * If \e a and \e comp are in the same component then
+     * it returns false otherwise it returns true.
+     */
+
+    bool move(const T &a, const T &comp) {
+
+      IIter ai = m[a];
+      IIter lai = _find(ai);
+      IIter clit = _find(m[comp]);
+
+      if (lai == clit)
+	return false;
+
+      ItemList &c = *clit->my_class;
+
+      bool is_leader = (lai == ai);
+      bool singleton = false;
+
+      if (is_leader) {
+	++lai;
+      }
+
+      c.splice(c.end(), *lai->my_class, ai);
+
+      if (is_leader) {
+	if (ai->size == 1) {
+	  classes.erase(ai->my_class);
+	  singleton = true;
+	}
+	else {
+	  lai->size = ai->size; 
+	  lai->my_class = ai->my_class;	
+	}
+      }
+      if (!singleton) {
+	for (IIter i = lai; i != lai->my_class->end(); ++i)
+	  i->parent = lai;
+	--lai->size;
+      }
+
+      ai->parent = clit;
+      ai->my_class = 0;
+      ++clit->size;
+
+      return true;
+    }
+
+
+    /**
+     * \brief Remove the given element from the structure.
+     *
+     * Remove 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.
+     */
+    void erase(const T &a) {
+
+      IIter ma = m[a];
+      if (ma == 0) return;
+
+      IIter la = _find(ma);
+      if (la == ma) {
+	if (ma -> size == 1){
+	  classes.erase(ma->my_class);
+	  m.set(a,0);
+	  return;
+	}
+	++la;
+	la->size = ma->size; 
+	la->my_class = ma->my_class;	
+      }
+
+      for (IIter i = la; i != la->my_class->end(); ++i) {
+	i->parent = la;
+      }
+
+      la->size--;
+      la->my_class->erase(ma);
+      m.set(a,0);
+    }
+
+    /**
+     * \brief Removes the component of the given element from the structure.
+     *
+     * Removes the component of the given element from the structure.
+     */
+
+    void eraseClass(const T &a) {
+      IIter ma = m[a];
+      if (ma == 0) return;
+#     ifdef DEBUG
+      CIter c = _find(ma)->my_class;
+      for (IIter i=c->begin(); i!=c->end(); ++i)
+	m.set(i->me, 0);
+#     endif
+      classes.erase(_find(ma)->my_class);
+    }
+
+
+    class ClassIt {
+      friend class UnionFindEnum;
+
+      CcIter i;
+    public:
+      ClassIt(Invalid): i(0) {}
+      ClassIt() {}
+      
+      operator const T& () const { 
+	ItemList const &ll = *i;
+	return (ll.begin())->me; }
+      bool operator == (ClassIt it) const {
+	return (i == it.i);
+      }
+      bool operator != (ClassIt it) const {
+	return (i != it.i);
+      }
+      bool operator < (ClassIt it) const {
+	return (i < it.i);
+      }
+
+      bool valid() const { return i != 0; }
+    private:
+      void first(const ClassList &l) { i = l.begin(); validate(l); }
+      void next(const ClassList &l) {
+	++i; 
+	validate(l);
+      }
+      void validate(const ClassList &l) {
+	if ( i == l.end() ) 
+	  i = 0;
+      }
+    };
+
+    /**
+     * \brief Sets the iterator to point to the first component.
+     * 
+     * Sets the iterator to point to the first component.
+     *
+     * With the \ref first, \ref valid and \ref next methods you can
+     * iterate through the components. For example:
+     * \code
+     * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
+     * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
+     * UnionFindEnum<Graph::Node, Graph::NodeMap>::ClassIt iter;
+     *  for (U.first(iter); U.valid(iter); U.next(iter)) {
+     *    // iter is convertible to Graph::Node
+     *    cout << iter << endl;
+     *  }
+     * \endcode
+     */
+
+    ClassIt& first(ClassIt& it) const {
+      it.first(classes);
+      return it;
+    }
+
+    /**
+     * \brief Returns whether the iterator is valid.
+     *
+     * Returns whether the iterator is valid.
+     *
+     * With the \ref first, \ref valid and \ref next methods you can
+     * iterate through the components. See the example here: \ref first.
+     */
+
+    bool valid(ClassIt const &it) const {
+      return it.valid(); 
+    }
+
+    /**
+     * \brief Steps the iterator to the next component. 
+     *
+     * Steps the iterator to the next component.
+     *
+     * With the \ref first, \ref valid and \ref next methods you can
+     * iterate through the components. See the example here: \ref first.
+     */
+
+    ClassIt& next(ClassIt& it) const {
+      it.next(classes);
+      return it;
+    }
+
+
+    class ItemIt {
+      friend class UnionFindEnum;
+
+      IcIter i;
+      const ItemList *l;
+    public:
+      ItemIt(Invalid): i(0) {}
+      ItemIt() {}
+      
+      operator const T& () const { return i->me; }
+      bool operator == (ItemIt it) const {
+	return (i == it.i);
+      }
+      bool operator != (ItemIt it) const {
+	return (i != it.i);
+      }
+      bool operator < (ItemIt it) const {
+	return (i < it.i);
+      }
+
+      bool valid() const { return i != 0; }
+    private:
+      void first(const ItemList &il) { l=&il; i = l->begin(); validate(); }
+      void next() {
+	++i; 
+	validate();
+      }
+      void validate() {
+	if ( i == l->end() ) 
+	  i = 0;
+      }
+    };
+
+
+
+    /**
+     * \brief Sets the iterator to point to the first element of the component.
+     * 
+     * \anchor first2 
+     * Sets the iterator to point to the first element of the component.
+     *
+     * With the \ref first2 "first", \ref valid2 "valid" 
+     * and \ref next2 "next" methods you can
+     * iterate through the elements of a component. For example
+     * (iterating through the component of the node \e node):
+     * \code
+     * Graph::Node node = ...;
+     * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
+     * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
+     * UnionFindEnum<Graph::Node, Graph::NodeMap>::ItemIt iiter;
+     *   for (U.first(iiter, node); U.valid(iiter); U.next(iiter)) {
+     *     // iiter is convertible to Graph::Node
+     *     cout << iiter << endl;
+     *   }
+     * \endcode
+     */
+    
+    ItemIt& first(ItemIt& it, const T& a) const {
+      it.first( * _find(m[a])->my_class );
+      return it;
+    }
+
+    /**
+     * \brief Returns whether the iterator is valid.
+     *
+     * \anchor valid2
+     * Returns whether the iterator is valid.
+     *
+     * With the \ref first2 "first", \ref valid2 "valid" 
+     * and \ref next2 "next" methods you can
+     * iterate through the elements of a component.
+     * See the example here: \ref first2 "first".
+     */
+
+    bool valid(ItemIt const &it) const {
+      return it.valid(); 
+    }
+
+    /**
+     * \brief Steps the iterator to the next component. 
+     *
+     * \anchor next2
+     * Steps the iterator to the next component.
+     *
+     * With the \ref first2 "first", \ref valid2 "valid" 
+     * and \ref next2 "next" methods you can
+     * iterate through the elements of a component.
+     * See the example here: \ref first2 "first".
+     */
+
+    ItemIt& next(ItemIt& it) const {
+      it.next();
+      return it;
+    }
+    
+  };
+
+
+  //! @}
+
+} //namespace hugo
+
+#endif //HUGO_UNION_FIND_H
diff -r d8863141824d -r fb261e3a9a0f src/hugo/xy.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/hugo/xy.h	Thu May 06 13:21:24 2004 +0000
@@ -0,0 +1,227 @@
+// -*- c++ -*-
+#ifndef HUGO_XY_H
+#define HUGO_XY_H
+
+#include <iostream>
+
+///\ingroup misc
+///\file
+///\brief A simple two dimensional vector and a bounding box implementation 
+///
+/// The class \ref hugo::xy "xy" implements
+///a two dimensional vector with the usual
+/// operations.
+///
+/// The class \ref hugo::BoundingBox "BoundingBox" can be used to determine
+/// the rectangular bounding box a set of \ref hugo::xy "xy"'s.
+///
+///\author Attila Bernath
+
+
+namespace hugo {
+
+  /// \addtogroup misc
+  /// @{
+
+  /// A two dimensional vector (plainvector) implementation
+
+  /// A two dimensional vector (plainvector) implementation
+  ///with the usual vector
+  /// operators.
+  ///
+  ///\author Attila Bernath
+  template<typename T>
+    class xy {
+
+    public:
+
+      T x,y;     
+      
+      ///Default constructor: both coordinates become 0
+      xy() : x(0), y(0) {}
+
+      ///Constructing the instance from coordinates
+      xy(T a, T b) : x(a), y(b) { }
+
+
+      ///Gives back the square of the norm of the vector
+      T normSquare(){
+	return x*x+y*y;
+      };
+  
+      ///Increments the left hand side by u
+      xy<T>& operator +=(const xy<T>& u){
+	x += u.x;
+	y += u.y;
+	return *this;
+      };
+  
+      ///Decrements the left hand side by u
+      xy<T>& operator -=(const xy<T>& u){
+	x -= u.x;
+	y -= u.y;
+	return *this;
+      };
+
+      ///Multiplying the left hand side with a scalar
+      xy<T>& operator *=(const T &u){
+	x *= u;
+	y *= u;
+	return *this;
+      };
+
+      ///Dividing the left hand side by a scalar
+      xy<T>& operator /=(const T &u){
+	x /= u;
+	y /= u;
+	return *this;
+      };
+  
+      ///Returns the scalar product of two vectors
+      T operator *(const xy<T>& u){
+	return x*u.x+y*u.y;
+      };
+  
+      ///Returns the sum of two vectors
+      xy<T> operator+(const xy<T> &u) const {
+	xy<T> b=*this;
+	return b+=u;
+      };
+
+      ///Returns the difference of two vectors
+      xy<T> operator-(const xy<T> &u) const {
+	xy<T> b=*this;
+	return b-=u;
+      };
+
+      ///Returns a vector multiplied by a scalar
+      xy<T> operator*(const T &u) const {
+	xy<T> b=*this;
+	return b*=u;
+      };
+
+      ///Returns a vector divided by a scalar
+      xy<T> operator/(const T &u) const {
+	xy<T> b=*this;
+	return b/=u;
+      };
+
+      ///Testing equality
+      bool operator==(const xy<T> &u){
+	return (x==u.x) && (y==u.y);
+      };
+
+      ///Testing inequality
+      bool operator!=(xy u){
+	return  (x!=u.x) || (y!=u.y);
+      };
+
+    };
+
+  ///Reading a plainvector from a stream
+  template<typename T>
+  inline
+  std::istream& operator>>(std::istream &is, xy<T> &z)
+  {
+
+    is >> z.x >> z.y;
+    return is;
+  }
+
+  ///Outputting a plainvector to a stream
+  template<typename T>
+  inline
+  std::ostream& operator<<(std::ostream &os, xy<T> z)
+  {
+    os << "(" << z.x << ", " << z.y << ")";
+    return os;
+  }
+
+
+  /// A class to calculate or store the bounding box of plainvectors.
+
+  /// A class to calculate or store the bounding box of plainvectors.
+  ///
+  ///\author Attila Bernath
+  template<typename T>
+    class BoundingBox {
+      xy<T> bottom_left, top_right;
+      bool _empty;
+    public:
+      
+      ///Default constructor: an empty bounding box
+      BoundingBox() { _empty = true; }
+
+      ///Constructing the instance from one point
+      BoundingBox(xy<T> a) { bottom_left=top_right=a; _empty = false; }
+
+      ///Is there any point added
+      bool empty() const {
+	return _empty;
+      }
+
+      ///Gives back the bottom left corner (if the bounding box is empty, then the return value is not defined) 
+      xy<T> bottomLeft() const {
+	return bottom_left;
+      };
+
+      ///Gives back the top right corner (if the bounding box is empty, then the return value is not defined) 
+      xy<T> topRight() const {
+	return top_right;
+      };
+
+      ///Checks whether a point is inside a bounding box
+      bool inside(const xy<T>& u){
+	if (_empty)
+	  return false;
+	else{
+	  return ((u.x-bottom_left.x)*(top_right.x-u.x) >= 0 &&
+		  (u.y-bottom_left.y)*(top_right.y-u.y) >= 0 );
+	}
+      }
+  
+      ///Increments a bounding box with a point
+      BoundingBox& operator +=(const xy<T>& u){
+	if (_empty){
+	  bottom_left=top_right=u;
+	  _empty = false;
+	}
+	else{
+	  if (bottom_left.x > u.x) bottom_left.x = u.x;
+	  if (bottom_left.y > u.y) bottom_left.y = u.y;
+	  if (top_right.x < u.x) top_right.x = u.x;
+	  if (top_right.y < u.y) top_right.y = u.y;
+	}
+	return *this;
+      };
+  
+      ///Sums a bounding box and a point
+      BoundingBox operator +(const xy<T>& u){
+	BoundingBox b = *this;
+	return b += u;
+      };
+
+      ///Increments a bounding box with an other bounding box
+      BoundingBox& operator +=(const BoundingBox &u){
+	if ( !u.empty() ){
+	  *this += u.bottomLeft();
+	  *this += u.topRight();
+	}
+	return *this;
+      };
+  
+      ///Sums two bounding boxes
+      BoundingBox operator +(const BoundingBox& u){
+	BoundingBox b = *this;
+	return b += u;
+      };
+
+    };//class Boundingbox
+
+
+  /// @}
+
+
+} //namespace hugo
+
+#endif //HUGO_XY_H
diff -r d8863141824d -r fb261e3a9a0f src/include/bin_heap.h
--- a/src/include/bin_heap.h	Thu May 06 09:26:23 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,246 +0,0 @@
-// -*- C++ -*- //
-
-/* FIXME: Copyright ... 
- *
- * This implementation is heavily based on STL's heap functions and
- * the similar class by Alpar Juttner in IKTA...
- */
-
-/******
- *
- * BinHeap<ItemType, PrioType, ItemIntMap, [PrioCompare]>
- *
- * Ez az osztaly item-prioritas parok tarolasara alkalmas binaris kupacot
- * valosit meg.
- * A kupacban legfolul mindig az a par talalhato, amiben a prioritas a
- * legkisebb. (Gondolj a Dijkstra pont-tavolsag kupacara; igazabol ahhoz
- * lett keszitve...)
- *
- * Megjegyzes: a kupacos temakorokben a prioritast kulcsnak szoktak nevezni,
- * de mivel ez zavaro tud lenni a property-map-es kulcs-ertek szohasznalata
- * miatt, megprobaltunk valami semleges elnevezeseket kitalalni.
- *
- * A hasznalatahoz szukseg van egy irhato/olvashato property_map-re, ami
- * az itemekhez egy int-et tud tarolni (ezzel tudom megkeresni az illeto
- * elemet a kupacban a csokkentes es hasonlo muveletekhez).
- * A map-re csak referenciat tarol, ugy hogy a kupac elete folyan a map-nek
- * is elnie kell. (???)
- *
- * Ketfele modon hasznalhato:
- * Lusta mod:
- * set(Item, Prio) metodussal pakolunk a kupacba,
- * aztan o majd eldonti, hogy ez az elem mar benne van-e es ha igen, akkor
- * csokkentettunk-e rajta, vagy noveltunk.
- * Ehhez nagyon fontos, hogy az atadott property map inicializalva legyen
- * minden szobajovo kulcs ertekre, -1 -es ertekkel!
- * Es ilyen esetben a kulcsokrol lekerdezheto az allapotuk a state metodussal:
- * (nem jart meg a kupacban PRE_HEAP=-1, epp a kupacban van IN_HEAP=0,
- *  mar kikerult a kupacbol POST_HEAP=-2).
- * Szoval ebben a modban a kupac nagyjabol hasznalhato property_map-kent, csak
- * meg meg tudja mondani a "legkisebb" prioritasu elemet. De csak nagyjabol,
- * hiszen a kupacbol kikerult elemeknek elvesz az ertekuk...
- *
- * Kozvetlen mod:
- * push(Item, Prio) metodussal belerakunk a kupacba (ha az illeto kulcs mar
- * benn volt, akkor gaz).
- * increase/decrease(Item i, Prio new_prio) metodusokkal lehet
- * novelni/csokkenteni az illeto elemhez tartozo prioritast. (Ha nem volt
- * megbenne a kupacban az illeto elem, vagy nem abba az iranyba valtoztattad
- * az erteket, amerre mondtad -- gaz).
- *
- * Termeszetesen a fenti ket modot ertelemszeruen lehet keverni.
- * Ja es mindig nagyon gaz, ha belepiszkalsz a map-be, amit a kupac
- * hasznal. :-))
- *
- *
- * Bocs, most faradt vagyok, majd egyszer leforditom. (Misi)
- *
- */
-
-
-#ifndef BIN_HEAP_HH
-#define BIN_HEAP_HH
-
-///\ingroup auxdat
-///\file
-///\brief Binary Heap implementation.
-
-#include <vector>
-#include <utility>
-#include <functional>
-
-namespace hugo {
-
-  /// \addtogroup auxdat
-  /// @{
-
-   /// A Binary Heap implementation.
-  template <typename Item, typename Prio, typename ItemIntMap,
-	    typename Compare = std::less<Prio> >
-  class BinHeap {
-
-  public:
-    typedef Item                             ItemType;
-    // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...
-    typedef Prio                             PrioType;
-    typedef std::pair<ItemType,PrioType>     PairType;
-    typedef ItemIntMap                       ItemIntMapType;
-    typedef Compare                          PrioCompare;
-
-    /**
-     * Each Item element have a state associated to it. It may be "in heap",
-     * "pre heap" or "post heap". The later two are indifferent from the
-     * heap's point of view, but may be useful to the user.
-     *
-     * The ItemIntMap _should_ be initialized in such way, that it maps
-     * PRE_HEAP (-1) to any element to be put in the heap...
-     */
-    ///\todo it is used nowhere
-    ///
-    enum state_enum {
-      IN_HEAP = 0,
-      PRE_HEAP = -1,
-      POST_HEAP = -2
-    };
-
-  private:
-    std::vector<PairType> data;
-    Compare comp;
-    // FIXME: jo ez igy???
-    ItemIntMap &iim;
-
-  public:
-    BinHeap(ItemIntMap &_iim) : iim(_iim) {}
-    BinHeap(ItemIntMap &_iim, const Compare &_comp) : comp(_comp), iim(_iim) {}
-
-
-    int size() const { return data.size(); }
-    bool empty() const { return data.empty(); }
-
-  private:
-    static int parent(int i) { return (i-1)/2; }
-    static int second_child(int i) { return 2*i+2; }
-    bool less(const PairType &p1, const PairType &p2) const {
-      return comp(p1.second, p2.second);
-    }
-
-    int bubble_up(int hole, PairType p);
-    int bubble_down(int hole, PairType p, int length);
-
-    void move(const PairType &p, int i) {
-      data[i] = p;
-      iim.set(p.first, i);
-    }
-
-    void rmidx(int h) {
-      int n = data.size()-1;
-      if( h>=0 && h<=n ) {
-	iim.set(data[h].first, POST_HEAP);
-	if ( h<n ) {
-	  bubble_down(h, data[n], n);
-	}
-	data.pop_back();
-      }
-    }
-
-  public:
-    void push(const PairType &p) {
-      int n = data.size();
-      data.resize(n+1);
-      bubble_up(n, p);
-    }
-    void push(const Item &i, const Prio &p) { push(PairType(i,p)); }
-
-    Item top() const {
-      return data[0].first;
-    }
-    /// Returns the prio of the top element of the heap.
-    Prio prio() const {
-      return data[0].second;
-    }
-
-    void pop() {
-      rmidx(0);
-    }
-
-    void erase(const Item &i) {
-      rmidx(iim[i]);
-    }
-
-    Prio operator[](const Item &i) const {
-      int idx = iim[i];
-      return data[idx].second;
-    }
-
-    void set(const Item &i, const Prio &p) {
-      int idx = iim[i];
-      if( idx < 0 ) {
-	push(i,p);
-      }
-      else if( comp(p, data[idx].second) ) {
-	bubble_up(idx, PairType(i,p));
-      }
-      else {
-	bubble_down(idx, PairType(i,p), data.size());
-      }
-    }
-
-    void decrease(const Item &i, const Prio &p) {
-      int idx = iim[i];
-      bubble_up(idx, PairType(i,p));
-    }
-    void increase(const Item &i, const Prio &p) {
-      int idx = iim[i];
-      bubble_down(idx, PairType(i,p), data.size());
-    }
-
-    state_enum state(const Item &i) const {
-      int s = iim[i];
-      if( s>=0 )
-	s=0;
-      return state_enum(s);
-    }
-
-  }; // class BinHeap
-
-  
-  template <typename K, typename V, typename M, typename C>
-  int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) {
-    int par = parent(hole);
-    while( hole>0 && less(p,data[par]) ) {
-      move(data[par],hole);
-      hole = par;
-      par = parent(hole);
-    }
-    move(p, hole);
-    return hole;
-  }
-
-  template <typename K, typename V, typename M, typename C>
-  int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) {
-    int child = second_child(hole);
-    while(child < length) {
-      if( less(data[child-1], data[child]) ) {
-	--child;
-      }
-      if( !less(data[child], p) )
-	goto ok;
-      move(data[child], hole);
-      hole = child;
-      child = second_child(hole);
-    }
-    child--;
-    if( child<length && less(data[child], p) ) {
-      move(data[child], hole);
-      hole=child;
-    }
-  ok:
-    move(p, hole);
-    return hole;
-  }
-
-  ///@}
-
-} // namespace hugo
-
-#endif // BIN_HEAP_HH
diff -r d8863141824d -r fb261e3a9a0f src/include/dijkstra.h
--- a/src/include/dijkstra.h	Thu May 06 09:26:23 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,208 +0,0 @@
-// -*- C++ -*-
-#ifndef HUGO_DIJKSTRA_H
-#define HUGO_DIJKSTRA_H
-
-///\ingroup galgs
-///\file
-///\brief Dijkstra algorithm.
-
-#include <bin_heap.h>
-#include <invalid.h>
-
-namespace hugo {
-
-/// \addtogroup galgs
-/// @{
-
-  ///%Dijkstra algorithm class.
-
-  ///This class provides an efficient implementation of %Dijkstra algorithm.
-  ///The edge lengths are passed to the algorithm using a
-  ///\ref ReadMapSkeleton "readable map",
-  ///so it is easy to change it to any kind of length.
-  ///
-  ///The type of the length is determined by the \c ValueType of the length map.
-  ///
-  ///It is also possible to change the underlying priority heap.
-  ///
-  ///\param Graph The graph type the algorithm runs on.
-  ///\param LengthMap This read-only
-  ///EdgeMap
-  ///determines the
-  ///lengths of the edges. It is read once for each edge, so the map
-  ///may involve in relatively time consuming process to compute the edge
-  ///length if it is necessary. The default map type is
-  ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
-  ///\param Heap The heap type used by the %Dijkstra
-  ///algorithm. The default
-  ///is using \ref BinHeap "binary heap".
-  ///
-  ///\author Jacint Szabo
-#ifdef DOXYGEN
-  template <typename Graph,
-	    typename LengthMap,
-	    typename Heap>
-#else
-  template <typename Graph,
-	    typename LengthMap=typename Graph::template EdgeMap<int>,
-	    template <class,class,class,class> class Heap = BinHeap >
-#endif
-  class Dijkstra{
-  public:
-    typedef typename Graph::Node Node;
-    typedef typename Graph::NodeIt NodeIt;
-    typedef typename Graph::Edge Edge;
-    typedef typename Graph::OutEdgeIt OutEdgeIt;
-    
-    typedef typename LengthMap::ValueType ValueType;
-    typedef typename Graph::template NodeMap<Edge> PredMap;
-    typedef typename Graph::template NodeMap<Node> PredNodeMap;
-    typedef typename Graph::template NodeMap<ValueType> DistMap;
-
-  private:
-    const Graph& G;
-    const LengthMap& length;
-    PredMap predecessor;
-    PredNodeMap pred_node;
-    DistMap distance;
-    
-  public :
-    
-    Dijkstra(const Graph& _G, const LengthMap& _length) :
-      G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { }
-    
-    void run(Node s);
-    
-    ///The distance of a node from the root.
-
-    ///Returns the distance of a node from the root.
-    ///\pre \ref run() must be called before using this function.
-    ///\warning If node \c v in unreachable from the root the return value
-    ///of this funcion is undefined.
-    ValueType dist(Node v) const { return distance[v]; }
-
-    ///Returns the previous edge of the shortest path tree.
-
-    ///For a node \c v it returns the previous edge of the shortest path tree,
-    ///i.e. it returns the last edge from a shortest path from the root to \c
-    ///v. It is INVALID if \c v is unreachable from the root or if \c v=s. The
-    ///shortest path tree used here is equal to the shortest path tree used in
-    ///\ref predNode(Node v).  \pre \ref run() must be called before using
-    ///this function.
-    Edge pred(Node v) const { return predecessor[v]; }
-
-    ///Returns the previous node of the shortest path tree.
-
-    ///For a node \c v it returns the previous node of the shortest path tree,
-    ///i.e. it returns the last but one node from a shortest path from the
-    ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
-    ///\c v=s. The shortest path tree used here is equal to the shortest path
-    ///tree used in \ref pred(Node v).  \pre \ref run() must be called before
-    ///using this function.
-    Node predNode(Node v) const { return pred_node[v]; }
-    
-    ///Returns a reference to the NodeMap of distances.
-
-    ///Returns a reference to the NodeMap of distances. \pre \ref run() must
-    ///be called before using this function.
-    const DistMap &distMap() const { return distance;}
- 
-    ///Returns a reference to the shortest path tree map.
-
-    ///Returns a reference to the NodeMap of the edges of the
-    ///shortest path tree.
-    ///\pre \ref run() must be called before using this function.
-    const PredMap &predMap() const { return predecessor;}
- 
-    ///Returns a reference to the map of nodes of shortest paths.
-
-    ///Returns a reference to the NodeMap of the last but one nodes of the
-    ///shortest path tree.
-    ///\pre \ref run() must be called before using this function.
-    const PredNodeMap &predNodeMap() const { return pred_node;}
-
-    ///Checks if a node is reachable from the root.
-
-    ///Returns \c true if \c v is reachable from the root.
-    ///\warning the root node is reported to be unreached!
-    ///\todo Is this what we want?
-    ///\pre \ref run() must be called before using this function.
-    ///
-    bool reached(Node v) { return G.valid(predecessor[v]); }
-    
-  };
-  
-
-  // **********************************************************************
-  //  IMPLEMENTATIONS
-  // **********************************************************************
-
-  ///Runs %Dijkstra algorithm from node the root.
-
-  ///This method runs the %Dijkstra algorithm from a root node \c s
-  ///in order to
-  ///compute the
-  ///shortest path to each node. The algorithm computes
-  ///- The shortest path tree.
-  ///- The distance of each node from the root.
-  template <typename Graph, typename LengthMap,
-	    template<class,class,class,class> class Heap >
-  void Dijkstra<Graph,LengthMap,Heap>::run(Node s) {
-    
-    NodeIt u;
-    for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
-      predecessor.set(u,INVALID);
-      pred_node.set(u,INVALID);
-    }
-    
-    typename Graph::template NodeMap<int> heap_map(G,-1);
-    
-    typedef Heap<Node, ValueType, typename Graph::template NodeMap<int>,
-      std::less<ValueType> > 
-      HeapType;
-    
-    HeapType heap(heap_map);
-    
-    heap.push(s,0); 
-    
-      while ( !heap.empty() ) {
-	
-	Node v=heap.top(); 
-	ValueType oldvalue=heap[v];
-	heap.pop();
-	distance.set(v, oldvalue);
-	
-	{ //FIXME this bracket is for e to be local
-	  OutEdgeIt e;
-	for(G.first(e, v);
-	    G.valid(e); G.next(e)) {
-	  Node w=G.bNode(e); 
-	  
-	  switch(heap.state(w)) {
-	  case HeapType::PRE_HEAP:
-	    heap.push(w,oldvalue+length[e]); 
-	    predecessor.set(w,e);
-	    pred_node.set(w,v);
-	    break;
-	  case HeapType::IN_HEAP:
-	    if ( oldvalue+length[e] < heap[w] ) {
-	      heap.decrease(w, oldvalue+length[e]); 
-	      predecessor.set(w,e);
-	      pred_node.set(w,v);
-	    }
-	    break;
-	  case HeapType::POST_HEAP:
-	    break;
-	  }
-	}
-      } //FIXME tis bracket
-      }
-  }
-
-/// @}
-  
-} //END OF NAMESPACE HUGO
-
-#endif
-
-
diff -r d8863141824d -r fb261e3a9a0f src/include/dimacs.h
--- a/src/include/dimacs.h	Thu May 06 09:26:23 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,206 +0,0 @@
-// -*- c++ -*-
-#ifndef HUGO_DIMACS_H
-#define HUGO_DIMACS_H
-
-#include <iostream>
-#include <string>
-#include <vector>
-#include <maps.h>
-
-/// \file
-/// \brief Dimacs file format reader.
-
-namespace hugo {
-
-  /// Dimacs flow file format reader function.
-
-  /// This function reads a flow instance from dimacs flow format.
-  /// At the beginning \c g is cleared by \c g.clear().
-  /// If the data coming from \c is is a max flow problem instance, then 
-  /// \c s and \c t will be respectively the source and target nodes 
-  /// and \c capacity will contain the edge capacities.
-  /// If the data is a shortest path problem instance then \c s will be the 
-  /// source node and \c capacity will contain the edge lengths.
-  ///
-  ///\author Marton Makai
-  template<typename Graph, typename CapacityMap>
-  void readDimacsMaxFlow(std::istream& is, Graph &g, 
-			 typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) {
-    g.clear();
-    int cap;
-    char d;
-    std::string problem;
-    char c;
-    int i, j;
-    std::string str;
-    int n, m; 
-    typename Graph::Edge e;
-    std::vector<typename Graph::Node> nodes;
-    while (is>>c) {
-      switch (c) {
-      case 'c': //comment
-	getline(is, str);
-	break;
-      case 'p': //problem definition
-	is >> problem >> n >> m;
-	getline(is, str);
-	nodes.resize(n+1);
-	for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
-	break;
-      case 'n': //node definition
-	if (problem=="sp") { //shortest path problem
-	  is >> i;
-	  getline(is, str);
-	  s=nodes[i];
-	}
-	if (problem=="max") { //max flow problem
-	  is >> i >> d;
-	  getline(is, str);
-	  if (d=='s') s=nodes[i];
-	  if (d=='t') t=nodes[i];
-	}
-	break;
-      case 'a':
-	is >> i >> j >> cap;
-	getline(is, str);
-	e=g.addEdge(nodes[i], nodes[j]);
-	capacity.update();
-	capacity.set(e, cap);
-	break;
-      }
-    }
-  }
-
-  /// matching problem
-  template<typename Graph>
-  void readDimacs(std::istream& is, Graph &g) {
-    typename Graph::Node u;
-    NullMap<typename Graph::Edge, int> n;
-    readDimacs(is, g, n, u, u, n);
-    std::cout<<"igen en.";
-  }
-
-  /// sg problem
-  template<typename Graph, typename CapacityMap>
-  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity) {
-    typename Graph::Node u;
-    NullMap<typename Graph::Edge, int> n;
-    readDimacs(is, g, capacity, u, u, n);
-  }
-
-  /// shortest path problem
-  template<typename Graph, typename CapacityMap>
-  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 
-		  typename Graph::Node &s) {
-    NullMap<typename Graph::Edge, int> n;
-    readDimacs(is, g, capacity, s, s, n);
-  }
-
-  /// max flow problem
-  template<typename Graph, typename CapacityMap>
-  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 
-		  typename Graph::Node &s, typename Graph::Node &t) {
-    NullMap<typename Graph::Edge, int> n;
-    readDimacs(is, g, capacity, s, t, n);
-  }
-
-  /// min cost flow problem
-  template<typename Graph, typename CapacityMap, typename CostMap>
-  void readDimacs(std::istream& is, Graph &g, CapacityMap& capacity, 
-		  typename Graph::Node &s, typename Graph::Node &t, 
-		  CostMap& cost) {
-    g.clear();
-    typename CapacityMap::ValueType _cap;
-    typename CostMap::ValueType _cost;
-    char d;
-    std::string problem;
-    char c;
-    int i, j;
-    std::string str;
-    int n, m; 
-    typename Graph::Edge e;
-    std::vector<typename Graph::Node> nodes;
-    while (is>>c) {
-      switch (c) {
-      case 'c': //comment
-	getline(is, str);
-	break;
-      case 'p': //problem definition
-	is >> problem >> n >> m;
-	getline(is, str);
-	nodes.resize(n+1);
-	for (int k=1; k<=n; ++k) nodes[k]=g.addNode();
-	break;
-      case 'n': //node definition
-	if (problem=="sp") { //shortest path problem
-	  is >> i;
-	  getline(is, str);
-	  s=nodes[i];
-	}
-	if (problem=="max" || problem=="min") { //((max) or (min cost)) flow problem
-	  is >> i >> d;
-	  getline(is, str);
-	  if (d=='s') s=nodes[i];
-	  if (d=='t') t=nodes[i];
-	}
-	break;
-      case 'a':
-	if ( problem == "mat" ) {
-	  is >> i >> j;
-	  getline(is, str);
-	  g.addEdge(nodes[i], nodes[j]);
-	}
-	if ( problem == "max" || problem == "sp") {
-	  is >> i >> j >> _cap;
-	  getline(is, str);
-	  e=g.addEdge(nodes[i], nodes[j]);
-	  capacity.update();
-	  capacity.set(e, _cap);
-	}
-	if ( problem == "min" ) {
-	  is >> i >> j >> _cap >> _cost;
-	  getline(is, str);
-	  e=g.addEdge(nodes[i], nodes[j]);
-	  capacity.update();
-	  capacity.set(e, _cap);
-	  cost.update();
-	  cost.set(e, _cost);
-	}
-	break;
-      }
-    }
-  }
-
-
-  
-  /// write matching problem
-  template<typename Graph>
-  void writeDimacs(std::ostream& os, const Graph &g) {
-    typedef typename Graph::NodeIt NodeIt;
-    typedef typename Graph::EdgeIt EdgeIt;  
-    
-    typename Graph::template NodeMap<int> nodes(g);
-
-    os << "c matching problem" << std::endl;
-
-    int i=1;
-    NodeIt v;
-    for(g.first(v); g.valid(v); g.next(v)) {
-      nodes.set(v, i);
-      ++i;
-    }    
-    
-    os << "p mat " << g.nodeNum() << " " << g.edgeNum() << std::endl;
-
-    EdgeIt e;
-    for(g.first(e); g.valid(e); g.next(e)) {
-      os << "a " << nodes[g.tail(e)] << " " << nodes[g.head(e)] << std::endl; 
-    }
-
-  }
-
-
-
-} //namespace hugo
-
-#endif //HUGO_DIMACS_H
diff -r d8863141824d -r fb261e3a9a0f src/include/error.h
--- a/src/include/error.h	Thu May 06 09:26:23 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,68 +0,0 @@
-// -*- C++ -*- //
-
-#ifndef HUGO_ERROR_H
-#define HUGO_ERROR_H
-
-//! \ingroup misc
-//! \file
-//! \brief Basic error handling (signaling) routines.
-
-#include <exception>
-#include <string>
-#include <sstream>
-
-
-namespace hugo {
-
-  /**
-   * \brief Generic exception class.
-   *
-   * \todo Do we need this?
-   *
-   * \todo Don't we need different kind of exceptions for different kind
-   * of errors?
-   * Shouldn't we use \<stdexcept\> instead?
-   */
-  class Exception : public std::exception {
-  protected:
-    std::ostringstream buf;
-  public:
-    Exception() {}
-    explicit Exception(const std::string &s) { buf << s; }
-    Exception(const Exception &e) : std::exception() {
-      buf << e.buf.str();
-    }
-    virtual ~Exception() throw() {}
-    
-    virtual const char* what() const throw() {
-      return buf.str().c_str();
-    }
-
-    Exception& operator<<(std::string const& s) { buf << s; return *this; }
-    Exception& operator<<(char const *s) { buf << s; return *this; }
-    Exception& operator<<(int i) { buf << i; return *this; }
-  };
-
-  /**
-   * \brief Generic error signaling function.
-   *
-   * \todo Do we really need this? Is it helpful?
-   */
-  inline void fault(const std::string &msg) {
-    throw Exception(msg);
-  }
-
-  /**
-   * \brief Macro for mark not yet implemented features.
-   *
-   * \todo Is this the right place for this? It should be used only in
-   * modules under development.
-   */
-
-# define FIXME(msg) \
-    do { throw ::hugo::Exception() << "FIXME: " msg " (in: "    \
-      __FILE__ ", " << __LINE__ << ")";                         \
-    } while(false)
-
-}
-#endif // HUGO_ERROR_H
diff -r d8863141824d -r fb261e3a9a0f src/include/fib_heap.h
--- a/src/include/fib_heap.h	Thu May 06 09:26:23 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,500 +0,0 @@
-// -*- C++ -*-
-
-#ifndef HUGO_FIB_HEAP_H
-#define HUGO_FIB_HEAP_H
-
-///\ingroup auxdat
-///\file
-///\brief Fibonacci Heap implementation.
-
-#include <vector>
-#include <functional>
-#include <math.h>
-
-namespace hugo {
-  
-  /// \addtogroup auxdat
-  /// @{
-
-  /// An implementation of the Fibonacci Heap.
-
-  /**
-     This class implements the \e Fibonacci \e heap data structure. A \e heap
-     is a data structure for storing items with specified values called \e
-     priorities, such that finding the item with minimum priority with respect
-     to \e Compare is efficient. In a heap one can change the priority of an
-     item, add or erase an item, etc.
-
-     The methods \ref increase and \ref erase are not efficient in a Fibonacci
-     heap. In case of many calls to these operations, it is better to use a
-     \e binary \e heap.
-     
-     \param Item The type of the items to be stored.  
-     \param Prio The type of the priority of the items.
-     \param ItemIntMap A read and writable Item int map, for the usage of
-     the heap.
-     \param Compare A class for the comparison of the priorities. The
-     default is \c std::less<Prio>.
-
-  */
-
-#ifdef DOXYGEN
-  template <typename Item, 
-	    typename Prio, 
-	    typename ItemIntMap, 
-	    typename Compare>
-#else
-  template <typename Item, 
-	    typename Prio, 
-	    typename ItemIntMap, 
-	    typename Compare = std::less<Prio> >
-#endif
-  class FibHeap {
-  public:     
-    typedef Prio PrioType;
-    
-  private:
-    class store;
-    
-    std::vector<store> container;
-    int minimum;
-    ItemIntMap &iimap;
-    Compare comp;
-    int num_items;
-    
-  public:
-    enum state_enum {
-      IN_HEAP = 0,
-      PRE_HEAP = -1,
-      POST_HEAP = -2
-    };
-    
-    FibHeap(ItemIntMap &_iimap) : minimum(0), iimap(_iimap), num_items() {} 
-    FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0), 
-      iimap(_iimap), comp(_comp), num_items() {}
-    
-    ///The number of items stored in the heap.
-
-    /**
-       Returns the number of items stored in the heap.
-    */
-    int size() const { return num_items; }
-
-    ///Checks if the heap stores no items.
-    
-    /**
-       Returns \c true iff the heap stores no items.
-    */
-    bool empty() const { return num_items==0; }
-
-    ///\c item gets to the heap with priority \c value independently if \c item was already there.
-
-    /**
-       This method calls \ref push(\c item, \c value) if \c item is not
-       stored in the heap and it calls \ref decrease(\c item, \c value) or
-       \ref increase(\c item, \c value) otherwise.
-    */
-    void set (Item const item, PrioType const value); 
-    
-    ///Adds \c item to the heap with priority \c value. 
-    
-    /**
-       Adds \c item to the heap with priority \c value. 
-       \pre \c item must not be stored in the heap. 
-    */
-    void push (Item const item, PrioType const value);
-    
-    
-    ///Returns the item having the minimum priority w.r.t.  Compare.
-    
-    /**
-       This method returns the item having the minimum priority w.r.t.  Compare. 
-       \pre The heap must be nonempty.
-    */
-    Item top() const { return container[minimum].name; }
-    
-
-    ///Returns the minimum priority w.r.t.  Compare.
-
-    /**
-       It returns the minimum priority w.r.t.  Compare.
-       \pre The heap must be nonempty.
-    */
-    PrioType prio() const { return container[minimum].prio; }
-    
-
-    ///Returns the priority of \c item.
-
-    /**
-       It returns the priority of \c item.
-       \pre \c item must be in the heap.
-    */
-    PrioType& operator[](const Item& item) { 
-      return container[iimap[item]].prio; 
-    }
-    
-    ///Returns the priority of \c item.
-    
-    /**
-       It returns the priority of \c item.
-       \pre \c item must be in the heap.
-    */
-    const PrioType& operator[](const Item& item) const { 
-      return container[iimap[item]].prio; 
-    }
-
-
-    ///Deletes the item with minimum priority w.r.t.  Compare.
-
-    /**
-    This method deletes the item with minimum priority w.r.t. 
-    Compare from the heap.
-    \pre The heap must be non-empty.
-    */
-    void pop();
-
-    ///Deletes \c item from the heap.
-
-    /**
-       This method deletes \c item from the heap, if \c item was already
-       stored in the heap. It is quite inefficient in Fibonacci heaps.
-    */
-    void erase (const Item& item); 
-
-    ///Decreases the priority of \c item to \c value.
-
-    /**
-       This method decreases the priority of \c item to \c value.
-       \pre \c item must be stored in the heap with priority at least \c
-       value w.r.t.  Compare.
-    */
-    void decrease (Item item, PrioType const value); 
-
-
-    ///Increases the priority of \c item to \c value.
-
-    /**
-       This method sets the priority of \c item to \c value. Though
-       there is no precondition on the priority of \c item, this
-       method should be used only if there is a need to really \e increase
-       (w.r.t.  Compare) the priority of \c item, because this
-       method is inefficient.
-    */
-    void increase (Item item, PrioType const value) {
-      erase(item);
-      push(item, value);
-    }
-
-
-    ///Tells if \c item is in, was already in, or has never been in the heap.
-
-    /**
-       This method returns PRE_HEAP if \c item has never been in the
-       heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
-       otherwise. In the latter case it is possible that \c item will
-       get back to the heap again.
-    */
-    state_enum state(const Item &item) const {
-      int i=iimap[item];
-      if( i>=0 ) {
-	if ( container[i].in ) i=0;
-	else i=-2; 
-      }
-      return state_enum(i);
-    }    
-    
-  private:
-    
-    void balance();
-    void makeroot(int c);
-    void cut(int a, int b);
-    void cascade(int a);
-    void fuse(int a, int b);
-    void unlace(int a);
-
-
-    class store {
-      friend class FibHeap;
-      
-      Item name;
-      int parent;
-      int left_neighbor;
-      int right_neighbor;
-      int child;
-      int degree;  
-      bool marked;
-      bool in;
-      PrioType prio;
-      
-      store() : parent(-1), child(-1), degree(), marked(false), in(true) {} 
-    };
-  };    
- 
-
-
-    // **********************************************************************
-    //  IMPLEMENTATIONS
-    // **********************************************************************
-    
-  template <typename Item, typename Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::set 
-  (Item const item, PrioType const value) 
-  {
-    int i=iimap[item];
-    if ( i >= 0 && container[i].in ) {
-      if ( comp(value, container[i].prio) ) decrease(item, value); 
-      if ( comp(container[i].prio, value) ) increase(item, value); 
-    } else push(item, value);
-  }
-    
-  template <typename Item, typename Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::push 
-  (Item const item, PrioType const value) {
-      int i=iimap[item];      
-      if ( i < 0 ) {
-	int s=container.size();
-	iimap.set( item, s );	
-	store st;
-	st.name=item;
-	container.push_back(st);
-	i=s;
-      } else {
-	container[i].parent=container[i].child=-1;
-	container[i].degree=0;
-	container[i].in=true;
-	container[i].marked=false;
-      }
-
-      if ( num_items ) {
-	container[container[minimum].right_neighbor].left_neighbor=i;
-	container[i].right_neighbor=container[minimum].right_neighbor;
-	container[minimum].right_neighbor=i;
-	container[i].left_neighbor=minimum;
-	if ( comp( value, container[minimum].prio) ) minimum=i; 
-      } else {
-	container[i].right_neighbor=container[i].left_neighbor=i;
-	minimum=i;	
-      }
-      container[i].prio=value;
-      ++num_items;
-    }
-    
-  template <typename Item, typename Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::pop() {
-      /*The first case is that there are only one root.*/
-      if ( container[minimum].left_neighbor==minimum ) {
-	container[minimum].in=false;
-	if ( container[minimum].degree!=0 ) { 
-	  makeroot(container[minimum].child);
-	  minimum=container[minimum].child;
-	  balance();
-	}
-      } else {
-	int right=container[minimum].right_neighbor;
-	unlace(minimum);
-	container[minimum].in=false;
-	if ( container[minimum].degree > 0 ) {
-	  int left=container[minimum].left_neighbor;
-	  int child=container[minimum].child;
-	  int last_child=container[child].left_neighbor;
-	
-	  makeroot(child);
-	  
-	  container[left].right_neighbor=child;
-	  container[child].left_neighbor=left;
-	  container[right].left_neighbor=last_child;
-	  container[last_child].right_neighbor=right;
-	}
-	minimum=right;
-	balance();
-      } // the case where there are more roots
-      --num_items;   
-    }
-
-
-  template <typename Item, typename Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::erase 
-  (const Item& item) {
-      int i=iimap[item];
-      
-      if ( i >= 0 && container[i].in ) { 	
-	if ( container[i].parent!=-1 ) {
-	  int p=container[i].parent;
-	  cut(i,p);	    
-	  cascade(p);
-	}
-	minimum=i;     //As if its prio would be -infinity
-	pop();
-      }
-  }
-    
-  template <typename Item, typename Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease 
-  (Item item, PrioType const value) {
-      int i=iimap[item];
-      container[i].prio=value;
-      int p=container[i].parent;
-      
-      if ( p!=-1 && comp(value, container[p].prio) ) {
-	cut(i,p);	    
-	cascade(p);
-      }      
-      if ( comp(value, container[minimum].prio) ) minimum=i; 
-  }
- 
-
-  template <typename Item, typename Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() {      
-
-    int maxdeg=int( floor( 2.08*log(double(container.size()))))+1;
-  
-    std::vector<int> A(maxdeg,-1); 
-    
-    /*
-     *Recall that now minimum does not point to the minimum prio element.
-     *We set minimum to this during balance().
-     */
-    int anchor=container[minimum].left_neighbor; 
-    int next=minimum; 
-    bool end=false; 
-    	
-       do {
-	int active=next;
-	if ( anchor==active ) end=true;
-	int d=container[active].degree;
-	next=container[active].right_neighbor;
-
-	while (A[d]!=-1) {	  
-	  if( comp(container[active].prio, container[A[d]].prio) ) {
-	    fuse(active,A[d]); 
-	  } else { 
-	    fuse(A[d],active);
-	    active=A[d];
-	  } 
-	  A[d]=-1;
-	  ++d;
-	}	
-	A[d]=active;
-       } while ( !end );
-
-
-       while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;
-       int s=minimum;
-       int m=minimum;
-       do {  
-	 if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
-	 s=container[s].right_neighbor;
-       } while ( s != m );
-    }
-
-  template <typename Item, typename Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot 
-  (int c) {
-      int s=c;
-      do {  
-	container[s].parent=-1;
-	s=container[s].right_neighbor;
-      } while ( s != c );
-    }
-  
-  
-  template <typename Item, typename Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::cut 
-  (int a, int b) {    
-    /*
-     *Replacing a from the children of b.
-     */
-    --container[b].degree;
-    
-    if ( container[b].degree !=0 ) {
-      int child=container[b].child;
-      if ( child==a ) 
-	container[b].child=container[child].right_neighbor;
-      unlace(a);
-    }
-    
-    
-    /*Lacing a to the roots.*/
-    int right=container[minimum].right_neighbor;
-    container[minimum].right_neighbor=a;
-    container[a].left_neighbor=minimum;
-    container[a].right_neighbor=right;
-    container[right].left_neighbor=a;
-    
-    container[a].parent=-1;
-    container[a].marked=false;
-  }
-  
-
-  template <typename Item, typename Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade 
-  (int a) 
-    {
-      if ( container[a].parent!=-1 ) {
-	int p=container[a].parent;
-	
-	if ( container[a].marked==false ) container[a].marked=true;
-	else {
-	  cut(a,p);
-	  cascade(p);
-	}
-      }
-    }
-
-
-  template <typename Item, typename Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse 
-  (int a, int b) {
-      unlace(b);
-      
-      /*Lacing b under a.*/
-      container[b].parent=a;
-
-      if (container[a].degree==0) {
-	container[b].left_neighbor=b;
-	container[b].right_neighbor=b;
-	container[a].child=b;	
-      } else {
-	int child=container[a].child;
-	int last_child=container[child].left_neighbor;
-	container[child].left_neighbor=b;
-	container[b].right_neighbor=child;
-	container[last_child].right_neighbor=b;
-	container[b].left_neighbor=last_child;
-      }
-
-      ++container[a].degree;
-      
-      container[b].marked=false;
-    }
-
-  
-  /*
-   *It is invoked only if a has siblings.
-   */
-  template <typename Item, typename Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace 
-  (int a) {      
-      int leftn=container[a].left_neighbor;
-      int rightn=container[a].right_neighbor;
-      container[leftn].right_neighbor=rightn;
-      container[rightn].left_neighbor=leftn;
-  }
-  
-  ///@}
-
-} //namespace hugo
-
-#endif //HUGO_FIB_HEAP_H
-
diff -r d8863141824d -r fb261e3a9a0f src/include/invalid.h
--- a/src/include/invalid.h	Thu May 06 09:26:23 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,38 +0,0 @@
-// -*- mode:C++ -*-
-
-#ifndef HUGO_INVALID_H
-#define HUGO_INVALID_H
-
-///\file
-///\brief Definition of INVALID.
-
-namespace hugo {
-
-  /// Dummy type to make it easier to make invalid iterators.
-  
-  /// See \ref INVALID, how to use it.
-  
-  struct Invalid {
-  public:
-    bool operator==(Invalid) { return true;  }
-    bool operator!=(Invalid) { return false; }
-    bool operator< (Invalid) { return false; }
-  };
-  
-  /// Invalid iterators.
-  
-  /// \ref Invalid is a global type that converts to each iterator
-  /// in such a way that the value of the target iterator will be invalid.
-
-  // It is also used to convert the \c INVALID constant to the
-  // node iterator that makes is possible to write 
-
-  //extern Invalid INVALID;
-
-  //const Invalid &INVALID = *(Invalid *)0;
-  const Invalid INVALID = Invalid();
-
-} //namespace hugo
-
-#endif
-  
diff -r d8863141824d -r fb261e3a9a0f src/include/maps.h
--- a/src/include/maps.h	Thu May 06 09:26:23 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,129 +0,0 @@
-// -*- C++ -*- //
-#ifndef HUGO_MAPS_H
-#define HUGO_MAPS_H
-
-///\file
-///\brief Miscellaneous property maps
-///
-///\todo This file has the same name as the concept file in skeletons,
-/// and this is not easily detectable in docs...
-
-#include <map>
-
-namespace hugo {
-
-  /// Null map. (aka DoNothingMap)
-
-  /// If you have to provide a map only for its type definitions,
-  /// or if you have to provide a writable map, but will not use the
-  /// data written to it...
-  template<typename K, typename T>
-  class NullMap
-  {
-  public:
-    typedef K KeyType;
-    typedef T ValueType;
-
-    T operator[](const K&) const { return T(); }
-    void set(const K&, const T&) {}
-    ///\bug when update is removed from map concepts by being dynamic
-    ///stuffs, this line have to be removed.
-    void update() { }
-  };
-
-
-  /// Constant map.
-
-  /// This is a readable map which assignes a specified value to each key.
-  /// In other aspects it is equivalent to the \ref NullMap
-  template<typename K, typename T>
-  class ConstMap
-  {
-    T v;
-  public:
-    typedef K KeyType;
-    typedef T ValueType;
-
-    ConstMap() {}
-    ConstMap(const T &_v) : v(_v) {}
-
-    T operator[](const K&) const { return v; }
-    void set(const K&, const T&) {}
-
-    template<typename T1>
-    struct rebind {
-      typedef ConstMap<K,T1> other;
-    };
-
-    template<typename T1>
-    ConstMap(const ConstMap<K,T1> &, const T &_v) : v(_v) {}
-  };
-
-
-
-  /// \c std::map wrapper
-
-  /// This is essentially a wrapper for \c std::map. With addition that
-  /// you can specify a default value different from \c ValueType() .
-  ///
-  /// \todo Provide allocator parameter...
-  template <typename Key, typename T, typename Compare = std::less<Key> >
-  class StdMap : public std::map<Key,T,Compare> {
-    typedef std::map<Key,T,Compare> parent;
-    T v;
-    typedef typename parent::value_type PairType;
-
-  public:
-    typedef Key KeyType;
-    typedef T ValueType;
-    typedef T& ReferenceType;
-    typedef const T& ConstReferenceType;
-
-
-    StdMap() : v() {}
-    /// Constructor with specified default value
-    StdMap(const T& _v) : v(_v) {}
-
-    /// \brief Constructs the map from an appropriate std::map.
-    ///
-    /// \warning Inefficient: copies the content of \c m !
-    StdMap(const parent &m) : parent(m) {}
-    /// \brief Constructs the map from an appropriate std::map, and explicitly
-    /// specifies a default value.
-    ///
-    /// \warning Inefficient: copies the content of \c m !
-    StdMap(const parent &m, const T& _v) : parent(m), v(_v) {}
-    
-    template<typename T1, typename Comp1>
-    StdMap(const StdMap<Key,T1,Comp1> &m, const T &_v) { 
-      //FIXME; 
-    }
-
-    ReferenceType operator[](const Key &k) {
-      return insert(PairType(k,v)).first -> second;
-    }
-    ConstReferenceType operator[](const Key &k) const {
-      typename parent::iterator i = lower_bound(k);
-      if (i == parent::end() || parent::key_comp()(k, (*i).first))
-	return v;
-      return (*i).second;
-    }
-    void set(const Key &k, const T &t) {
-      parent::operator[](k) = t;
-    }
-
-    /// Changes the default value of the map.
-    /// \return Returns the previous default value.
-    ///
-    /// \warning The value of some keys (which has alredy been queried, but
-    /// the value has been unchanged from the default) may change!
-    T setDefault(const T &_v) { T old=v; v=_v; return old; }
-
-    template<typename T1>
-    struct rebind {
-      typedef StdMap<Key,T1,Compare> other;
-    };
-  };
-  
-}
-#endif // HUGO_MAPS_H
diff -r d8863141824d -r fb261e3a9a0f src/include/skeletons/graph.h
--- a/src/include/skeletons/graph.h	Thu May 06 09:26:23 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,399 +0,0 @@
-// -*- c++ -*-
-#ifndef HUGO_SKELETON_GRAPH_H
-#define HUGO_SKELETON_GRAPH_H
-
-///\file
-///\brief Declaration of GraphSkeleton.
-
-#include <invalid.h>
-
-/// The namespace of HugoLib
-namespace hugo {
-
-  // @defgroup empty_graph The GraphSkeleton class
-  // @{
-
-  /// An empty graph class.
-  
-  /// This class provides all the common features of a graph structure,
-  /// however completely without implementations and real data structures
-  /// behind the interface.
-  /// All graph algorithms should compile with this class, but it will not
-  /// run properly, of course.
-  ///
-  /// It can be used for checking the interface compatibility,
-  /// or it can serve as a skeleton of a new graph structure.
-  /// 
-  /// Also, you will find here the full documentation of a certain graph
-  /// feature, the documentation of a real graph imlementation
-  /// like @ref ListGraph or
-  /// @ref SmartGraph will just refer to this structure.
-  class GraphSkeleton
-  {
-  public:
-    /// Defalult constructor.
-    GraphSkeleton() {}
-    ///Copy consructor.
-
-    ///\todo It is not clear, what we expect from a copy constructor.
-    ///E.g. How to assign the nodes/edges to each other? What about maps?
-    GraphSkeleton(const GraphSkeleton &G) {}
-
-    /// The base type of the node iterators.
-
-    /// This is the base type of each node iterators,
-    /// thus each kind of node iterator will convert to this.
-    class Node {
-    public:
-      /// @warning The default constructor sets the iterator
-      /// to an undefined value.
-      Node() {}   //FIXME
-      /// Invalid constructor \& conversion.
-
-      /// This constructor initializes the iterator to be invalid.
-      /// \sa Invalid for more details.
-
-      Node(Invalid) {}
-      //Node(const Node &) {}
-
-      /// Two iterators are equal if and only if they point to the
-      /// same object or both are invalid.
-      bool operator==(Node) const { return true; }
-
-      /// \sa \ref operator==(Node n)
-      ///
-      bool operator!=(Node) const { return true; }
-
-      bool operator<(Node) const { return true; }
-    };
-    
-    /// This iterator goes through each node.
-
-    /// This iterator goes through each node.
-    /// Its usage is quite simple, for example you can count the number
-    /// of nodes in graph \c G of type \c Graph like this:
-    /// \code
-    ///int count=0;
-    ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++;
-    /// \endcode
-    class NodeIt : public Node {
-    public:
-      /// @warning The default constructor sets the iterator
-      /// to an undefined value.
-      NodeIt() {} //FIXME
-      /// Invalid constructor \& conversion.
-
-      /// Initialize the iterator to be invalid
-      /// \sa Invalid for more details.
-      NodeIt(Invalid) {}
-      /// Sets the iterator to the first node of \c G.
-      NodeIt(const GraphSkeleton &) {}
-      /// @warning The default constructor sets the iterator
-      /// to an undefined value.
-      NodeIt(const NodeIt &n) : Node(n) {}
-    };
-    
-    
-    /// The base type of the edge iterators.
-    class Edge {
-    public:
-      /// @warning The default constructor sets the iterator
-      /// to an undefined value.
-      Edge() {}   //FIXME
-      /// Initialize the iterator to be invalid
-      Edge(Invalid) {}
-      /// Two iterators are equal if and only if they point to the
-      /// same object or both are invalid.
-      bool operator==(Edge) const { return true; }
-      bool operator!=(Edge) const { return true; }
-      bool operator<(Edge) const { return true; }
-    };
-    
-    /// This iterator goes trough the outgoing edges of a node.
-
-    /// This iterator goes trough the \e outgoing edges of a certain node
-    /// of a graph.
-    /// Its usage is quite simple, for example you can count the number
-    /// of outgoing edges of a node \c n
-    /// in graph \c G of type \c Graph as follows.
-    /// \code
-    ///int count=0;
-    ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
-    /// \endcode
-    
-    class OutEdgeIt : public Edge {
-    public:
-      /// @warning The default constructor sets the iterator
-      /// to an undefined value.
-      OutEdgeIt() {}
-      /// Initialize the iterator to be invalid
-      OutEdgeIt(Invalid) {}
-      /// This constructor sets the iterator to first outgoing edge.
-    
-      /// This constructor set the iterator to the first outgoing edge of
-      /// node
-      ///@param n the node
-      ///@param G the graph
-      OutEdgeIt(const GraphSkeleton &, Node) {}
-    };
-
-    /// This iterator goes trough the incoming edges of a node.
-
-    /// This iterator goes trough the \e incoming edges of a certain node
-    /// of a graph.
-    /// Its usage is quite simple, for example you can count the number
-    /// of outgoing edges of a node \c n
-    /// in graph \c G of type \c Graph as follows.
-    /// \code
-    ///int count=0;
-    ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
-    /// \endcode
-
-    class InEdgeIt : public Edge {
-    public:
-      /// @warning The default constructor sets the iterator
-      /// to an undefined value.
-      InEdgeIt() {}
-      /// Initialize the iterator to be invalid
-      InEdgeIt(Invalid) {}
-      InEdgeIt(const GraphSkeleton &, Node) {}    
-    };
-    //  class SymEdgeIt : public Edge {};
-
-    /// This iterator goes through each edge.
-
-    /// This iterator goes through each edge of a graph.
-    /// Its usage is quite simple, for example you can count the number
-    /// of edges in a graph \c G of type \c Graph as follows:
-    /// \code
-    ///int count=0;
-    ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++;
-    /// \endcode
-    class EdgeIt : public Edge {
-    public:
-      /// @warning The default constructor sets the iterator
-      /// to an undefined value.
-      EdgeIt() {}
-      /// Initialize the iterator to be invalid
-      EdgeIt(Invalid) {}
-      EdgeIt(const GraphSkeleton &) {}
-    };
-
-    /// First node of the graph.
-
-    /// \retval i the first node.
-    /// \return the first node.
-    ///
-    NodeIt &first(NodeIt &i) const { return i;}
-
-    /// The first incoming edge.
-    InEdgeIt &first(InEdgeIt &i, Node) const { return i;}
-    /// The first outgoing edge.
-    OutEdgeIt &first(OutEdgeIt &i, Node) const { return i;}
-    //  SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
-    /// The first edge of the Graph.
-    EdgeIt &first(EdgeIt &i) const { return i;}
-
-//     Node getNext(Node) const {}
-//     InEdgeIt getNext(InEdgeIt) const {}
-//     OutEdgeIt getNext(OutEdgeIt) const {}
-//     //SymEdgeIt getNext(SymEdgeIt) const {}
-//     EdgeIt getNext(EdgeIt) const {}
-
-    /// Go to the next node.
-    NodeIt &next(NodeIt &i) const { return i;}
-    /// Go to the next incoming edge.
-    InEdgeIt &next(InEdgeIt &i) const { return i;}
-    /// Go to the next outgoing edge.
-    OutEdgeIt &next(OutEdgeIt &i) const { return i;}
-    //SymEdgeIt &next(SymEdgeIt &) const {}
-    /// Go to the next edge.
-    EdgeIt &next(EdgeIt &i) const { return i;}
-
-    ///Gives back the head node of an edge.
-    Node head(Edge) const { return INVALID; }
-    ///Gives back the tail node of an edge.
-    Node tail(Edge) const { return INVALID; }
-  
-    //   Node aNode(InEdgeIt) const {}
-    //   Node aNode(OutEdgeIt) const {}
-    //   Node aNode(SymEdgeIt) const {}
-
-    //   Node bNode(InEdgeIt) const {}
-    //   Node bNode(OutEdgeIt) const {}
-    //   Node bNode(SymEdgeIt) const {}
-
-    /// Checks if a node iterator is valid
-
-    ///\todo Maybe, it would be better if iterator converted to
-    ///bool directly, as Jacint prefers.
-    bool valid(const Node&) const { return true;}
-    /// Checks if an edge iterator is valid
-
-    ///\todo Maybe, it would be better if iterator converted to
-    ///bool directly, as Jacint prefers.
-    bool valid(const Edge&) const { return true;}
-
-    ///Gives back the \e id of a node.
-
-    ///\warning Not all graph structures provide this feature.
-    ///
-    int id(const Node&) const { return 0;}
-    ///Gives back the \e id of an edge.
-
-    ///\warning Not all graph structures provide this feature.
-    ///
-    int id(const Edge&) const { return 0;}
-
-    //void setInvalid(Node &) const {};
-    //void setInvalid(Edge &) const {};
-  
-    ///Add a new node to the graph.
-
-    /// \return the new node.
-    ///
-    Node addNode() { return INVALID;}
-    ///Add a new edge to the graph.
-
-    ///Add a new edge to the graph with tail node \c tail
-    ///and head node \c head.
-    ///\return the new edge.
-    Edge addEdge(Node, Node) { return INVALID;}
-    
-    /// Resets the graph.
-
-    /// This function deletes all edges and nodes of the graph.
-    /// It also frees the memory allocated to store them.
-    void clear() {}
-
-    int nodeNum() const { return 0;}
-    int edgeNum() const { return 0;}
-
-    ///Read/write/reference map of the nodes to type \c T.
-
-    ///Read/write/reference map of the nodes to type \c T.
-    /// \sa MemoryMapSkeleton
-    /// \todo We may need copy constructor
-    /// \todo We may need conversion from other nodetype
-    /// \todo We may need operator=
-    /// \warning Making maps that can handle bool type (NodeMap<bool>)
-    /// needs extra attention!
-
-    template<class T> class NodeMap
-    {
-    public:
-      typedef T ValueType;
-      typedef Node KeyType;
-
-      NodeMap(const GraphSkeleton &) {}
-      NodeMap(const GraphSkeleton &, T) {}
-
-      template<typename TT> NodeMap(const NodeMap<TT> &) {}
-
-      /// Sets the value of a node.
-
-      /// Sets the value associated with node \c i to the value \c t.
-      ///
-      void set(Node, T) {}
-      // Gets the value of a node.
-      //T get(Node i) const {return *(T*)0;}  //FIXME: Is it necessary?
-      T &operator[](Node) {return *(T*)0;}
-      const T &operator[](Node) const {return *(T*)0;}
-
-      /// Updates the map if the graph has been changed
-
-      /// \todo Do we need this?
-      ///
-      void update() {}
-      void update(T a) {}   //FIXME: Is it necessary
-    };
-
-    ///Read/write/reference map of the edges to type \c T.
-
-    ///Read/write/reference map of the edges to type \c T.
-    ///It behaves exactly in the same way as \ref NodeMap.
-    /// \sa NodeMap
-    /// \sa MemoryMapSkeleton
-    /// \todo We may need copy constructor
-    /// \todo We may need conversion from other edgetype
-    /// \todo We may need operator=
-    template<class T> class EdgeMap
-    {
-    public:
-      typedef T ValueType;
-      typedef Edge KeyType;
-
-      EdgeMap(const GraphSkeleton &) {}
-      EdgeMap(const GraphSkeleton &, T ) {}
-    
-      ///\todo It can copy between different types.
-      ///
-      template<typename TT> EdgeMap(const EdgeMap<TT> &) {}
-
-      void set(Edge, T) {}
-      //T get(Edge) const {return *(T*)0;}
-      T &operator[](Edge) {return *(T*)0;}
-      const T &operator[](Edge) const {return *(T*)0;}
-    
-      void update() {}
-      void update(T a) {}   //FIXME: Is it necessary
-    };
-  };
-
-  /// An empty eraseable graph class.
-  
-  /// This class provides all the common features of an \e eraseable graph
-  /// structure,
-  /// however completely without implementations and real data structures
-  /// behind the interface.
-  /// All graph algorithms should compile with this class, but it will not
-  /// run properly, of course.
-  ///
-  /// \todo This blabla could be replaced by a sepatate description about
-  /// Skeletons.
-  ///
-  /// It can be used for checking the interface compatibility,
-  /// or it can serve as a skeleton of a new graph structure.
-  /// 
-  /// Also, you will find here the full documentation of a certain graph
-  /// feature, the documentation of a real graph imlementation
-  /// like @ref ListGraph or
-  /// @ref SmartGraph will just refer to this structure.
-  class EraseableGraphSkeleton : public GraphSkeleton
-  {
-  public:
-    /// Deletes a node.
-    void erase(Node n) {}
-    /// Deletes an edge.
-    void erase(Edge e) {}
-
-    /// Defalult constructor.
-    EraseableGraphSkeleton() {}
-    ///Copy consructor.
-    EraseableGraphSkeleton(const GraphSkeleton &G) {}
-  };
-
-  
-  // @}
-
-} //namespace hugo
-
-
-
-// class EmptyBipGraph : public Graph Skeleton
-// {
-//   class ANode {};
-//   class BNode {};
-
-//   ANode &next(ANode &) {}
-//   BNode &next(BNode &) {}
-
-//   ANode &getFirst(ANode &) const {}
-//   BNode &getFirst(BNode &) const {}
-
-//   enum NodeClass { A = 0, B = 1 };
-//   NodeClass getClass(Node n) {}
-
-// }
-
-#endif // HUGO_SKELETON_GRAPH_H
diff -r d8863141824d -r fb261e3a9a0f src/include/skeletons/maps.h
--- a/src/include/skeletons/maps.h	Thu May 06 09:26:23 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,130 +0,0 @@
-// -*- c++ -*-
-#ifndef HUGO_MAPSKELETON_H
-#define HUGO_MAPSKELETON_H
-
-///\file
-///\brief Map concepts checking classes for testing and documenting.
-
-namespace hugo {
-
-  /// The namespace of HUGOlib concepts and concept checking classes
-  namespace skeleton {
-  
-    /// Readable map concept
-    template<typename K, typename T>
-    class ReadableMap
-    {
-    public:
-      /// Map's key type.
-      typedef K KeyType;    
-      /// Map's value type. (The type of objects associated with the keys).
-      typedef T ValueType;
-
-      /// Returns the value associated with a key.
-      ValueType operator[](const KeyType &k) const {return ValueType();}
-
-      /// Copy contsructor. (optional)
-      ReadableMap(const ReadableMap&) {}
-      /// Assignment operator. (optional)
-      ReadableMap& operator=(const ReadableMap&) {return *this;}
-
-      ReadableMap() {}
-    };
-
-
-    /// Writable map concept
-    template<typename K, typename T>
-    class WritableMap
-    {
-    public:
-      /// Map's key type.
-      typedef K KeyType;    
-      /// Map's value type. (The type of objects associated with the keys).
-      typedef T ValueType;
-
-      /// Sets the value associated with a key.
-      void set(const KeyType &k,const ValueType &t) {}
-
-      WritableMap() {}
-    };
-
-    ///Read/Writeable map concept
-    template<typename K, typename T>
-    class ReadWritableMap : public ReadableMap<K,T>,
-			    public WritableMap<K,T>
-    {
-    public:
-      /// Map's key type.
-      typedef K KeyType;    
-      /// Map's value type. (The type of objects associated with the keys).
-      typedef T ValueType;
-
-      /// Returns the value associated with a key.
-      ValueType operator[](const KeyType &k) const {return ValueType();}
-      /// Sets the value associated with a key.
-      void set(const KeyType &k,const ValueType &t) {}
-
-      /// Copy contsructor. (optional)
-      ReadWritableMap(const ReadWritableMap&) {}
-      /// Assignment operator. (optional)
-      ReadWritableMap& operator=(const ReadWritableMap&) {return *this;}
-
-      /// Facility to define a map with an other value type (optional)
-      template<typename T1>
-      struct rebind {
-	/// The type of a map with the given value type
-	typedef ReadWritableMap<K,T1> other;
-      };
-      /// @brief Constructor that copies all keys from the other map and
-      /// assigns to them a default value (optional)
-      template<typename T1>
-      ReadWritableMap(const ReadWritableMap<K,T1> &map, const ValueType &v) {}
-
-      ReadWritableMap() {}
-    };
-  
-  
-    ///Dereferable map concept
-    template<typename K, typename T>
-    class DereferableMap : public ReadWritableMap<K,T>
-    {
-    public:
-      /// Map's key type.
-      typedef K KeyType;    
-      /// Map's value type. (The type of objects associated with the keys).
-      typedef T ValueType;
-      /// Map's reference type. (Reference to an object associated with a key)
-      typedef ValueType& ReferenceType;
-      /// Map's const reference type.
-      typedef const ValueType& ConstReferenceType;
-
-      ///Returns a reference to the value associated to a key.
-      ReferenceType operator[](const KeyType &i);
-      ///Returns a const reference to the value associated to a key.
-      ConstReferenceType operator[](const KeyType &i) const;
-      /// Sets the value associated with a key.
-      void set(const KeyType &k,const ValueType &t) { operator[](k)=t; }
-
-      /// Copy contsructor. (optional)
-      DereferableMap(const DereferableMap&) {}
-      /// Assignment operator. (optional)
-      DereferableMap& operator=(const DereferableMap&) {return *this;}
-
-      /// Facility to define a map with an other value type (optional)
-      template<typename T1>
-      struct rebind {
-	/// The type of a map with the given value type
-	typedef DereferableMap<K,T1> other;
-      };
-      /// @brief Constructor that copies all keys from the other map and
-      /// assigns to them a default value (optional)
-      template<typename T1>
-      DereferableMap(const DereferableMap<K,T1> &map, const ValueType &v) {}
-
-      DereferableMap() {}
-    };
-
-
-  }
-}
-#endif // HUGO_MAPSKELETON_H
diff -r d8863141824d -r fb261e3a9a0f src/include/smart_graph.h
--- a/src/include/smart_graph.h	Thu May 06 09:26:23 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,614 +0,0 @@
-// -*- mode:C++ -*-
-
-#ifndef HUGO_SMART_GRAPH_H
-#define HUGO_SMART_GRAPH_H
-
-///\ingroup graphs
-///\file
-///\brief SmartGraph and SymSmartGraph classes.
-
-#include <vector>
-#include <limits.h>
-
-#include "invalid.h"
-
-namespace hugo {
-
-/// \addtogroup graphs
-/// @{
-  class SymSmartGraph;
-
-  ///A smart graph class.
-
-  ///This is a simple and fast graph implementation.
-  ///It is also quite memory efficient, but at the price
-  ///that <b> it does not support node and edge deletion</b>.
-  ///It conforms to the graph interface documented under
-  ///the description of \ref GraphSkeleton.
-  ///\sa \ref GraphSkeleton.
-  ///
-  ///\todo Some member functions could be \c static.
-  ///\author Alpar Juttner
-  class SmartGraph {
-
-    struct NodeT 
-    {
-      int first_in,first_out;      
-      NodeT() : first_in(-1), first_out(-1) {}
-    };
-    struct EdgeT 
-    {
-      int head, tail, next_in, next_out;      
-      //FIXME: is this necessary?
-      EdgeT() : next_in(-1), next_out(-1) {}  
-    };
-
-    std::vector<NodeT> nodes;
-
-    std::vector<EdgeT> edges;
-    
-    protected:
-    
-    template <typename Key> class DynMapBase
-    {
-    protected:
-      const SmartGraph* G; 
-    public:
-      virtual void add(const Key k) = 0;
-      virtual void erase(const Key k) = 0;
-      DynMapBase(const SmartGraph &_G) : G(&_G) {}
-      virtual ~DynMapBase() {}
-      friend class SmartGraph;
-    };
-    
-  public:
-    template <typename T> class EdgeMap;
-    template <typename T> class EdgeMap;
-
-    class Node;
-    class Edge;
-
-    //  protected:
-    // HELPME:
-  protected:
-    ///\bug It must be public because of SymEdgeMap.
-    ///
-    mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
-    ///\bug It must be public because of SymEdgeMap.
-    ///
-    mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
-    
-  public:
-
-
-    class NodeIt;
-    class EdgeIt;
-    class OutEdgeIt;
-    class InEdgeIt;
-    
-    template <typename T> class NodeMap;
-    template <typename T> class EdgeMap;
-    
-  public:
-
-    SmartGraph() : nodes(), edges() { }
-    SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
-    
-    ~SmartGraph()
-    {
-      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
-	  i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
-      for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
-	  i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
-    }
-
-    int nodeNum() const { return nodes.size(); }  //FIXME: What is this?
-    int edgeNum() const { return edges.size(); }  //FIXME: What is this?
-
-    ///\bug This function does something different than
-    ///its name would suggests...
-    int maxNodeId() const { return nodes.size(); }  //FIXME: What is this?
-    ///\bug This function does something different than
-    ///its name would suggests...
-    int maxEdgeId() const { return edges.size(); }  //FIXME: What is this?
-
-    Node tail(Edge e) const { return edges[e.n].tail; }
-    Node head(Edge e) const { return edges[e.n].head; }
-
-    Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
-    Node aNode(InEdgeIt e) const { return edges[e.n].head; }
-
-    Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
-    Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
-
-    NodeIt& first(NodeIt& v) const { 
-      v=NodeIt(*this); return v; }
-    EdgeIt& first(EdgeIt& e) const { 
-      e=EdgeIt(*this); return e; }
-    OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 
-      e=OutEdgeIt(*this,v); return e; }
-    InEdgeIt& first(InEdgeIt& e, const Node v) const { 
-      e=InEdgeIt(*this,v); return e; }
-
-//     template< typename It >
-//     It first() const { It e; first(e); return e; }
-
-//     template< typename It >
-//     It first(Node v) const { It e; first(e,v); return e; }
-
-    bool valid(Edge e) const { return e.n!=-1; }
-    bool valid(Node n) const { return n.n!=-1; }
-    
-    ///\deprecated Use
-    ///\code
-    ///  e=INVALID;
-    ///\endcode
-    ///instead.
-    void setInvalid(Edge &e) { e.n=-1; }
-    ///\deprecated Use
-    ///\code
-    ///  e=INVALID;
-    ///\endcode
-    ///instead.
-    void setInvalid(Node &n) { n.n=-1; }
-    
-    template <typename It> It getNext(It it) const
-    { It tmp(it); return next(tmp); }
-
-    NodeIt& next(NodeIt& it) const { 
-      it.n=(it.n+2)%(nodes.size()+1)-1; 
-      return it; 
-    }
-    OutEdgeIt& next(OutEdgeIt& it) const
-    { it.n=edges[it.n].next_out; return it; }
-    InEdgeIt& next(InEdgeIt& it) const
-    { it.n=edges[it.n].next_in; return it; }
-    EdgeIt& next(EdgeIt& it) const { --it.n; return it; }
-
-    int id(Node v) const { return v.n; }
-    int id(Edge e) const { return e.n; }
-
-    Node addNode() {
-      Node n; n.n=nodes.size();
-      nodes.push_back(NodeT()); //FIXME: Hmmm...
-
-      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
-	  i!=dyn_node_maps.end(); ++i) (**i).add(n);
-
-      return n;
-    }
-    
-    Edge addEdge(Node u, Node v) {
-      Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
-      edges[e.n].tail=u.n; edges[e.n].head=v.n;
-      edges[e.n].next_out=nodes[u.n].first_out;
-      edges[e.n].next_in=nodes[v.n].first_in;
-      nodes[u.n].first_out=nodes[v.n].first_in=e.n;
-
-      for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
-	  i!=dyn_edge_maps.end(); ++i) (**i).add(e);
-
-      return e;
-    }
-
-    void clear() {nodes.clear();edges.clear();}
-
-    class Node {
-      friend class SmartGraph;
-      template <typename T> friend class NodeMap;
-      
-      friend class Edge;
-      friend class OutEdgeIt;
-      friend class InEdgeIt;
-      friend class SymEdge;
-
-    protected:
-      int n;
-      friend int SmartGraph::id(Node v) const; 
-      Node(int nn) {n=nn;}
-    public:
-      Node() {}
-      Node (Invalid) { n=-1; }
-      bool operator==(const Node i) const {return n==i.n;}
-      bool operator!=(const Node i) const {return n!=i.n;}
-      bool operator<(const Node i) const {return n<i.n;}
-    };
-    
-    class NodeIt : public Node {
-      friend class SmartGraph;
-    public:
-      NodeIt() : Node() { }
-      NodeIt(Invalid i) : Node(i) { }
-      NodeIt(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { }
-    };
-
-    class Edge {
-      friend class SmartGraph;
-      template <typename T> friend class EdgeMap;
-
-      //template <typename T> friend class SymSmartGraph::SymEdgeMap;      
-      //friend Edge SymSmartGraph::opposite(Edge) const;
-      
-      friend class Node;
-      friend class NodeIt;
-    protected:
-      int n;
-      friend int SmartGraph::id(Edge e) const;
-
-      Edge(int nn) {n=nn;}
-    public:
-      Edge() { }
-      Edge (Invalid) { n=-1; }
-      bool operator==(const Edge i) const {return n==i.n;}
-      bool operator!=(const Edge i) const {return n!=i.n;}
-      bool operator<(const Edge i) const {return n<i.n;}
-      ///\bug This is a workaround until somebody tells me how to
-      ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
-      int &idref() {return n;}
-      const int &idref() const {return n;}
-    };
-    
-    class EdgeIt : public Edge {
-      friend class SmartGraph;
-    public:
-      EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { }
-      EdgeIt (Invalid i) : Edge(i) { }
-      EdgeIt() : Edge() { }
-      ///\bug This is a workaround until somebody tells me how to
-      ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
-      int &idref() {return n;}
-    };
-    
-    class OutEdgeIt : public Edge {
-      friend class SmartGraph;
-    public: 
-      OutEdgeIt() : Edge() { }
-      OutEdgeIt (Invalid i) : Edge(i) { }
-
-      OutEdgeIt(const SmartGraph& G,const Node v)
-	: Edge(G.nodes[v.n].first_out) {}
-    };
-    
-    class InEdgeIt : public Edge {
-      friend class SmartGraph;
-    public: 
-      InEdgeIt() : Edge() { }
-      InEdgeIt (Invalid i) : Edge(i) { }
-      InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
-    };
-
-    template <typename T> class NodeMap : public DynMapBase<Node>
-    {
-      std::vector<T> container;
-
-    public:
-      typedef T ValueType;
-      typedef Node KeyType;
-
-      NodeMap(const SmartGraph &_G) :
-	DynMapBase<Node>(_G), container(_G.maxNodeId())
-      {
-	G->dyn_node_maps.push_back(this);
-      }
-      NodeMap(const SmartGraph &_G,const T &t) :
-	DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
-      {
-	G->dyn_node_maps.push_back(this);
-      }
-      
-      NodeMap(const NodeMap<T> &m) :
- 	DynMapBase<Node>(*m.G), container(m.container)
-      {
- 	G->dyn_node_maps.push_back(this);
-      }
-
-      template<typename TT> friend class NodeMap;
- 
-      ///\todo It can copy between different types.
-      ///
-      template<typename TT> NodeMap(const NodeMap<TT> &m) :
-	DynMapBase<Node>(*m.G)
-      {
-	G->dyn_node_maps.push_back(this);
-	typename std::vector<TT>::const_iterator i;
-	for(typename std::vector<TT>::const_iterator i=m.container.begin();
-	    i!=m.container.end();
-	    i++)
-	  container.push_back(*i);
-      }
-      ~NodeMap()
-      {
-	if(G) {
-	  std::vector<DynMapBase<Node>* >::iterator i;
-	  for(i=G->dyn_node_maps.begin();
-	      i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
-	  //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
-	  //A better way to do that: (Is this really important?)
-	  if(*i==this) {
-	    *i=G->dyn_node_maps.back();
-	    G->dyn_node_maps.pop_back();
-	  }
-	}
-      }
-
-      void add(const Node k) 
-      {
-	if(k.n>=int(container.size())) container.resize(k.n+1);
-      }
-
-      void erase(const Node) { }
-      
-      void set(Node n, T a) { container[n.n]=a; }
-      //'T& operator[](Node n)' would be wrong here
-      typename std::vector<T>::reference
-      operator[](Node n) { return container[n.n]; }
-      //'const T& operator[](Node n)' would be wrong here
-      typename std::vector<T>::const_reference 
-      operator[](Node n) const { return container[n.n]; }
-
-      ///\warning There is no safety check at all!
-      ///Using operator = between maps attached to different graph may
-      ///cause serious problem.
-      ///\todo Is this really so?
-      ///\todo It can copy between different types.
-      const NodeMap<T>& operator=(const NodeMap<T> &m)
-      {
-	container = m.container;
-	return *this;
-      }
-      template<typename TT>
-      const NodeMap<T>& operator=(const NodeMap<TT> &m)
-      {
-	std::copy(m.container.begin(), m.container.end(), container.begin());
-	return *this;
-      }
-      
-      void update() {}    //Useless for Dynamic Maps
-      void update(T a) {}  //Useless for Dynamic Maps
-    };
-    
-    template <typename T> class EdgeMap : public DynMapBase<Edge>
-    {
-      std::vector<T> container;
-
-    public:
-      typedef T ValueType;
-      typedef Edge KeyType;
-
-      EdgeMap(const SmartGraph &_G) :
-	DynMapBase<Edge>(_G), container(_G.maxEdgeId())
-      {
-	//FIXME: What if there are empty Id's?
-	//FIXME: Can I use 'this' in a constructor?
-	G->dyn_edge_maps.push_back(this);
-      }
-      EdgeMap(const SmartGraph &_G,const T &t) :
-	DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
-      {
-	G->dyn_edge_maps.push_back(this);
-      } 
-      EdgeMap(const EdgeMap<T> &m) :
- 	DynMapBase<Edge>(*m.G), container(m.container)
-      {
- 	G->dyn_edge_maps.push_back(this);
-      }
-
-      template<typename TT> friend class EdgeMap;
-
-      ///\todo It can copy between different types.
-      ///
-      template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
-	DynMapBase<Edge>(*m.G)
-      {
-	G->dyn_edge_maps.push_back(this);
-	typename std::vector<TT>::const_iterator i;
-	for(typename std::vector<TT>::const_iterator i=m.container.begin();
-	    i!=m.container.end();
-	    i++)
-	  container.push_back(*i);
-      }
-      ~EdgeMap()
-      {
-	if(G) {
-	  std::vector<DynMapBase<Edge>* >::iterator i;
-	  for(i=G->dyn_edge_maps.begin();
-	      i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
-	  //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
-	  //A better way to do that: (Is this really important?)
-	  if(*i==this) {
-	    *i=G->dyn_edge_maps.back();
-	    G->dyn_edge_maps.pop_back();
-	  }
-	}
-      }
-      
-      void add(const Edge k) 
-      {
-	if(k.n>=int(container.size())) container.resize(k.n+1);
-      }
-      void erase(const Edge) { }
-      
-      void set(Edge n, T a) { container[n.n]=a; }
-      //T get(Edge n) const { return container[n.n]; }
-      typename std::vector<T>::reference
-      operator[](Edge n) { return container[n.n]; }
-      typename std::vector<T>::const_reference
-      operator[](Edge n) const { return container[n.n]; }
-
-      ///\warning There is no safety check at all!
-      ///Using operator = between maps attached to different graph may
-      ///cause serious problem.
-      ///\todo Is this really so?
-      ///\todo It can copy between different types.
-      const EdgeMap<T>& operator=(const EdgeMap<T> &m)
-      {
-	container = m.container;
-	return *this;
-      }
-      template<typename TT>
-      const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
-      {
-	std::copy(m.container.begin(), m.container.end(), container.begin());
-	return *this;
-      }
-      
-      void update() {}    //Useless for DynMaps
-      void update(T a) {}  //Useless for DynMaps
-    };
-
-  };
-
-  ///Graph for bidirectional edges.
-
-  ///The purpose of this graph structure is to handle graphs
-  ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
-  ///of oppositely directed edges.
-  ///There is a new edge map type called
-  ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"
-  ///that complements this
-  ///feature by
-  ///storing shared values for the edge pairs. The usual
-  ///\ref GraphSkeleton::EdgeMap "EdgeMap"
-  ///can be used
-  ///as well.
-  ///
-  ///The oppositely directed edge can also be obtained easily
-  ///using \ref opposite.
-  ///\warning It shares the similarity with \ref SmartGraph that
-  ///it is not possible to delete edges or nodes from the graph.
-  //\sa \ref SmartGraph.
-
-  class SymSmartGraph : public SmartGraph
-  {
-  public:
-    template<typename T> class SymEdgeMap;
-    template<typename T> friend class SymEdgeMap;
-
-    SymSmartGraph() : SmartGraph() { }
-    SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
-    ///Adds a pair of oppositely directed edges to the graph.
-    Edge addEdge(Node u, Node v)
-    {
-      Edge e = SmartGraph::addEdge(u,v);
-      SmartGraph::addEdge(v,u);
-      return e;
-    }
-
-    ///The oppositely directed edge.
-
-    ///Returns the oppositely directed
-    ///pair of the edge \c e.
-    Edge opposite(Edge e) const
-    {
-      Edge f;
-      f.idref() = e.idref() - 2*(e.idref()%2) + 1;
-      return f;
-    }
-    
-    ///Common data storage for the edge pairs.
-
-    ///This map makes it possible to store data shared by the oppositely
-    ///directed pairs of edges.
-    template <typename T> class SymEdgeMap : public DynMapBase<Edge>
-    {
-      std::vector<T> container;
-      
-    public:
-      typedef T ValueType;
-      typedef Edge KeyType;
-
-      SymEdgeMap(const SymSmartGraph &_G) :
-	DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
-      {
-	static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.push_back(this);
-      }
-      SymEdgeMap(const SymSmartGraph &_G,const T &t) :
-	DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
-      {
-	G->dyn_edge_maps.push_back(this);
-      }
-
-      SymEdgeMap(const SymEdgeMap<T> &m) :
- 	DynMapBase<SymEdge>(*m.G), container(m.container)
-      {
- 	G->dyn_node_maps.push_back(this);
-      }
-
-      //      template<typename TT> friend class SymEdgeMap;
-
-      ///\todo It can copy between different types.
-      ///
-
-      template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :
-	DynMapBase<SymEdge>(*m.G)
-      {
-	G->dyn_node_maps.push_back(this);
-	typename std::vector<TT>::const_iterator i;
-	for(typename std::vector<TT>::const_iterator i=m.container.begin();
-	    i!=m.container.end();
-	    i++)
-	  container.push_back(*i);
-      }
- 
-      ~SymEdgeMap()
-      {
-	if(G) {
-	  std::vector<DynMapBase<Edge>* >::iterator i;
-	  for(i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.begin();
-	      i!=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.end()
-		&& *i!=this; ++i) ;
-	  //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
-	  //A better way to do that: (Is this really important?)
-	  if(*i==this) {
-	    *i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.back();
-	    static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.pop_back();
-	  }
-	}
-      }
-      
-      void add(const Edge k) 
-      {
-	if(!k.idref()%2&&k.idref()/2>=int(container.size()))
-	  container.resize(k.idref()/2+1);
-      }
-      void erase(const Edge k) { }
-      
-      void set(Edge n, T a) { container[n.idref()/2]=a; }
-      //T get(Edge n) const { return container[n.idref()/2]; }
-      typename std::vector<T>::reference
-      operator[](Edge n) { return container[n.idref()/2]; }
-      typename std::vector<T>::const_reference
-      operator[](Edge n) const { return container[n.idref()/2]; }
-
-      ///\warning There is no safety check at all!
-      ///Using operator = between maps attached to different graph may
-      ///cause serious problem.
-      ///\todo Is this really so?
-      ///\todo It can copy between different types.
-      const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
-      {
-	container = m.container;
-	return *this;
-      }
-      template<typename TT>
-      const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
-      {
-	std::copy(m.container.begin(), m.container.end(), container.begin());
-	return *this;
-      }
-      
-      void update() {}    //Useless for DynMaps
-      void update(T a) {}  //Useless for DynMaps
-
-    };
-
-  };
-  
-  /// @}  
-
-} //namespace hugo
-
-
-
-
-#endif //SMART_GRAPH_H
diff -r d8863141824d -r fb261e3a9a0f src/include/time_measure.h
--- a/src/include/time_measure.h	Thu May 06 09:26:23 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,208 +0,0 @@
-// -*- c++ -*-
-#ifndef HUGO_TIME_MEASURE_H
-#define HUGO_TIME_MEASURE_H
-
-///\ingroup misc
-///\file
-///\brief Tools for measuring cpu usage
-
-#include <sys/time.h>
-#include <sys/times.h>
-#include <fstream>
-#include <iostream>
-#include <unistd.h>
-
-namespace hugo {
-
-  /// \addtogroup misc
-  /// @{
-
-  /// A class to store (cpu)time instances.
-
-  /// This class stores five time values.
-  /// - a real time
-  /// - a user cpu time
-  /// - a system cpu time
-  /// - a user cpu time of children
-  /// - a system cpu time of children
-  ///
-  /// TimeStamp's can be added to or substracted from each other and
-  /// they can be pushed to a stream.
-  ///
-  /// In most cases, perhaps \ref Timer class is what you want to use instead.
-  ///
-  ///\author Alpar Juttner
-
-  class TimeStamp
-  {
-    tms ts;
-    double real_time;
-  
-  public:
-
-    tms &getTms() {return ts;}
-    const tms &getTms() const {return ts;}
-    ///Read the current time values of the process
-    void stamp()
-    {
-      timeval tv;
-      times(&ts);
-      gettimeofday(&tv, 0);real_time=tv.tv_sec+double(tv.tv_usec)/1e6;
-    }
-  
-    /// Constructor initializing with zero
-    TimeStamp()
-    { ts.tms_utime=ts.tms_stime=ts.tms_cutime=ts.tms_cstime=0; real_time=0;}
-    ///Constructor initializing with the current time values of the process
-    TimeStamp(void *) { stamp();}
-  
-    ///
-    TimeStamp &operator+=(const TimeStamp &b)
-    {
-      ts.tms_utime+=b.ts.tms_utime;
-      ts.tms_stime+=b.ts.tms_stime;
-      ts.tms_cutime+=b.ts.tms_cutime;
-      ts.tms_cstime+=b.ts.tms_cstime;
-      real_time+=b.real_time;
-      return *this;
-    }
-    ///
-    TimeStamp operator+(const TimeStamp &b) const
-    {
-      TimeStamp t(*this);
-      return t+=b;
-    }
-    ///
-    TimeStamp &operator-=(const TimeStamp &b)
-    {
-      ts.tms_utime-=b.ts.tms_utime;
-      ts.tms_stime-=b.ts.tms_stime;
-      ts.tms_cutime-=b.ts.tms_cutime;
-      ts.tms_cstime-=b.ts.tms_cstime;
-      real_time-=b.real_time;
-      return *this;
-    }
-    ///
-    TimeStamp operator-(const TimeStamp &b) const
-    {
-      TimeStamp t(*this);
-      return t-=b;
-    }
-
-    ///The time ellapsed since the last call of stamp()
-    TimeStamp ellapsed() const
-    {
-      TimeStamp t(NULL);
-      return t-*this;
-    }
-  
-    friend std::ostream& operator<<(std::ostream& os,const TimeStamp &t);
-  
-    ///Gives back the user time of the process
-    double getUserTime() const
-    {
-      return double(ts.tms_utime)/sysconf(_SC_CLK_TCK);
-    }
-    ///Gives back the system time of the process
-    double getSystemTime() const
-    {
-      return double(ts.tms_stime)/sysconf(_SC_CLK_TCK);
-    }
-    ///Gives back the user time of the process' children
-    double getCUserTime() const
-    {
-      return double(ts.tms_cutime)/sysconf(_SC_CLK_TCK);
-    }
-    ///Gives back the user time of the process' children
-    double getCSystemTime() const
-    {
-      return double(ts.tms_cstime)/sysconf(_SC_CLK_TCK);
-    }
-    ///Gives back the real time of the process
-    double getRealTime() const {return real_time;}
-  };
-
-  ///Class measuring the cpu time and real time usage of the process
-
-  ///Class measuring the cpu time and real time usage of the process.
-  ///It is quite easy-to-use, here is a short example.
-  ///\code
-  ///int main()
-  ///{
-  ///
-  ///  ...
-  ///
-  ///  Timer T();
-  ///  doSomething();
-  ///  cout << T;
-  ///  T.reset();
-  ///  doSomethingElse();
-  ///  cout << T;
-  ///
-  ///  ...
-  ///
-  ///}
-  ///\endcode
-  ///
-  ///\todo This shouldn't be Unix (Linux) specific.
-  ///
-  ///\author Alpar Juttner
-  class Timer
-  {
-    TimeStamp start_time;
-
-    void _reset() {start_time.stamp();}
-  
-  public: 
-    ///Constructor. It starts with zero time counters
-    Timer() {_reset();}
-
-    ///Computes the ellapsed time
-
-    ///This conversion computes the ellapsed time
-    ///since the construction of \c t or since
-    ///the last \c t.reset().
-    operator TimeStamp ()
-    {
-      TimeStamp t;
-      t.stamp();
-      return t-start_time;
-    }
-
-    ///Resets the time counters
-    TimeStamp reset()
-    {
-      TimeStamp t(start_time);
-      _reset();
-      return start_time-t;
-    }
-  };
-
-  ///Prints the time counters
-
-  ///Prints the time counters in the following form:
-  ///
-  /// <tt>u: XX.XXs s: XX.XXs cu: XX.XXs cs: XX.XXs real: XX.XXs</tt>
-  ///
-  /// where the values are the
-  /// \li \c u: user cpu time,
-  /// \li \c s: system cpu time,
-  /// \li \c cu: user cpu time of children,
-  /// \li \c cs: system cpu time of children,
-  /// \li \c real: real time.
-  inline std::ostream& operator<<(std::ostream& os,const TimeStamp &t)
-  {
-    long cls = sysconf(_SC_CLK_TCK);
-    os << "u: " << double(t.getTms().tms_utime)/cls <<
-      "s, s: " << double(t.getTms().tms_stime)/cls <<
-      "s, cu: " << double(t.getTms().tms_cutime)/cls <<
-      "s, cs: " << double(t.getTms().tms_cstime)/cls <<
-      "s, real: " << t.getRealTime() << "s";
-    return os;
-  }
-
-  /// @}  
-
-} //namespace hugo
-
-#endif //HUGO_TIME_MEASURE_H
diff -r d8863141824d -r fb261e3a9a0f src/include/unionfind.h
--- a/src/include/unionfind.h	Thu May 06 09:26:23 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,700 +0,0 @@
-// -*- c++ -*- //
-#ifndef HUGO_UNION_FIND_H
-#define HUGO_UNION_FIND_H
-
-//!\ingroup auxdat
-//!\file
-//!\brief Union-Find data structures.
-
-
-#include <vector>
-#include <list>
-#include <utility>
-#include <algorithm>
-
-#include <invalid.h>
-
-namespace hugo {
-
-  //! \addtogroup 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 compresson.
-   * 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.
-   *
-   * \pre The elements are automatically added only if the map 
-   * given to the constructor was filled with -1's. Otherwise you
-   * need to add all the elements by the \ref insert() method.
-   */
-
-  template <typename T, typename TIntMap>
-  class UnionFind {
-    
-  public:
-    typedef T ElementType;
-    typedef std::pair<int,int> PairType;
-
-  private:
-    std::vector<PairType> data;
-    TIntMap& map;
-
-  public:
-    UnionFind(TIntMap& m) : map(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(T a)
-    {
-      int comp0 = map[a];
-      if (comp0 < 0) {
-	return insert(a);
-      }
-      int comp = comp0;
-      int next;
-      while ( (next = data[comp].first) != comp) {
-	comp = next;
-      }
-      while ( (next = data[comp0].first) != comp) {
-	data[comp0].first = comp;
-	comp0 = next;
-      }
-
-      return comp;
-    }
-
-    /**
-     * \brief Insert a new element into the structure.
-     *
-     * This method inserts a new element into the data structure. 
-     *
-     * It is not required to use this method:
-     * if the map given to the constructor was filled 
-     * with -1's then it is called automatically
-     * on the first \ref find or \ref join.
-     *
-     * The method returns the index of the new component.
-     */
-
-    int insert(T a)
-    {
-      int n = data.size();
-      data.push_back(std::make_pair(n, 1));
-      map.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 elemenent \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(T a, T b)
-    {
-      int ca = find(a);
-      int cb = find(b);
-
-      if ( ca == cb ) 
-	return false;
-
-      if ( data[ca].second > data[cb].second ) {
-	data[cb].first = ca;
-	data[ca].second += data[cb].second;
-      }
-      else {
-	data[ca].first = cb;
-	data[cb].second += data[ca].second;
-      }
-      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(T a)
-    {
-      int ca = find(a);
-      return data[ca].second;
-    }
-
-  };
-
-
-
-
-  /*******************************************************/
-
-
-#ifdef DEVELOPMENT_DOCS
-
-  /**
-   * \brief The auxiliary class for the \ref UnionFindEnum class.
-   *
-   * In the \ref UnionFindEnum class all components are represented as
-   * a std::list. 
-   * Items of these lists are UnionFindEnumItem structures.
-   *
-   * The class has four fields:
-   *  - T me - the actual element 
-   *  - IIter parent - the parent of the element in the union-find structure
-   *  - int size - the size of the component of the element. 
-   *            Only valid if the element
-   *            is the leader of the component.
-   *  - CIter my_class - pointer into the list of components 
-   *            pointing to the component of the element.
-   *            Only valid if the element is the leader of the component.
-   */
-
-#endif
-
-  template <typename T>
-  struct UnionFindEnumItem {
-
-    typedef std::list<UnionFindEnumItem> ItemList;
-    typedef std::list<ItemList> ClassList;
-    typedef typename ItemList::iterator IIter;
-    typedef typename ClassList::iterator CIter;
-
-    T me;
-    IIter parent;
-    int size;
-    CIter my_class;
-
-    UnionFindEnumItem() {}
-    UnionFindEnumItem(const T &_me, CIter _my_class): 
-      me(_me), size(1), my_class(_my_class) {}
-  };
-
-
-  /**
-   * \brief A \e Union-Find data structure implementation which
-   * is able to enumerate the components.
-   *
-   * The class implements an \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 compresson.
-   *
-   * \pre You
-   * need to add all the elements by the \ref insert() method.
-   */
-
-
-  template <typename T, template <typename Item> class Map>
-  class UnionFindEnum {
-
-    typedef std::list<UnionFindEnumItem<T> > ItemList;
-    typedef std::list<ItemList> ClassList;
-    typedef typename ItemList::iterator IIter;
-    typedef typename ItemList::const_iterator IcIter;
-    typedef typename ClassList::iterator CIter;
-    typedef typename ClassList::const_iterator CcIter;
-
-  public:
-    typedef T ElementType;
-    typedef UnionFindEnumItem<T> ItemType;
-    typedef Map< IIter > MapType;
-
-  private:
-    MapType& m;
-    ClassList classes;
-
-    IIter _find(IIter a) const {
-      IIter comp = a;
-      IIter next;
-      while( (next = comp->parent) != comp ) {
-	comp = next;
-      }
-
-      IIter comp1 = a;
-      while( (next = comp1->parent) != comp ) {
-	comp1->parent = comp->parent;
-	comp1 = next;
-      }
-      return comp;
-    }
-
-  public:
-    UnionFindEnum(MapType& _m) : m(_m) {}
-
-
-    /**
-     * \brief Insert the given element into a new component.
-     *
-     * This method creates a new component consisting only of the
-     * given element.
-     */
-
-    void insert(const T &a)
-    {
-
-
-      classes.push_back(ItemList());
-      CIter aclass = classes.end();
-      --aclass;
-
-      ItemList &alist = *aclass;
-      alist.push_back(ItemType(a, aclass));
-      IIter ai = alist.begin();
-
-      ai->parent = ai;
-      m.set(a, ai);
-
-    }
-
-    /**
-     * \brief Insert the given element into the component of the others.
-     *
-     * This methods insert the element \e a into the component of the
-     * element \e comp. 
-     */
-
-    void insert(const T &a, const T &comp) {
-      
-      IIter clit = _find(m[comp]);
-      ItemList &c = *clit->my_class;
-      c.push_back(ItemType(a,0));
-      IIter ai = c.end();
-      --ai;
-      ai->parent = clit;
-      m.set(a, ai);
-      ++clit->size;
-    }
-
-
-    /**
-     * \brief Find the leader of the component of the given element.
-     *
-     * The method returns the leader of the component of the given element.
-     */
-
-    T find(const T &a) const {
-      return _find(m[a])->me;
-    }
-
-
-    /**
-     * \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 elemenent \e a and component of
-     * element \e b. If \e a and \e b are in the same component then
-     * returns false else returns true.
-     */
-
-    bool join(T a, T b) {
-
-      IIter ca = _find(m[a]);
-      IIter cb = _find(m[b]);
-
-      if ( ca == cb ) {
-	return false;
-      }
-
-      if ( ca->size > cb->size ) {
-
-	cb->parent = ca->parent;
-	ca->size += cb->size;
-	
-	ItemList &alist = *ca->my_class;
-	alist.splice(alist.end(),*cb->my_class);
-
-	classes.erase(cb->my_class);
-	cb->my_class = 0;
-      }
-      else {
-
-	ca->parent = cb->parent;
-	cb->size += ca->size;
-	
-	ItemList &blist = *cb->my_class;
-	blist.splice(blist.end(),*ca->my_class);
-
-	classes.erase(ca->my_class);
-	ca->my_class = 0;
-      }
-
-      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 T &a) const {
-      return _find(m[a])->size;
-    }
-
-
-    /**
-     * \brief Split up the component of the element. 
-     *
-     * Splitting the component of the element into sigleton
-     * components (component of size one).
-     */
-
-    void split(const T &a) {
-
-      IIter ca = _find(m[a]);
- 
-      if ( ca->size == 1 )
-	return;
-      
-      CIter aclass = ca->my_class;
-
-      for(IIter curr = ca; ++curr != aclass->end(); curr=ca) {
-	classes.push_back(ItemList());
-	CIter nl = --classes.end();
-	nl->splice(nl->end(), *aclass, curr);
-
-	curr->size=1;
-	curr->parent=curr;
-	curr->my_class = nl;
-      }
-
-      ca->size=1;
-      return;
-    }
-
-
-    /**
-     * \brief Set the given element to the leader element of its component.
-     *
-     * Set the given element to the leader element of its component.
-     */
-
-    void makeRep(const T &a) {
-
-      IIter ia = m[a];
-      IIter la = _find(ia);
-      if (la == ia) return;
-
-      ia->my_class = la->my_class;
-      la->my_class = 0;
-
-      ia->size = la->size;
-
-      CIter l = ia->my_class;
-      l->splice(l->begin(),*l,ia);
-
-      ia->parent = ia;
-      la->parent = ia;
-    }
-
-    /**
-     * \brief Move the given element to an other component.
-     *
-     * This method moves the element \e a from its component
-     * to the component of \e comp.
-     * If \e a and \e comp are in the same component then
-     * it returns false otherwise it returns true.
-     */
-
-    bool move(const T &a, const T &comp) {
-
-      IIter ai = m[a];
-      IIter lai = _find(ai);
-      IIter clit = _find(m[comp]);
-
-      if (lai == clit)
-	return false;
-
-      ItemList &c = *clit->my_class;
-
-      bool is_leader = (lai == ai);
-      bool singleton = false;
-
-      if (is_leader) {
-	++lai;
-      }
-
-      c.splice(c.end(), *lai->my_class, ai);
-
-      if (is_leader) {
-	if (ai->size == 1) {
-	  classes.erase(ai->my_class);
-	  singleton = true;
-	}
-	else {
-	  lai->size = ai->size; 
-	  lai->my_class = ai->my_class;	
-	}
-      }
-      if (!singleton) {
-	for (IIter i = lai; i != lai->my_class->end(); ++i)
-	  i->parent = lai;
-	--lai->size;
-      }
-
-      ai->parent = clit;
-      ai->my_class = 0;
-      ++clit->size;
-
-      return true;
-    }
-
-
-    /**
-     * \brief Remove the given element from the structure.
-     *
-     * Remove 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.
-     */
-    void erase(const T &a) {
-
-      IIter ma = m[a];
-      if (ma == 0) return;
-
-      IIter la = _find(ma);
-      if (la == ma) {
-	if (ma -> size == 1){
-	  classes.erase(ma->my_class);
-	  m.set(a,0);
-	  return;
-	}
-	++la;
-	la->size = ma->size; 
-	la->my_class = ma->my_class;	
-      }
-
-      for (IIter i = la; i != la->my_class->end(); ++i) {
-	i->parent = la;
-      }
-
-      la->size--;
-      la->my_class->erase(ma);
-      m.set(a,0);
-    }
-
-    /**
-     * \brief Removes the component of the given element from the structure.
-     *
-     * Removes the component of the given element from the structure.
-     */
-
-    void eraseClass(const T &a) {
-      IIter ma = m[a];
-      if (ma == 0) return;
-#     ifdef DEBUG
-      CIter c = _find(ma)->my_class;
-      for (IIter i=c->begin(); i!=c->end(); ++i)
-	m.set(i->me, 0);
-#     endif
-      classes.erase(_find(ma)->my_class);
-    }
-
-
-    class ClassIt {
-      friend class UnionFindEnum;
-
-      CcIter i;
-    public:
-      ClassIt(Invalid): i(0) {}
-      ClassIt() {}
-      
-      operator const T& () const { 
-	ItemList const &ll = *i;
-	return (ll.begin())->me; }
-      bool operator == (ClassIt it) const {
-	return (i == it.i);
-      }
-      bool operator != (ClassIt it) const {
-	return (i != it.i);
-      }
-      bool operator < (ClassIt it) const {
-	return (i < it.i);
-      }
-
-      bool valid() const { return i != 0; }
-    private:
-      void first(const ClassList &l) { i = l.begin(); validate(l); }
-      void next(const ClassList &l) {
-	++i; 
-	validate(l);
-      }
-      void validate(const ClassList &l) {
-	if ( i == l.end() ) 
-	  i = 0;
-      }
-    };
-
-    /**
-     * \brief Sets the iterator to point to the first component.
-     * 
-     * Sets the iterator to point to the first component.
-     *
-     * With the \ref first, \ref valid and \ref next methods you can
-     * iterate through the components. For example:
-     * \code
-     * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
-     * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
-     * UnionFindEnum<Graph::Node, Graph::NodeMap>::ClassIt iter;
-     *  for (U.first(iter); U.valid(iter); U.next(iter)) {
-     *    // iter is convertible to Graph::Node
-     *    cout << iter << endl;
-     *  }
-     * \endcode
-     */
-
-    ClassIt& first(ClassIt& it) const {
-      it.first(classes);
-      return it;
-    }
-
-    /**
-     * \brief Returns whether the iterator is valid.
-     *
-     * Returns whether the iterator is valid.
-     *
-     * With the \ref first, \ref valid and \ref next methods you can
-     * iterate through the components. See the example here: \ref first.
-     */
-
-    bool valid(ClassIt const &it) const {
-      return it.valid(); 
-    }
-
-    /**
-     * \brief Steps the iterator to the next component. 
-     *
-     * Steps the iterator to the next component.
-     *
-     * With the \ref first, \ref valid and \ref next methods you can
-     * iterate through the components. See the example here: \ref first.
-     */
-
-    ClassIt& next(ClassIt& it) const {
-      it.next(classes);
-      return it;
-    }
-
-
-    class ItemIt {
-      friend class UnionFindEnum;
-
-      IcIter i;
-      const ItemList *l;
-    public:
-      ItemIt(Invalid): i(0) {}
-      ItemIt() {}
-      
-      operator const T& () const { return i->me; }
-      bool operator == (ItemIt it) const {
-	return (i == it.i);
-      }
-      bool operator != (ItemIt it) const {
-	return (i != it.i);
-      }
-      bool operator < (ItemIt it) const {
-	return (i < it.i);
-      }
-
-      bool valid() const { return i != 0; }
-    private:
-      void first(const ItemList &il) { l=&il; i = l->begin(); validate(); }
-      void next() {
-	++i; 
-	validate();
-      }
-      void validate() {
-	if ( i == l->end() ) 
-	  i = 0;
-      }
-    };
-
-
-
-    /**
-     * \brief Sets the iterator to point to the first element of the component.
-     * 
-     * \anchor first2 
-     * Sets the iterator to point to the first element of the component.
-     *
-     * With the \ref first2 "first", \ref valid2 "valid" 
-     * and \ref next2 "next" methods you can
-     * iterate through the elements of a component. For example
-     * (iterating through the component of the node \e node):
-     * \code
-     * Graph::Node node = ...;
-     * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
-     * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
-     * UnionFindEnum<Graph::Node, Graph::NodeMap>::ItemIt iiter;
-     *   for (U.first(iiter, node); U.valid(iiter); U.next(iiter)) {
-     *     // iiter is convertible to Graph::Node
-     *     cout << iiter << endl;
-     *   }
-     * \endcode
-     */
-    
-    ItemIt& first(ItemIt& it, const T& a) const {
-      it.first( * _find(m[a])->my_class );
-      return it;
-    }
-
-    /**
-     * \brief Returns whether the iterator is valid.
-     *
-     * \anchor valid2
-     * Returns whether the iterator is valid.
-     *
-     * With the \ref first2 "first", \ref valid2 "valid" 
-     * and \ref next2 "next" methods you can
-     * iterate through the elements of a component.
-     * See the example here: \ref first2 "first".
-     */
-
-    bool valid(ItemIt const &it) const {
-      return it.valid(); 
-    }
-
-    /**
-     * \brief Steps the iterator to the next component. 
-     *
-     * \anchor next2
-     * Steps the iterator to the next component.
-     *
-     * With the \ref first2 "first", \ref valid2 "valid" 
-     * and \ref next2 "next" methods you can
-     * iterate through the elements of a component.
-     * See the example here: \ref first2 "first".
-     */
-
-    ItemIt& next(ItemIt& it) const {
-      it.next();
-      return it;
-    }
-    
-  };
-
-
-  //! @}
-
-} //namespace hugo
-
-#endif //HUGO_UNION_FIND_H
diff -r d8863141824d -r fb261e3a9a0f src/include/xy.h
--- a/src/include/xy.h	Thu May 06 09:26:23 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,227 +0,0 @@
-// -*- c++ -*-
-#ifndef HUGO_XY_H
-#define HUGO_XY_H
-
-#include <iostream>
-
-///\ingroup misc
-///\file
-///\brief A simple two dimensional vector and a bounding box implementation 
-///
-/// The class \ref hugo::xy "xy" implements
-///a two dimensional vector with the usual
-/// operations.
-///
-/// The class \ref hugo::BoundingBox "BoundingBox" can be used to determine
-/// the rectangular bounding box a set of \ref hugo::xy "xy"'s.
-///
-///\author Attila Bernath
-
-
-namespace hugo {
-
-  /// \addtogroup misc
-  /// @{
-
-  /// A two dimensional vector (plainvector) implementation
-
-  /// A two dimensional vector (plainvector) implementation
-  ///with the usual vector
-  /// operators.
-  ///
-  ///\author Attila Bernath
-  template<typename T>
-    class xy {
-
-    public:
-
-      T x,y;     
-      
-      ///Default constructor: both coordinates become 0
-      xy() : x(0), y(0) {}
-
-      ///Constructing the instance from coordinates
-      xy(T a, T b) : x(a), y(b) { }
-
-
-      ///Gives back the square of the norm of the vector
-      T normSquare(){
-	return x*x+y*y;
-      };
-  
-      ///Increments the left hand side by u
-      xy<T>& operator +=(const xy<T>& u){
-	x += u.x;
-	y += u.y;
-	return *this;
-      };
-  
-      ///Decrements the left hand side by u
-      xy<T>& operator -=(const xy<T>& u){
-	x -= u.x;
-	y -= u.y;
-	return *this;
-      };
-
-      ///Multiplying the left hand side with a scalar
-      xy<T>& operator *=(const T &u){
-	x *= u;
-	y *= u;
-	return *this;
-      };
-
-      ///Dividing the left hand side by a scalar
-      xy<T>& operator /=(const T &u){
-	x /= u;
-	y /= u;
-	return *this;
-      };
-  
-      ///Returns the scalar product of two vectors
-      T operator *(const xy<T>& u){
-	return x*u.x+y*u.y;
-      };
-  
-      ///Returns the sum of two vectors
-      xy<T> operator+(const xy<T> &u) const {
-	xy<T> b=*this;
-	return b+=u;
-      };
-
-      ///Returns the difference of two vectors
-      xy<T> operator-(const xy<T> &u) const {
-	xy<T> b=*this;
-	return b-=u;
-      };
-
-      ///Returns a vector multiplied by a scalar
-      xy<T> operator*(const T &u) const {
-	xy<T> b=*this;
-	return b*=u;
-      };
-
-      ///Returns a vector divided by a scalar
-      xy<T> operator/(const T &u) const {
-	xy<T> b=*this;
-	return b/=u;
-      };
-
-      ///Testing equality
-      bool operator==(const xy<T> &u){
-	return (x==u.x) && (y==u.y);
-      };
-
-      ///Testing inequality
-      bool operator!=(xy u){
-	return  (x!=u.x) || (y!=u.y);
-      };
-
-    };
-
-  ///Reading a plainvector from a stream
-  template<typename T>
-  inline
-  std::istream& operator>>(std::istream &is, xy<T> &z)
-  {
-
-    is >> z.x >> z.y;
-    return is;
-  }
-
-  ///Outputting a plainvector to a stream
-  template<typename T>
-  inline
-  std::ostream& operator<<(std::ostream &os, xy<T> z)
-  {
-    os << "(" << z.x << ", " << z.y << ")";
-    return os;
-  }
-
-
-  /// A class to calculate or store the bounding box of plainvectors.
-
-  /// A class to calculate or store the bounding box of plainvectors.
-  ///
-  ///\author Attila Bernath
-  template<typename T>
-    class BoundingBox {
-      xy<T> bottom_left, top_right;
-      bool _empty;
-    public:
-      
-      ///Default constructor: an empty bounding box
-      BoundingBox() { _empty = true; }
-
-      ///Constructing the instance from one point
-      BoundingBox(xy<T> a) { bottom_left=top_right=a; _empty = false; }
-
-      ///Is there any point added
-      bool empty() const {
-	return _empty;
-      }
-
-      ///Gives back the bottom left corner (if the bounding box is empty, then the return value is not defined) 
-      xy<T> bottomLeft() const {
-	return bottom_left;
-      };
-
-      ///Gives back the top right corner (if the bounding box is empty, then the return value is not defined) 
-      xy<T> topRight() const {
-	return top_right;
-      };
-
-      ///Checks whether a point is inside a bounding box
-      bool inside(const xy<T>& u){
-	if (_empty)
-	  return false;
-	else{
-	  return ((u.x-bottom_left.x)*(top_right.x-u.x) >= 0 &&
-		  (u.y-bottom_left.y)*(top_right.y-u.y) >= 0 );
-	}
-      }
-  
-      ///Increments a bounding box with a point
-      BoundingBox& operator +=(const xy<T>& u){
-	if (_empty){
-	  bottom_left=top_right=u;
-	  _empty = false;
-	}
-	else{
-	  if (bottom_left.x > u.x) bottom_left.x = u.x;
-	  if (bottom_left.y > u.y) bottom_left.y = u.y;
-	  if (top_right.x < u.x) top_right.x = u.x;
-	  if (top_right.y < u.y) top_right.y = u.y;
-	}
-	return *this;
-      };
-  
-      ///Sums a bounding box and a point
-      BoundingBox operator +(const xy<T>& u){
-	BoundingBox b = *this;
-	return b += u;
-      };
-
-      ///Increments a bounding box with an other bounding box
-      BoundingBox& operator +=(const BoundingBox &u){
-	if ( !u.empty() ){
-	  *this += u.bottomLeft();
-	  *this += u.topRight();
-	}
-	return *this;
-      };
-  
-      ///Sums two bounding boxes
-      BoundingBox operator +(const BoundingBox& u){
-	BoundingBox b = *this;
-	return b += u;
-      };
-
-    };//class Boundingbox
-
-
-  /// @}
-
-
-} //namespace hugo
-
-#endif //HUGO_XY_H