# HG changeset patch
# User alpar
# Date 1080548178 0
# Node ID f45703336699802fe5371d0ed8d2b5bac34eb72c
# Parent  35c2543f45fb4d83ddda3f425afa5ceb34cffe31
Move invalid.h smart_graph.h maps.h emptygraph.h to include

diff -r 35c2543f45fb -r f45703336699 doc/Doxyfile
--- a/doc/Doxyfile	Fri Mar 26 23:34:45 2004 +0000
+++ b/doc/Doxyfile	Mon Mar 29 08:16:18 2004 +0000
@@ -391,10 +391,10 @@
 # directories like "/usr/src/myproject". Separate the files or directories 
 # with spaces.
 
-INPUT                  = ../src/demo/alpar/emptygraph.h \
-                         ../src/doxy/invalid.h \
-                         ../src/demo/alpar/smart_graph.h \
-                         ../src/demo/alpar/mapskeleton.h \
+INPUT                  = ../src/include/skeletons/graph.h \
+                         ../src/include/invalid.h \
+                         ../src/include/smart_graph.h \
+                         ../src/include/skeletons/maps.h \
                          ../src/demo/alpar/dijkstra/dijkstra.h \
                          ../src/demo/alpar/dijkstra/bin_heap.hh \
                          ../src/demo/alpar/dijkstra/fib_heap.h \
diff -r 35c2543f45fb -r f45703336699 src/include/graph.h
--- a/src/include/graph.h	Fri Mar 26 23:34:45 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,493 +0,0 @@
-// -*-mode: c++; -*-
-#ifndef __GRAPH_H_
-#define __GRAPH_H_
-
-//inline void *operator new(size_t s, void *p) { return p; }
-#include <new>
-#include <vector>
-
-namespace NEGRO 
-{
-  using namespace std;
-  
-#include "oldgraph.h"
-  
-  template <class N, class E> class Graph : protected OldGraph<N,E>
-  {
-  public:
-    typedef E EdgeType;
-    typedef N NodeType;
-    
-    class EdgeIt
-    {
-    public:
-      NEGRO::EdgePoint e;
-      bool valid() { return e; }
-    };
-    
-    class InEdgeIt : public EdgeIt {};
-    class OutEdgeIt : public EdgeIt {};
-    class BiEdgeIt : public EdgeIt {};
-    class SymEdgeIt : public EdgeIt {};
-    
-    typedef int NodeIt;
-    
-    typedef NodeIt EachNodeIt;
-    
-    class NodeIterator;
-    
-    class EdgeIterator;
-    class InEdgeIterator;
-    class OutEdgeIterator;
-    class BiEdgeIterator;
-    class SymEdgeIterator;
-    class AllEdgeIterator;
-    
-    class FirstAnythingTypeNode; //Required by the unified First() function.
-
-    friend class NodeIterator;
-    friend class EdgeIterator;
-    friend class InEdgeIterator;
-    friend class OutEdgeIterator;
-    friend class BiEdgeIterator;
-    friend class SymEdgeIterator;
-    friend class EachEdgeIterator;
-    
-    class NodeIterator
-    {
-      Graph<N,E> *G;  //operator*() miatt kell!!!
-      int n;     //nem kellene, ha itt mutato lenne!!
-    public:    
-      
-      NodeIterator() {;} 
-      NodeIterator(Graph<N,E> &Gr)//'const Graph<N,E> &G' would be wrong.
-      {G=&Gr;n=Gr.OldGraph<N,E>::FirstNode();} 
-      NodeIterator(const NodeIterator &i) {G=i.G;n=i.n;}
-      
-      NodeIterator &goNext() { n=G->NextNode(n); return *this;}
-      NodeIterator next() const { return NodeIterator(*this).goNext();}
-      NodeIterator &operator++() { return goNext();} 
-      NodeIterator operator++(int)
-      {NodeIterator tmp(*this); goNext(); return tmp;}
-      bool valid() { return n!=INVALID; }
-      
-      N &operator*() const { return G->Data(n); }
-      N *operator->() const { return &G->Data(n); }
-      
-      bool operator==(const NodeIterator &i) const {return n==i.n;}
-      bool operator!=(const NodeIterator &i) const {return n!=i.n;}
-      
-      int index() const { return n; } //If the nodes are indexable 
-      friend class Graph;
-      friend class EdgeIterator;
-      friend class InEdgeIterator;
-      friend class OutEdgeIterator;
-      friend class BiEdgeIterator;
-      friend class SymEdgeIterator;
-      friend class EachEdgeIterator;
-      friend class FirstAnythingTypeNode;
-
-      //Nem kellene egy:
-      //      static NodeIterator &GetInvalid();  ?
-    };
-    
-    class EdgeIterator
-    {
-      
-      Graph<N,E> *G; //Itt baj van!!!!! operator*() miatt kell!
-      //Ez csak kicsit baj, de:
-      // Meg a From() es To() miatt!!!!!!!!!!
-      
-      NEGRO::EdgeIt e;
-      
-    public:
-      EdgeIterator() {;} //Kell inicializalni? (Nem)
-      EdgeIterator(const EdgeIterator &i) {G=i.G;e=i.e;}
-      
-      // Lehet, hogy ez a ketto nem kell!!!
-      
-      NodeIterator tail() const {NodeIterator i;i.G=G;i.n=e->From();return i;}
-      NodeIterator head() const {NodeIterator i;i.G=G;i.n=e->To();return i;}
-      NodeIterator opposite(const NodeIterator &n) const
-      {return n==tail()?head():tail();}
-      
-      bool valid() {return e;}
-      E &operator*() const { return G->Data(e); }
-      E *operator->() const { return &G->Data(e); }
-      
-      //operator const OutEdgeIterator ();
-      //operator const InEdgeIterator ();
-      //operator const BiEdgeIterator ();
-      //operator const SymEdgeIterator(); //Ez kerdeses, mit csinal
-      
-      bool operator==(const EdgeIterator &i) const {return e==i.e;}
-      bool operator!=(const EdgeIterator &i) const {return e!=i.e;}
-       
-      int Index() const {return e->index.block*EDGE_BLOCK_SIZE+e->index.index;}
-      //If the edges are indexable 
-
-      friend class Graph;
-      friend class InEdgeIterator;
-      friend class OutEdgeIterator;
-      friend class BiEdgeIterator;
-      friend class SymEdgeIterator;
-      friend class EachEdgeIterator;
-    };
-    
-    class BiEdgeIterator : public EdgeIterator
-    {
-    public:
-      BiEdgeIterator &goNextIn()  { e=e->NextIn(); return *this;}
-      BiEdgeIterator &goNextOut() { e=e->NextOut(); return *this;}
-      BiEdgeIterator nextIn() const  {return BiEdgeIterator(*this).goNextIn();}
-      BiEdgeIterator nextOut() const {return BiEdgeIterator(*this).goNextOut();}
-      
-      operator InEdgeIterator ()
-      {InEdgeIterator i; i.G=G;i.e=e;return i;}
-      operator OutEdgeIterator ()
-      {OutEdgeIterator i; i.G=G;i.e=e;return i;}
-      //operator const SymEdgeIterator ()
-      
-      friend class Graph;
-    };
-    
-    class InEdgeIterator : public EdgeIterator
-    //Ne a BiEdgeIterator-bol szarmazzon?
-    {
-    public:
-      InEdgeIterator() {}
-      InEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n)
-      { G=&Gr; e=Gr.OldGraph<N,E>::FirstIn(n.n);}
-
-      InEdgeIterator &GoNext() { e=e->NextIn(); return *this;}
-      InEdgeIterator Next() const {return InEdgeIterator(*this).GoNext();}
-      InEdgeIterator &operator++() { return GoNext();}
-      InEdgeIterator operator++(int)
-      {InEdgeIterator tmp(*this); GoNext(); return tmp;}
-      
-      operator const OutEdgeIterator ()
-      {OutEdgeIterator i; i.G=G;i.e=e;return i;}
-      operator const BiEdgeIterator ()
-      {EdgeIterator i; i.G=G;i.e=e;return i;}
-      //      operator const SymEdgeIterator ();
-      
-      NodeIterator Anode() const {return To();}
-      NodeIterator Bnode() const {return From();}
-      
-      friend class Graph;
-    };
-    
-    class OutEdgeIterator : public EdgeIterator
-    {
-    public:
-      OutEdgeIterator() {}
-      OutEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n)
-      { G=&Gr; e=Gr.OldGraph<N,E>::FirstOut(n.n);}
-
-      OutEdgeIterator &goNext() { e=e->NextOut(); return *this;}
-      OutEdgeIterator next() const {return OutEdgeIterator(*this).goNext();}
-      OutEdgeIterator &operator++() { return goNext();}
-      OutEdgeIterator operator++(int)
-      {OutEdgeIterator tmp(*this); goNext(); return tmp;}
-      
-      NodeIterator aNode() const {return tail();}
-      NodeIterator bNode() const {return head();}
-      
-      operator const InEdgeIterator ()
-      {InEdgeIterator i; i.G=G;i.e=e;return i;}
-      operator const BiEdgeIterator ()
-      {BiEdgeIterator i; i.G=G;i.e=e;return i;}
-      //operator const SymEdgeIterator(); 
-      
-      friend class Graph;
-    };
-    
-    class SymEdgeIterator : public EdgeIterator
-    {
-      NodeIterator n;  // Itt ketszer van a G
-      
-    public:
-      SymEdgeIterator() {}
-      SymEdgeIterator(Graph<N,E> &Gr,const NodeIterator &nn)
-      { G=&Gr; n=nn; e=Gr.OldGraph<N,E>::FirstEdge(nn.n); }
-
-      SymEdgeIterator &goNext() { e=G->NextEdge(n.n,e); return *this;}
-      SymEdgeIterator next() const {return SymEdgeIterator(*this).goNext();}
-      SymEdgeIterator &operator++() { return goNext();}
-      SymEdgeIterator operator++(int)
-      {SymEdgeIterator tmp(*this); goNext(); return tmp;}
-      
-      NodeIterator aNode() const {return n;}
-      NodeIterator bNode() const {return n.n==tail().n?head():tail();}
-      
-      operator const InEdgeIterator ()
-      {InEdgeIterator i; i.G=G;i.e=e;return i;}
-      operator const OutEdgeIterator ()
-      {OutEdgeIterator i; i.G=G;i.e=e;return i;}
-      operator const BiEdgeIterator ()
-      {BiEdgeIterator i; i.G=G;i.e=e;return i;}
-      
-      friend class Graph;
-    };
-    
-    class EachEdgeIterator : public EdgeIterator
-    {
-      NodeIterator n;  // Itt ketszer van a G
-      
-    public:
-      EachEdgeIterator() {}
-      EachEdgeIterator(Graph<N,E> &Gr) : n(Gr)
-      {
-	e=n.valid()?Gr.OldGraph<N,E>::FirstOut(n.n):NULL;
-      }  
-
-      EachEdgeIterator &goNext()
-      {
-	e=e->NextOut();
-	if(!e && (++n).valid()) e=G->OldGraph<N,E>::FirstOut(n.n);
-	return *this;
-      }
-      EachEdgeIterator next() const {return EachEdgeIterator(*this).goNext();}
-      EachEdgeIterator &operator++() { return goNext();}
-      EachEdgeIterator operator++(int)
-	{EachEdgeIterator tmp(*this); goNext(); return tmp;}
-      
-      
-      NodeIterator aNode() const {return n;}
-      NodeIterator bNode() const {return n.n==tail().n?head():tail();}
-      
-      operator const EdgeIterator ()
-      {EdgeIterator i; i.G=G;i.e=e;return i;}
-      operator const InEdgeIterator ()
-      {InEdgeIterator i; i.G=G;i.e=e;return i;}
-      operator const OutEdgeIterator ()
-      {OutEdgeIterator i; i.G=G;i.e=e;return i;}
-      operator const BiEdgeIterator ()
-      {BiEdgeIterator i; i.G=G;i.e=e;return i;}
-      
-      friend class Graph;
-    };
-    
-    typedef NodeIterator DeletingNodeIterator;
-    typedef EdgeIterator DeletingEdgeIterator;
-    typedef BiEdgeIterator DeletingBiEdgeIterator;
-    typedef OutEdgeIterator DeletingOutEdgeIterator;
-    typedef InEdgeIterator DeletingInEdgeIterator;
-    typedef SymEdgeIterator DeletingSymEdgeIterator;
-    
-    const NodeIterator firstNode()
-    {
-      NodeIterator i;
-      i.G=this;i.n=OldGraph<N,E>::FirstNode();
-      return i;
-    }
-    
-    void getFirst(NodeIt &p)   { p=OldGraph<N,E>::FirstNode(); }
-    
-    void getFirst(InEdgeIt &p,const NodeIt &n)
-    { p=OldGraph<N,E>::FirstIn(n); }
-    void getFirst(OutEdgeIt &p,const NodeIt &n)
-    { p=OldGraph<N,E>::FirstOut(n); }
-    void getFirst(SymEdgeIt &p,const NodeIt &n)
-    { p=OldGraph<N,E>::FirstEdge(n); }
-    void getFirst(EdgeIt &p) //Vegigmegy mindenen
-    { p.e=nodeNum()?OldGraph<N,E>::FirstOut(OldGraph<N,E>::FirstNode()):NULL;}
-
-    void getFirst(NodeIterator &i) { i.G=this;i.n=OldGraph<N,E>::FirstNode();}
-    
-    void getFirst(InEdgeIterator &i,const NodeIterator &n)
-    { i.G=this;i.e=OldGraph<N,E>::FirstIn(n.n); }
-    void getFirst(OutEdgeIterator &i,const NodeIterator &n)
-    { i.G=this;i.e=OldGraph<N,E>::FirstOut(n.n); }
-    void getFirst(SymEdgeIterator &i,const NodeIterator &n)
-    { i.G=this;i.e=OldGraph<N,E>::FirstEdge(n.n); }
-    void getFirst(EachEdgeIterator &i) //Vegigmegy mindenen
-    {
-      i.G=this;
-      getFirst(i.n);
-      i.e=OldGraph<N,E>::NodeNum()?OldGraph<N,E>::FirstOut(i.n.n):NULL;
-    }  
-    
-    
-    
-    //Vagy beginnode()?
-    const DeletingEdgeIterator firstOut(const NodeIterator &n)
-    {
-      EdgeIterator i;
-      i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstOut(n.n);
-      return i;
-    }
-    const DeletingEdgeIterator firstIn(const NodeIterator &n)
-    {
-      EdgeIterator i;
-      i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstIn(n.n);
-      return i;
-    }
-    const DeletingSymEdgeIterator firstSym(const NodeIterator &n)
-    {
-      EdgeIterator i;
-      i.G=n.G;i.n=n.n;
-      i.edge=n.G->OldGraph<N,E>::FirstEdge(n.n);
-      return i;
-    }
-    
-    //    class FirstAnythingType;
-    //    friend class FirstAnythingType;
-
-    class FirstAnythingTypeNode
-    {
-      NodeIterator n;
-    public:
-      FirstAnythingTypeNode(NodeIterator i) : n(i) {}
-
-      operator const InEdgeIterator () const
-      {InEdgeIterator i; n.G->GetFirst(i,n);return i;}
-      operator const OutEdgeIterator () const
-      {OutEdgeIterator i; n.G->GetFirst(i,n);return i;}
-      operator const SymEdgeIterator () const
-      {SymEdgeIterator i; n.G->GetFirst(i,n);return i;}
-  
-      operator const InEdgeIt () const
-      {InEdgeIt i; n.G->GetFirst(i,n);return i;}
-      operator const OutEdgeIt () const
-      {OutEdgeIt i; n.G->GetFirst(i,n);return i;}
-      operator const SymEdgeIt () const
-      {SymEdgeIt i; n.G->GetFirst(i,n);return i;}
-    };
-    
-    class FirstAnythingType
-    {
-      Graph<N,E> *G;
-    public:
-      FirstAnythingType(Graph<N,E> *gg) : G(gg) {}
-
-      operator const EachEdgeIterator () const
-      {EachEdgeIterator i; G->GetFirst(i);return i;}  
-      operator const EdgeIt () const
-      {EdgeIt i; G->GetFirst(i);return i;}
-      operator const NodeIterator () const
-      {NodeIterator i; G->GetFirst(i);return i;}  
-      operator const NodeIt () const
-      {NodeIt i; G->GetFirst(i);return i;}
-    } _FST;
-    
-    //    const NodeIterator First() {NodeIterator i;GetFirst(i); return i;}
-    FirstAnythingTypeNode first(NodeIterator &i)
-    {FirstAnythingTypeNode t(i); return t;}
-    const FirstAnythingType &first() {return _FST;}
-    
-    // LastNode() vagy endnode() stb. Nem kell?
-    
-    DeletingNodeIterator addNode()
-    {
-      DeletingNodeIterator i;
-      i.G=this; i.n=OldGraph<N,E>::AddNode();
-      return i;
-    }
-    DeletingEdgeIterator
-    addEdge(const NodeIterator from,const NodeIterator to)
-    {
-      DeletingEdgeIterator i;
-      i.G=this;i.e=OldGraph<N,E>::AddEdge(from.n,to.n);return i;
-    }
-    
-    void Delete(DeletingNodeIterator n) {n.G->OldGraph<N,E>::Delete(n.n);}
-    void Delete(DeletingEdgeIterator e) {e.G->OldGraph<N,E>::Delete(e.e);}
-    
-    int nodeNum() { OldGraph<N,E>::NodeNum(); }
-    void clean() { OldGraph<N,E>::Clean(); }
-
-    Graph() : _FST(this) {}
-
-    // MAPS:
-    template<class T> class NodeMap
-    {
-      Graph<N,E> *G;
-      vector<T> map;
-
-    public:
-      typedef T value_type;
-      void put(const NodeIterator i, const T &t) {map[i.Index()]=t;}
-      T get(const NodeIterator i) const {return map[i.Index()];}
-      T operator[](NodeIterator i) {return map[i.Index()];}
-
-      void update() { map.resize(G->MaxNode());}
-
-      NodeMap() {}
-      void setG(Graph<N,E> &Gr) { G=&Gr; update();}      
-    };
-
-    template<class T> class EdgeMap
-    {
-      Graph<N,E> *G;
-      vector<T> map;
-
-    public:
-      typedef T value_type;
-      void put(const EdgeIterator i, const T &t) {map[i.Index()]=t;}
-      T get(const EdgeIterator i) const {return map[i.Index()];}
-      T &operator[](EdgeIterator i) {return map[i.Index()];}
-      
-      void update()
-	{ map.resize(G->MaxEdge());}
-      
-      EdgeMap() {}
-      void setG(Graph<N,E> &Gr) 
-      { G=&Gr ;update();}
-      
-    };
-    
-
-    int maxNode() { return OldGraph<N,E>::MaxNode();}
-    int maxEdge() { return ::edge_block_num*EDGE_BLOCK_SIZE;}
-    
-  };
-  
-  template <class G> //G is a graph-type
-  class Path
-  {
-  public:
-    typedef G Graph;
-    typedef typename G::NodeIterator NodeIterator;
-    typedef typename G::EdgeIterator EdgeIterator;
-    typedef typename G::SymEdgeIterator SymEdgeIterator;
-    
-  private:
-    std::vector<EdgeIterator> path;
-    std::vector<bool> reversed;
-
-  public:
-    void setLength(int n) { path.resize(n);reversed.resize(n);}
-    int getLength() { return path.size(); }
-    EdgeIterator &operator[](int n) {return path[n];}
-    NodeIterator GetNode(int n) // What about path of length 1?
-    {
-      return n?
-	reversed[n-1]?path[n-1].tail():path[n-1].head():
-	reversed[0]?path[0].head():path[0].tail();
-    }
-    void setRevert(int n,bool r=true) {reversed[n]=r;}
-    void setEdge(int n,SymEdgeIterator i)
-    {
-      path[n]=i;
-      reversed[n] = i.head()==i.aNode();
-    }
-    void setEdge(int n,EdgeIterator i,bool r)
-    {
-      path[n]=i;
-      reversed[n] = r;
-    }
-
-    NodeIterator tail() { return getNode(0); }
-    NodeIterator head() { return getNode(getLength()); }
-  };
-  
-  /*   Ez itt a fiam kommentje:
-       <v n  nnnnnnnnnnnnnncncccccccccccccccccvvvvvv
-       vvnvnvnvnvnvvnnvnvnvnnvnbbbvfffffvvffffffffffffffffffffz
-       <<  < < <  < <  <   .cx..x.c.cc.c          
-       mcmn   
-  */
-};
-
-#endif
diff -r 35c2543f45fb -r f45703336699 src/include/invalid.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/include/invalid.h	Mon Mar 29 08:16:18 2004 +0000
@@ -0,0 +1,33 @@
+// -*- 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 {};
+  
+  /// 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();
+
+};
+
+#endif
+  
diff -r 35c2543f45fb -r f45703336699 src/include/smart_graph.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/include/smart_graph.h	Mon Mar 29 08:16:18 2004 +0000
@@ -0,0 +1,649 @@
+// -*- mode:C++ -*-
+
+#ifndef HUGO_SMART_GRAPH_H
+#define HUGO_SMART_GRAPH_H
+
+///\file
+///\brief SmartGraph and SymSmartGraph classes.
+
+#include <vector>
+#include <limits.h>
+
+#include "invalid.h"
+
+namespace hugo {
+
+  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.
+  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) = NULL;
+      virtual void erase(const Key k) = NULL;
+      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;
+    
+    //     class Node { int n; };
+    //     class NodeIt : public Node { };
+    //     class Edge { int n; };
+    //     class EdgeIt : public Edge {};
+    //     class OutEdgeIt : public Edge {};
+    //     class InEdgeIt : public Edge {};
+    //     class SymEdge;
+    
+    template <typename T> class NodeMap;
+    template <typename T> class EdgeMap;
+    
+  public:
+
+    /* default constructor */
+
+    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; }
+
+    // Marci
+    Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
+    Node aNode(InEdgeIt e) const { return edges[e.n].head; }
+//     //Node aNode(const SymEdge& e) const { return e.aNode(); }
+
+    // Marci
+    Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
+    Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
+//     //Node bNode(const SymEdge& e) const { return e.bNode(); }
+
+    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; }
+    
+    void setInvalid(Edge &e) { e.n=-1; }
+    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.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 i) { 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(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { }
+      NodeIt() : Node() { }
+    };
+
+    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){}
+    };
+
+    // Map types
+
+//     // Static Maps are not necessary.
+//     template <typename T>
+//     class NodeMap {
+//       const SmartGraph& G; 
+//       std::vector<T> container;
+//     public:
+//       typedef T ValueType;
+//       typedef Node KeyType;
+//       NodeMap(const SmartGraph& _G) : G(_G), container(G.maxNodeId()) { }
+//       NodeMap(const SmartGraph& _G, T a) : 
+// 	G(_G), container(G.maxNodeId(), a) { }
+//       void set(Node n, T a) { container[n.n]=a; }
+//       T get(Node n) const { return container[n.n]; }
+//       T& operator[](Node n) { return container[n.n]; }
+//       const T& operator[](Node n) const { return container[n.n]; }
+//       void update() { container.resize(G.maxNodeId()); }
+//       void update(T a) { container.resize(G.maxNodeId(), a); }
+//     };
+
+//     template <typename T>
+//     class EdgeMap {
+//       const SmartGraph& G; 
+//       std::vector<T> container;
+//     public:
+//       typedef T ValueType;
+//       typedef Edge KeyType;
+//       EdgeMap(const SmartGraph& _G) : G(_G), container(G.maxEdgeId()) { }
+//       EdgeMap(const SmartGraph& _G, T a) : 
+// 	G(_G), container(G.maxEdgeId(), a) { }
+//       void set(Edge e, T a) { container[e.n]=a; }
+//       T get(Edge e) const { return container[e.n]; }
+//       T& operator[](Edge e) { return container[e.n]; } 
+//       const T& operator[](Edge e) const { return container[e.n]; } 
+//       void update() { container.resize(G.maxEdgeId()); }
+//       void update(T a) { container.resize(G.maxEdgeId(), a); }
+//     };
+
+    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 get(Node n) const { return container[n.n]; }
+      //Hajjaj:
+      //T& operator[](Node n) { return container[n.n]; }
+      typename std::vector<T>::reference
+      operator[](Node n) { return container[n.n]; }
+      //const T& operator[](Node n) const { return container[n.n]; }
+      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)
+      {
+	copy(m.container.begin(), m.container.end(), container.begin());
+	return *this;
+      }
+      
+      void update() {}    //Useless for DynMaps
+      void update(T a) {}  //Useless for DynMaps
+    };
+    
+    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_node_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_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);
+      }
+      ~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)
+      {
+	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) { }
+    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)
+      {
+	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 35c2543f45fb -r f45703336699 src/work/alpar/graph.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/alpar/graph.h	Mon Mar 29 08:16:18 2004 +0000
@@ -0,0 +1,493 @@
+// -*-mode: c++; -*-
+#ifndef __GRAPH_H_
+#define __GRAPH_H_
+
+//inline void *operator new(size_t s, void *p) { return p; }
+#include <new>
+#include <vector>
+
+namespace NEGRO 
+{
+  using namespace std;
+  
+#include "oldgraph.h"
+  
+  template <class N, class E> class Graph : protected OldGraph<N,E>
+  {
+  public:
+    typedef E EdgeType;
+    typedef N NodeType;
+    
+    class EdgeIt
+    {
+    public:
+      NEGRO::EdgePoint e;
+      bool valid() { return e; }
+    };
+    
+    class InEdgeIt : public EdgeIt {};
+    class OutEdgeIt : public EdgeIt {};
+    class BiEdgeIt : public EdgeIt {};
+    class SymEdgeIt : public EdgeIt {};
+    
+    typedef int NodeIt;
+    
+    typedef NodeIt EachNodeIt;
+    
+    class NodeIterator;
+    
+    class EdgeIterator;
+    class InEdgeIterator;
+    class OutEdgeIterator;
+    class BiEdgeIterator;
+    class SymEdgeIterator;
+    class AllEdgeIterator;
+    
+    class FirstAnythingTypeNode; //Required by the unified First() function.
+
+    friend class NodeIterator;
+    friend class EdgeIterator;
+    friend class InEdgeIterator;
+    friend class OutEdgeIterator;
+    friend class BiEdgeIterator;
+    friend class SymEdgeIterator;
+    friend class EachEdgeIterator;
+    
+    class NodeIterator
+    {
+      Graph<N,E> *G;  //operator*() miatt kell!!!
+      int n;     //nem kellene, ha itt mutato lenne!!
+    public:    
+      
+      NodeIterator() {;} 
+      NodeIterator(Graph<N,E> &Gr)//'const Graph<N,E> &G' would be wrong.
+      {G=&Gr;n=Gr.OldGraph<N,E>::FirstNode();} 
+      NodeIterator(const NodeIterator &i) {G=i.G;n=i.n;}
+      
+      NodeIterator &goNext() { n=G->NextNode(n); return *this;}
+      NodeIterator next() const { return NodeIterator(*this).goNext();}
+      NodeIterator &operator++() { return goNext();} 
+      NodeIterator operator++(int)
+      {NodeIterator tmp(*this); goNext(); return tmp;}
+      bool valid() { return n!=INVALID; }
+      
+      N &operator*() const { return G->Data(n); }
+      N *operator->() const { return &G->Data(n); }
+      
+      bool operator==(const NodeIterator &i) const {return n==i.n;}
+      bool operator!=(const NodeIterator &i) const {return n!=i.n;}
+      
+      int index() const { return n; } //If the nodes are indexable 
+      friend class Graph;
+      friend class EdgeIterator;
+      friend class InEdgeIterator;
+      friend class OutEdgeIterator;
+      friend class BiEdgeIterator;
+      friend class SymEdgeIterator;
+      friend class EachEdgeIterator;
+      friend class FirstAnythingTypeNode;
+
+      //Nem kellene egy:
+      //      static NodeIterator &GetInvalid();  ?
+    };
+    
+    class EdgeIterator
+    {
+      
+      Graph<N,E> *G; //Itt baj van!!!!! operator*() miatt kell!
+      //Ez csak kicsit baj, de:
+      // Meg a From() es To() miatt!!!!!!!!!!
+      
+      NEGRO::EdgeIt e;
+      
+    public:
+      EdgeIterator() {;} //Kell inicializalni? (Nem)
+      EdgeIterator(const EdgeIterator &i) {G=i.G;e=i.e;}
+      
+      // Lehet, hogy ez a ketto nem kell!!!
+      
+      NodeIterator tail() const {NodeIterator i;i.G=G;i.n=e->From();return i;}
+      NodeIterator head() const {NodeIterator i;i.G=G;i.n=e->To();return i;}
+      NodeIterator opposite(const NodeIterator &n) const
+      {return n==tail()?head():tail();}
+      
+      bool valid() {return e;}
+      E &operator*() const { return G->Data(e); }
+      E *operator->() const { return &G->Data(e); }
+      
+      //operator const OutEdgeIterator ();
+      //operator const InEdgeIterator ();
+      //operator const BiEdgeIterator ();
+      //operator const SymEdgeIterator(); //Ez kerdeses, mit csinal
+      
+      bool operator==(const EdgeIterator &i) const {return e==i.e;}
+      bool operator!=(const EdgeIterator &i) const {return e!=i.e;}
+       
+      int Index() const {return e->index.block*EDGE_BLOCK_SIZE+e->index.index;}
+      //If the edges are indexable 
+
+      friend class Graph;
+      friend class InEdgeIterator;
+      friend class OutEdgeIterator;
+      friend class BiEdgeIterator;
+      friend class SymEdgeIterator;
+      friend class EachEdgeIterator;
+    };
+    
+    class BiEdgeIterator : public EdgeIterator
+    {
+    public:
+      BiEdgeIterator &goNextIn()  { e=e->NextIn(); return *this;}
+      BiEdgeIterator &goNextOut() { e=e->NextOut(); return *this;}
+      BiEdgeIterator nextIn() const  {return BiEdgeIterator(*this).goNextIn();}
+      BiEdgeIterator nextOut() const {return BiEdgeIterator(*this).goNextOut();}
+      
+      operator InEdgeIterator ()
+      {InEdgeIterator i; i.G=G;i.e=e;return i;}
+      operator OutEdgeIterator ()
+      {OutEdgeIterator i; i.G=G;i.e=e;return i;}
+      //operator const SymEdgeIterator ()
+      
+      friend class Graph;
+    };
+    
+    class InEdgeIterator : public EdgeIterator
+    //Ne a BiEdgeIterator-bol szarmazzon?
+    {
+    public:
+      InEdgeIterator() {}
+      InEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n)
+      { G=&Gr; e=Gr.OldGraph<N,E>::FirstIn(n.n);}
+
+      InEdgeIterator &GoNext() { e=e->NextIn(); return *this;}
+      InEdgeIterator Next() const {return InEdgeIterator(*this).GoNext();}
+      InEdgeIterator &operator++() { return GoNext();}
+      InEdgeIterator operator++(int)
+      {InEdgeIterator tmp(*this); GoNext(); return tmp;}
+      
+      operator const OutEdgeIterator ()
+      {OutEdgeIterator i; i.G=G;i.e=e;return i;}
+      operator const BiEdgeIterator ()
+      {EdgeIterator i; i.G=G;i.e=e;return i;}
+      //      operator const SymEdgeIterator ();
+      
+      NodeIterator Anode() const {return To();}
+      NodeIterator Bnode() const {return From();}
+      
+      friend class Graph;
+    };
+    
+    class OutEdgeIterator : public EdgeIterator
+    {
+    public:
+      OutEdgeIterator() {}
+      OutEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n)
+      { G=&Gr; e=Gr.OldGraph<N,E>::FirstOut(n.n);}
+
+      OutEdgeIterator &goNext() { e=e->NextOut(); return *this;}
+      OutEdgeIterator next() const {return OutEdgeIterator(*this).goNext();}
+      OutEdgeIterator &operator++() { return goNext();}
+      OutEdgeIterator operator++(int)
+      {OutEdgeIterator tmp(*this); goNext(); return tmp;}
+      
+      NodeIterator aNode() const {return tail();}
+      NodeIterator bNode() const {return head();}
+      
+      operator const InEdgeIterator ()
+      {InEdgeIterator i; i.G=G;i.e=e;return i;}
+      operator const BiEdgeIterator ()
+      {BiEdgeIterator i; i.G=G;i.e=e;return i;}
+      //operator const SymEdgeIterator(); 
+      
+      friend class Graph;
+    };
+    
+    class SymEdgeIterator : public EdgeIterator
+    {
+      NodeIterator n;  // Itt ketszer van a G
+      
+    public:
+      SymEdgeIterator() {}
+      SymEdgeIterator(Graph<N,E> &Gr,const NodeIterator &nn)
+      { G=&Gr; n=nn; e=Gr.OldGraph<N,E>::FirstEdge(nn.n); }
+
+      SymEdgeIterator &goNext() { e=G->NextEdge(n.n,e); return *this;}
+      SymEdgeIterator next() const {return SymEdgeIterator(*this).goNext();}
+      SymEdgeIterator &operator++() { return goNext();}
+      SymEdgeIterator operator++(int)
+      {SymEdgeIterator tmp(*this); goNext(); return tmp;}
+      
+      NodeIterator aNode() const {return n;}
+      NodeIterator bNode() const {return n.n==tail().n?head():tail();}
+      
+      operator const InEdgeIterator ()
+      {InEdgeIterator i; i.G=G;i.e=e;return i;}
+      operator const OutEdgeIterator ()
+      {OutEdgeIterator i; i.G=G;i.e=e;return i;}
+      operator const BiEdgeIterator ()
+      {BiEdgeIterator i; i.G=G;i.e=e;return i;}
+      
+      friend class Graph;
+    };
+    
+    class EachEdgeIterator : public EdgeIterator
+    {
+      NodeIterator n;  // Itt ketszer van a G
+      
+    public:
+      EachEdgeIterator() {}
+      EachEdgeIterator(Graph<N,E> &Gr) : n(Gr)
+      {
+	e=n.valid()?Gr.OldGraph<N,E>::FirstOut(n.n):NULL;
+      }  
+
+      EachEdgeIterator &goNext()
+      {
+	e=e->NextOut();
+	if(!e && (++n).valid()) e=G->OldGraph<N,E>::FirstOut(n.n);
+	return *this;
+      }
+      EachEdgeIterator next() const {return EachEdgeIterator(*this).goNext();}
+      EachEdgeIterator &operator++() { return goNext();}
+      EachEdgeIterator operator++(int)
+	{EachEdgeIterator tmp(*this); goNext(); return tmp;}
+      
+      
+      NodeIterator aNode() const {return n;}
+      NodeIterator bNode() const {return n.n==tail().n?head():tail();}
+      
+      operator const EdgeIterator ()
+      {EdgeIterator i; i.G=G;i.e=e;return i;}
+      operator const InEdgeIterator ()
+      {InEdgeIterator i; i.G=G;i.e=e;return i;}
+      operator const OutEdgeIterator ()
+      {OutEdgeIterator i; i.G=G;i.e=e;return i;}
+      operator const BiEdgeIterator ()
+      {BiEdgeIterator i; i.G=G;i.e=e;return i;}
+      
+      friend class Graph;
+    };
+    
+    typedef NodeIterator DeletingNodeIterator;
+    typedef EdgeIterator DeletingEdgeIterator;
+    typedef BiEdgeIterator DeletingBiEdgeIterator;
+    typedef OutEdgeIterator DeletingOutEdgeIterator;
+    typedef InEdgeIterator DeletingInEdgeIterator;
+    typedef SymEdgeIterator DeletingSymEdgeIterator;
+    
+    const NodeIterator firstNode()
+    {
+      NodeIterator i;
+      i.G=this;i.n=OldGraph<N,E>::FirstNode();
+      return i;
+    }
+    
+    void getFirst(NodeIt &p)   { p=OldGraph<N,E>::FirstNode(); }
+    
+    void getFirst(InEdgeIt &p,const NodeIt &n)
+    { p=OldGraph<N,E>::FirstIn(n); }
+    void getFirst(OutEdgeIt &p,const NodeIt &n)
+    { p=OldGraph<N,E>::FirstOut(n); }
+    void getFirst(SymEdgeIt &p,const NodeIt &n)
+    { p=OldGraph<N,E>::FirstEdge(n); }
+    void getFirst(EdgeIt &p) //Vegigmegy mindenen
+    { p.e=nodeNum()?OldGraph<N,E>::FirstOut(OldGraph<N,E>::FirstNode()):NULL;}
+
+    void getFirst(NodeIterator &i) { i.G=this;i.n=OldGraph<N,E>::FirstNode();}
+    
+    void getFirst(InEdgeIterator &i,const NodeIterator &n)
+    { i.G=this;i.e=OldGraph<N,E>::FirstIn(n.n); }
+    void getFirst(OutEdgeIterator &i,const NodeIterator &n)
+    { i.G=this;i.e=OldGraph<N,E>::FirstOut(n.n); }
+    void getFirst(SymEdgeIterator &i,const NodeIterator &n)
+    { i.G=this;i.e=OldGraph<N,E>::FirstEdge(n.n); }
+    void getFirst(EachEdgeIterator &i) //Vegigmegy mindenen
+    {
+      i.G=this;
+      getFirst(i.n);
+      i.e=OldGraph<N,E>::NodeNum()?OldGraph<N,E>::FirstOut(i.n.n):NULL;
+    }  
+    
+    
+    
+    //Vagy beginnode()?
+    const DeletingEdgeIterator firstOut(const NodeIterator &n)
+    {
+      EdgeIterator i;
+      i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstOut(n.n);
+      return i;
+    }
+    const DeletingEdgeIterator firstIn(const NodeIterator &n)
+    {
+      EdgeIterator i;
+      i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstIn(n.n);
+      return i;
+    }
+    const DeletingSymEdgeIterator firstSym(const NodeIterator &n)
+    {
+      EdgeIterator i;
+      i.G=n.G;i.n=n.n;
+      i.edge=n.G->OldGraph<N,E>::FirstEdge(n.n);
+      return i;
+    }
+    
+    //    class FirstAnythingType;
+    //    friend class FirstAnythingType;
+
+    class FirstAnythingTypeNode
+    {
+      NodeIterator n;
+    public:
+      FirstAnythingTypeNode(NodeIterator i) : n(i) {}
+
+      operator const InEdgeIterator () const
+      {InEdgeIterator i; n.G->GetFirst(i,n);return i;}
+      operator const OutEdgeIterator () const
+      {OutEdgeIterator i; n.G->GetFirst(i,n);return i;}
+      operator const SymEdgeIterator () const
+      {SymEdgeIterator i; n.G->GetFirst(i,n);return i;}
+  
+      operator const InEdgeIt () const
+      {InEdgeIt i; n.G->GetFirst(i,n);return i;}
+      operator const OutEdgeIt () const
+      {OutEdgeIt i; n.G->GetFirst(i,n);return i;}
+      operator const SymEdgeIt () const
+      {SymEdgeIt i; n.G->GetFirst(i,n);return i;}
+    };
+    
+    class FirstAnythingType
+    {
+      Graph<N,E> *G;
+    public:
+      FirstAnythingType(Graph<N,E> *gg) : G(gg) {}
+
+      operator const EachEdgeIterator () const
+      {EachEdgeIterator i; G->GetFirst(i);return i;}  
+      operator const EdgeIt () const
+      {EdgeIt i; G->GetFirst(i);return i;}
+      operator const NodeIterator () const
+      {NodeIterator i; G->GetFirst(i);return i;}  
+      operator const NodeIt () const
+      {NodeIt i; G->GetFirst(i);return i;}
+    } _FST;
+    
+    //    const NodeIterator First() {NodeIterator i;GetFirst(i); return i;}
+    FirstAnythingTypeNode first(NodeIterator &i)
+    {FirstAnythingTypeNode t(i); return t;}
+    const FirstAnythingType &first() {return _FST;}
+    
+    // LastNode() vagy endnode() stb. Nem kell?
+    
+    DeletingNodeIterator addNode()
+    {
+      DeletingNodeIterator i;
+      i.G=this; i.n=OldGraph<N,E>::AddNode();
+      return i;
+    }
+    DeletingEdgeIterator
+    addEdge(const NodeIterator from,const NodeIterator to)
+    {
+      DeletingEdgeIterator i;
+      i.G=this;i.e=OldGraph<N,E>::AddEdge(from.n,to.n);return i;
+    }
+    
+    void Delete(DeletingNodeIterator n) {n.G->OldGraph<N,E>::Delete(n.n);}
+    void Delete(DeletingEdgeIterator e) {e.G->OldGraph<N,E>::Delete(e.e);}
+    
+    int nodeNum() { OldGraph<N,E>::NodeNum(); }
+    void clean() { OldGraph<N,E>::Clean(); }
+
+    Graph() : _FST(this) {}
+
+    // MAPS:
+    template<class T> class NodeMap
+    {
+      Graph<N,E> *G;
+      vector<T> map;
+
+    public:
+      typedef T value_type;
+      void put(const NodeIterator i, const T &t) {map[i.Index()]=t;}
+      T get(const NodeIterator i) const {return map[i.Index()];}
+      T operator[](NodeIterator i) {return map[i.Index()];}
+
+      void update() { map.resize(G->MaxNode());}
+
+      NodeMap() {}
+      void setG(Graph<N,E> &Gr) { G=&Gr; update();}      
+    };
+
+    template<class T> class EdgeMap
+    {
+      Graph<N,E> *G;
+      vector<T> map;
+
+    public:
+      typedef T value_type;
+      void put(const EdgeIterator i, const T &t) {map[i.Index()]=t;}
+      T get(const EdgeIterator i) const {return map[i.Index()];}
+      T &operator[](EdgeIterator i) {return map[i.Index()];}
+      
+      void update()
+	{ map.resize(G->MaxEdge());}
+      
+      EdgeMap() {}
+      void setG(Graph<N,E> &Gr) 
+      { G=&Gr ;update();}
+      
+    };
+    
+
+    int maxNode() { return OldGraph<N,E>::MaxNode();}
+    int maxEdge() { return ::edge_block_num*EDGE_BLOCK_SIZE;}
+    
+  };
+  
+  template <class G> //G is a graph-type
+  class Path
+  {
+  public:
+    typedef G Graph;
+    typedef typename G::NodeIterator NodeIterator;
+    typedef typename G::EdgeIterator EdgeIterator;
+    typedef typename G::SymEdgeIterator SymEdgeIterator;
+    
+  private:
+    std::vector<EdgeIterator> path;
+    std::vector<bool> reversed;
+
+  public:
+    void setLength(int n) { path.resize(n);reversed.resize(n);}
+    int getLength() { return path.size(); }
+    EdgeIterator &operator[](int n) {return path[n];}
+    NodeIterator GetNode(int n) // What about path of length 1?
+    {
+      return n?
+	reversed[n-1]?path[n-1].tail():path[n-1].head():
+	reversed[0]?path[0].head():path[0].tail();
+    }
+    void setRevert(int n,bool r=true) {reversed[n]=r;}
+    void setEdge(int n,SymEdgeIterator i)
+    {
+      path[n]=i;
+      reversed[n] = i.head()==i.aNode();
+    }
+    void setEdge(int n,EdgeIterator i,bool r)
+    {
+      path[n]=i;
+      reversed[n] = r;
+    }
+
+    NodeIterator tail() { return getNode(0); }
+    NodeIterator head() { return getNode(getLength()); }
+  };
+  
+  /*   Ez itt a fiam kommentje:
+       <v n  nnnnnnnnnnnnnncncccccccccccccccccvvvvvv
+       vvnvnvnvnvnvvnnvnvnvnnvnbbbvfffffvvffffffffffffffffffffz
+       <<  < < <  < <  <   .cx..x.c.cc.c          
+       mcmn   
+  */
+};
+
+#endif
diff -r 35c2543f45fb -r f45703336699 src/work/alpar/invalid.h
--- a/src/work/alpar/invalid.h	Fri Mar 26 23:34:45 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,33 +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 {};
-  
-  /// 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();
-
-};
-
-#endif
-  
diff -r 35c2543f45fb -r f45703336699 src/work/alpar/smart_graph.h
--- a/src/work/alpar/smart_graph.h	Fri Mar 26 23:34:45 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,649 +0,0 @@
-// -*- mode:C++ -*-
-
-#ifndef HUGO_SMART_GRAPH_H
-#define HUGO_SMART_GRAPH_H
-
-///\file
-///\brief SmartGraph and SymSmartGraph classes.
-
-#include <vector>
-#include <limits.h>
-
-#include <invalid.h>
-
-namespace hugo {
-
-  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.
-  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) = NULL;
-      virtual void erase(const Key k) = NULL;
-      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;
-    
-    //     class Node { int n; };
-    //     class NodeIt : public Node { };
-    //     class Edge { int n; };
-    //     class EdgeIt : public Edge {};
-    //     class OutEdgeIt : public Edge {};
-    //     class InEdgeIt : public Edge {};
-    //     class SymEdge;
-    
-    template <typename T> class NodeMap;
-    template <typename T> class EdgeMap;
-    
-  public:
-
-    /* default constructor */
-
-    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; }
-
-    // Marci
-    Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
-    Node aNode(InEdgeIt e) const { return edges[e.n].head; }
-//     //Node aNode(const SymEdge& e) const { return e.aNode(); }
-
-    // Marci
-    Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
-    Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
-//     //Node bNode(const SymEdge& e) const { return e.bNode(); }
-
-    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; }
-    
-    void setInvalid(Edge &e) { e.n=-1; }
-    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.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 i) { 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(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { }
-      NodeIt() : Node() { }
-    };
-
-    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){}
-    };
-
-    // Map types
-
-//     // Static Maps are not necessary.
-//     template <typename T>
-//     class NodeMap {
-//       const SmartGraph& G; 
-//       std::vector<T> container;
-//     public:
-//       typedef T ValueType;
-//       typedef Node KeyType;
-//       NodeMap(const SmartGraph& _G) : G(_G), container(G.maxNodeId()) { }
-//       NodeMap(const SmartGraph& _G, T a) : 
-// 	G(_G), container(G.maxNodeId(), a) { }
-//       void set(Node n, T a) { container[n.n]=a; }
-//       T get(Node n) const { return container[n.n]; }
-//       T& operator[](Node n) { return container[n.n]; }
-//       const T& operator[](Node n) const { return container[n.n]; }
-//       void update() { container.resize(G.maxNodeId()); }
-//       void update(T a) { container.resize(G.maxNodeId(), a); }
-//     };
-
-//     template <typename T>
-//     class EdgeMap {
-//       const SmartGraph& G; 
-//       std::vector<T> container;
-//     public:
-//       typedef T ValueType;
-//       typedef Edge KeyType;
-//       EdgeMap(const SmartGraph& _G) : G(_G), container(G.maxEdgeId()) { }
-//       EdgeMap(const SmartGraph& _G, T a) : 
-// 	G(_G), container(G.maxEdgeId(), a) { }
-//       void set(Edge e, T a) { container[e.n]=a; }
-//       T get(Edge e) const { return container[e.n]; }
-//       T& operator[](Edge e) { return container[e.n]; } 
-//       const T& operator[](Edge e) const { return container[e.n]; } 
-//       void update() { container.resize(G.maxEdgeId()); }
-//       void update(T a) { container.resize(G.maxEdgeId(), a); }
-//     };
-
-    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 get(Node n) const { return container[n.n]; }
-      //Hajjaj:
-      //T& operator[](Node n) { return container[n.n]; }
-      typename std::vector<T>::reference
-      operator[](Node n) { return container[n.n]; }
-      //const T& operator[](Node n) const { return container[n.n]; }
-      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)
-      {
-	copy(m.container.begin(), m.container.end(), container.begin());
-	return *this;
-      }
-      
-      void update() {}    //Useless for DynMaps
-      void update(T a) {}  //Useless for DynMaps
-    };
-    
-    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_node_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_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);
-      }
-      ~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)
-      {
-	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) { }
-    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)
-      {
-	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