Changeset 774:4297098d9677 in lemon-0.x for src/hugo

Timestamp:

08/30/04 14:01:47 (20 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

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

Message:

Merge back the whole branches/hugo++ to trunk.

Location:

src/hugo

Files:

• Makefile.am (modified) (1 diff)
• bfs.h (added)
• dijkstra.h (modified) (4 diffs)
• full_graph.h (modified) (7 diffs)
• graph_wrapper.h (modified) (18 diffs)
• list_graph.h (modified) (24 diffs)
• max_flow.h (modified) (25 diffs)
• skeletons/graph.h (modified) (23 diffs)
• smart_graph.h (modified) (6 diffs)
• unionfind.h (modified) (1 diff)

src/hugo/Makefile.am

@@ -1 +1 @@
 pkginclude_HEADERS =                                                    \
+        bfs.h                                                           \
         bin_heap.h                                                      \
         dijkstra.h                                                      \

src/hugo/dijkstra.h

@@ -85 +85 @@
     bool local_distance;
 
+    //The source node of the last execution.
+    Node source;
+
     ///Initialize maps
     
@@ -213 +216 @@
       init_maps();
       
-      for ( NodeIt u(*G) ; G->valid(u) ; G->next(u) ) {
+      source = s;
+      
+      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
         predecessor->set(u,INVALID);
         pred_node->set(u,INVALID);
@@ -236 +241 @@
         
         
-        for(OutEdgeIt e(*G,v); G->valid(e); G->next(e)) {
-          Node w=G->bNode(e); 
+        for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
+          Node w=G->head(e); 
           
           switch(heap.state(w)) {
@@ -311 +316 @@
 
     ///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?
+    ///\warning the root node is reported to be reached!
     ///\pre \ref run() must be called before using this function.
     ///
-    bool reached(Node v) { return G->valid((*predecessor)[v]); }
+    bool reached(Node v) { return v==source || (*predecessor)[v]==INVALID; }
     
   };

src/hugo/full_graph.h

@@ -64 +64 @@
     Node head(Edge e) const { return e.n/NodeNum; }
 
-    Node aNode(OutEdgeIt e) const { return tail(e); }
-    Node aNode(InEdgeIt e) const { return head(e); }
-
-    Node bNode(OutEdgeIt e) const { return head(e); }
-    Node bNode(InEdgeIt e) const { return tail(e); }
-
     NodeIt& first(NodeIt& v) const {
       v=NodeIt(*this); return v; }
@@ -79 +73 @@
       e=InEdgeIt(*this,v); return e; }
 
-    static bool valid(Edge e) { return e.n!=-1; }
-    static bool valid(Node n) { return 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)%(NodeNum+1)-1; 
-      return it; 
-    }
-    OutEdgeIt& next(OutEdgeIt& it) const
-    { it.n+=NodeNum; if(it.n>=EdgeNum) it.n=-1; return it; }
-    InEdgeIt& next(InEdgeIt& it) const
-    { if(!((++it.n)%NodeNum)) it.n=-1; return it; }
-    static EdgeIt& next(EdgeIt& it) { --it.n; return it; }
-
     static int id(Node v) { return v.n; }
     static int id(Edge e) { return e.n; }
 
+    /// Finds an edge between two nodes.
+    
+    /// Finds an edge from node \c u to node \c v.
+    ///
+    /// If \c prev is \ref INVALID (this is the default value), then
+    /// It finds the first edge from \c u to \c v. Otherwise it looks for
+    /// the next edge from \c u to \c v after \c prev.
+    /// \return The found edge or INVALID if there is no such an edge.
+    Edge findEdge(Node u,Node v, Edge prev = INVALID) 
+    {
+      return prev.n==-1?Edge(*this,u.n,v.n):INVALID;
+    }
+    
+      
     class Node {
       friend class FullGraph;
@@ -120 +112 @@
     
     class NodeIt : public Node {
+      const FullGraph *G;
       friend class FullGraph;
     public:
       NodeIt() : Node() { }
+      NodeIt(const FullGraph& _G,Node n) : Node(n), G(&_G) { }
       NodeIt(Invalid i) : Node(i) { }
-      NodeIt(const FullGraph& G) : Node(G.NodeNum?0:-1) { }
+      NodeIt(const FullGraph& _G) : Node(_G.NodeNum?0:-1), G(&_G) { }
       ///\todo Undocumented conversion Node -\> NodeIt.
-      NodeIt(const FullGraph& G, const Node &n) : Node(n) { }
+      NodeIt& operator++() { n=(n+2)%(G->NodeNum+1)-1;return *this; }
     };
 
@@ -139 +133 @@
       friend int FullGraph::id(Edge e);
 
-      Edge(int nn) {n=nn;}
+      Edge(int nn) : n(nn) {}
+      Edge(const FullGraph &G, int tail, int head) : n(G.NodeNum*head+tail) {}
     public:
       Edge() { }
@@ -155 +150 @@
       friend class FullGraph;
     public:
-      EdgeIt(const FullGraph& G) : Edge(G.EdgeNum-1) { }
+      EdgeIt(const FullGraph& _G) : Edge(_G.EdgeNum-1) { }
+      EdgeIt(const FullGraph&, Edge e) : Edge(e) { }
       EdgeIt (Invalid i) : Edge(i) { }
       EdgeIt() : Edge() { }
+      EdgeIt& operator++() { --n; return *this; }
+
       ///\bug This is a workaround until somebody tells me how to
       ///make class \c SymFullGraph::SymEdgeMap friend of Edge
@@ -164 +162 @@
     
     class OutEdgeIt : public Edge {
+      const FullGraph *G;
       friend class FullGraph;
     public: 
       OutEdgeIt() : Edge() { }
+      OutEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
       OutEdgeIt (Invalid i) : Edge(i) { }
 
-      OutEdgeIt(const FullGraph& G,const Node v)
-        : Edge(v.n) {}
+      OutEdgeIt(const FullGraph& _G,const Node v) : Edge(v.n), G(&_G) {}
+      
+      OutEdgeIt& operator++()
+      { n+=G->NodeNum; if(n>=G->EdgeNum) n=-1; return *this; }
+
     };
     
     class InEdgeIt : public Edge {
+      const FullGraph *G;
       friend class FullGraph;
     public: 
       InEdgeIt() : Edge() { }
+      InEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
       InEdgeIt (Invalid i) : Edge(i) { }
-      InEdgeIt(const FullGraph& G,Node v) :Edge(v.n*G.NodeNum){}
+      InEdgeIt(const FullGraph& _G,Node v) : Edge(v.n*_G.NodeNum), G(&_G) {}
+      InEdgeIt& operator++()
+      { if(!((++n)%G->NodeNum)) n=-1; return *this; }
     };
 
@@ -280 +287 @@
         return *this;
       }
-      
+
       void update() {}
       void update(T a) {}

src/hugo/graph_wrapper.h

@@ -13 +13 @@
 #include <hugo/invalid.h>
 #include <hugo/maps.h>
-//#include <iter_map.h>
+#include <iostream>
 
 namespace hugo {
@@ -97 +97 @@
 
     GraphWrapper(Graph& _graph) : graph(&_graph) { }
+    GraphWrapper(const GraphWrapper<Graph>& gw) : graph(gw.graph) { }
 //     Graph& getGraph() const { return *graph; }
  
-//    typedef typename Graph::Node Node;
-    class Node : public Graph::Node {
+    typedef typename Graph::Node Node;
+//     class Node : public Graph::Node {
+//       friend class GraphWrapper<Graph>;
+//     public:
+//       Node() { }
+//       Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
+//       // /// \bug construction throughrthr multiple levels should be 
+//       // /// handled better
+//       // Node(const typename ParentGraph::ParentGraph::Node& _n) : 
+//       // Graph::Node(_n) { }
+//       Node(const Invalid& i) : Graph::Node(i) { }
+//     };
+    class NodeIt : public Node { 
+      const GraphWrapper<Graph>* gw;
       friend class GraphWrapper<Graph>;
-    public:
-      Node() { }
-      Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
-      // /// \bug construction throughrthr multiple levels should be 
-      // /// handled better
-      // Node(const typename ParentGraph::ParentGraph::Node& _n) : 
-      // Graph::Node(_n) { }
-      Node(const Invalid& i) : Graph::Node(i) { }
-    };
-    class NodeIt { 
-      friend class GraphWrapper<Graph>;
-      typename Graph::NodeIt n;
      public:
       NodeIt() { }
-      NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
-      NodeIt(const Invalid& i) : n(i) { }
-      NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
-      operator Node() const { return Node(typename Graph::Node(n)); }
-    };
-//    typedef typename Graph::Edge Edge;
-    class Edge : public Graph::Edge {
+      //      NodeIt(const NodeIt& n) : Node(n), gw(n.gw) { }
+      NodeIt(Invalid i) : Node(i) { }
+      NodeIt(const GraphWrapper<Graph>& _gw) : 
+        Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { }
+      NodeIt(const GraphWrapper<Graph>& _gw, const Node& n) : 
+        Node(n), gw(&_gw) { }
+      NodeIt& operator++() { 
+        *(static_cast<Node*>(this))=
+          ++(typename Graph::NodeIt(*(gw->graph), *this));
+        return *this; 
+      }
+    };
+    typedef typename Graph::Edge Edge;
+//     class Edge : public Graph::Edge {
+//       friend class GraphWrapper<Graph>;
+//     public:
+//       Edge() { }
+//       Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
+//       Edge(const Invalid& i) : Graph::Edge(i) { }
+//     };
+    class OutEdgeIt : public Edge { 
+      const GraphWrapper<Graph>* gw;
       friend class GraphWrapper<Graph>;
-    public:
-      Edge() { }
-      Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
-      Edge(const Invalid& i) : Graph::Edge(i) { }
-    };
-    class OutEdgeIt { 
+     public:
+      OutEdgeIt() { }
+      //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }
+      OutEdgeIt(Invalid i) : Edge(i) { }
+      OutEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) : 
+        Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
+      OutEdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) : 
+        Edge(e), gw(&_gw) { }
+      OutEdgeIt& operator++() { 
+        *(static_cast<Edge*>(this))=
+          ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
+        return *this; 
+      }
+    };
+    class InEdgeIt : public Edge { 
+      const GraphWrapper<Graph>* gw;
       friend class GraphWrapper<Graph>;
-      typename Graph::OutEdgeIt e;
-    public:
-      OutEdgeIt() { }
-      OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
-      OutEdgeIt(const Invalid& i) : e(i) { }
-      OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) : 
-        e(*(_G.graph), typename Graph::Node(_n)) { }
-      operator Edge() const { return Edge(typename Graph::Edge(e)); }
-    };
-    class InEdgeIt { 
+     public:
+      InEdgeIt() { }
+      //InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
+      InEdgeIt(Invalid i) : Edge(i) { }
+      InEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) : 
+        Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
+      InEdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) : 
+        Edge(e), gw(&_gw) { }
+      InEdgeIt& operator++() { 
+        *(static_cast<Edge*>(this))=
+          ++(typename Graph::InEdgeIt(*(gw->graph), *this));
+        return *this; 
+      }
+    };
+    //typedef typename Graph::SymEdgeIt SymEdgeIt;
+    class EdgeIt : public Edge { 
+      const GraphWrapper<Graph>* gw;
       friend class GraphWrapper<Graph>;
-      typename Graph::InEdgeIt e;
-    public:
-      InEdgeIt() { }
-      InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
-      InEdgeIt(const Invalid& i) : e(i) { }
-      InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) : 
-        e(*(_G.graph), typename Graph::Node(_n)) { }
-      operator Edge() const { return Edge(typename Graph::Edge(e)); }
-    };
-    //typedef typename Graph::SymEdgeIt SymEdgeIt;
-    class EdgeIt { 
-      friend class GraphWrapper<Graph>;
-      typename Graph::EdgeIt e;
-    public:
+     public:
       EdgeIt() { }
-      EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
-      EdgeIt(const Invalid& i) : e(i) { }
-      EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
-      operator Edge() const { return Edge(typename Graph::Edge(e)); }
+      //EdgeIt(const EdgeIt& e) : Edge(e), gw(e.gw) { }
+      EdgeIt(Invalid i) : Edge(i) { }
+      EdgeIt(const GraphWrapper<Graph>& _gw) : 
+        Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { }
+      EdgeIt(const GraphWrapper<Graph>& _gw, const Edge& e) : 
+        Edge(w), gw(&_gw) { }
+      EdgeIt& operator++() { 
+        *(static_cast<Edge*>(this))=
+          ++(typename Graph::EdgeIt(*(gw->graph), *this));
+        return *this; 
+      }
     };
    
@@ -176 +203 @@
     }
 
-    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
-    OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
-    InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
-    EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }    
+//     NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
+//     OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
+//     InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
+//     EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }    
 
     Node tail(const Edge& e) const { 
@@ -186 +213 @@
       return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
 
-    bool valid(const Node& n) const { 
-      return graph->valid(static_cast<typename Graph::Node>(n)); }
-    bool valid(const Edge& e) const { 
-      return graph->valid(static_cast<typename Graph::Edge>(e)); }
+//     bool valid(const Node& n) const { 
+//       return graph->valid(static_cast<typename Graph::Node>(n)); }
+//     bool valid(const Edge& e) const { 
+//       return graph->valid(static_cast<typename Graph::Edge>(e)); }
 
     int nodeNum() const { return graph->nodeNum(); }
     int edgeNum() const { return graph->edgeNum(); }
   
-    Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
-    Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
-    Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
-    Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
+//     Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
+//     Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
+//     Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
+//     Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
   
     Node addNode() const { return Node(graph->addNode()); }
@@ -219 +246 @@
       typedef typename Graph::template NodeMap<T> Parent;
     public:
-      NodeMap(const GraphWrapper<Graph>& _G) :  Parent(*(_G.graph)) { }
-      NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
+      NodeMap(const GraphWrapper<Graph>& gw) :  Parent(*(gw.graph)) { }
+      NodeMap(const GraphWrapper<Graph>& gw, T a) : Parent(*(gw.graph), a) { }
     };
 
@@ -226 +253 @@
       typedef typename Graph::template EdgeMap<T> Parent;
     public:
-      EdgeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { }
-      EdgeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { }
+      EdgeMap(const GraphWrapper<Graph>& gw) : Parent(*(gw.graph)) { }
+      EdgeMap(const GraphWrapper<Graph>& gw, T a) : Parent(*(gw.graph), a) { }
     };
   };
@@ -247 +274 @@
   public:
     RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }  
+    RevGraphWrapper(const RevGraphWrapper<Graph>& gw) : Parent(gw) { }
 
     typedef typename GraphWrapper<Graph>::Node Node;
@@ -257 +285 @@
     //typedef typename GraphWrapper<Graph>::InEdgeIt OutEdgeIt;
 
-    class OutEdgeIt { 
+    class OutEdgeIt : public Edge { 
+      const RevGraphWrapper<Graph>* gw;
       friend class GraphWrapper<Graph>;
-      friend class RevGraphWrapper<Graph>;
-      typename Graph::InEdgeIt e;
-    public:
+     public:
       OutEdgeIt() { }
-      OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
-      OutEdgeIt(const Invalid& i) : e(i) { }
-      OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) : 
-        e(*(_G.graph), typename Graph::Node(_n)) { }
-      operator Edge() const { return Edge(typename Graph::Edge(e)); }
-    };
-    class InEdgeIt { 
+      //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }
+      OutEdgeIt(Invalid i) : Edge(i) { }
+      OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) : 
+        Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
+      OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) : 
+        Edge(e), gw(&_gw) { }
+      OutEdgeIt& operator++() { 
+        *(static_cast<Edge*>(this))=
+          ++(typename Graph::InEdgeIt(*(gw->graph), *this));
+        return *this; 
+      }
+    };
+    class InEdgeIt : public Edge { 
+      const RevGraphWrapper<Graph>* gw;
       friend class GraphWrapper<Graph>;
-      friend class RevGraphWrapper<Graph>;
-      typename Graph::OutEdgeIt e;
-    public:
+     public:
       InEdgeIt() { }
-      InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
-      InEdgeIt(const Invalid& i) : e(i) { }
-      InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) : 
-        e(*(_G.graph), typename Graph::Node(_n)) { }
-      operator Edge() const { return Edge(typename Graph::Edge(e)); }
+      //InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
+      InEdgeIt(Invalid i) : Edge(i) { }
+      InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) : 
+        Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
+      InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) : 
+        Edge(e), gw(&_gw) { }
+      InEdgeIt& operator++() { 
+        *(static_cast<Edge*>(this))=
+          ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
+        return *this; 
+      }
     };
 
@@ -290 +328 @@
     }
 
-    using GraphWrapper<Graph>::next;
-    OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
-    InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
-
-    Node aNode(const OutEdgeIt& e) const { 
-      return Node(this->graph->aNode(e.e)); }
-    Node aNode(const InEdgeIt& e) const { 
-      return Node(this->graph->aNode(e.e)); }
-    Node bNode(const OutEdgeIt& e) const { 
-      return Node(this->graph->bNode(e.e)); }
-    Node bNode(const InEdgeIt& e) const { 
-      return Node(this->graph->bNode(e.e)); }
+//     using GraphWrapper<Graph>::next;
+//     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
+//     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
+
+//     Node aNode(const OutEdgeIt& e) const { 
+//       return Node(this->graph->aNode(e.e)); }
+//     Node aNode(const InEdgeIt& e) const { 
+//       return Node(this->graph->aNode(e.e)); }
+//     Node bNode(const OutEdgeIt& e) const { 
+//       return Node(this->graph->bNode(e.e)); }
+//     Node bNode(const InEdgeIt& e) const { 
+//       return Node(this->graph->bNode(e.e)); }
 
     Node tail(const Edge& e) const { 
@@ -309 +347 @@
 
   };
-
-
 
   /// A graph wrapper for hiding nodes and edges from a graph.
@@ -627 +663 @@
     typedef GraphWrapper<Graph> Parent; 
   protected:
-    //const CapacityMap* capacity;
-    //FlowMap* flow;
-
     ForwardFilterMap* forward_filter;
     BackwardFilterMap* backward_filter;
@@ -648 +681 @@
       GraphWrapper<Graph>(_graph), 
       forward_filter(&_forward_filter), backward_filter(&_backward_filter) { }
+    SubBidirGraphWrapper(const SubBidirGraphWrapper<Graph, 
+                         ForwardFilterMap, BackwardFilterMap>& gw) : 
+      Parent(gw), 
+      forward_filter(gw.forward_filter), 
+      backward_filter(gw.backward_filter) { }
 
     class Edge; 
@@ -658 +696 @@
 
     typedef typename GraphWrapper<Graph>::Node Node;
-    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
-
+    //typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
+
+    typedef typename Graph::Edge GraphEdge;
     class Edge : public Graph::Edge {
       friend class SubBidirGraphWrapper<Graph, 
@@ -672 +711 @@
       Edge() { }
       ///\bug =false kell-e? zsoltnak kell az addEdge miatt
-      Edge(const typename Graph::Edge& _e, bool _backward=false) : 
-        Graph::Edge(_e), backward(_backward) { }
-      Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
+      Edge(const typename Graph::Edge& e, bool _backward/*=false*/) : 
+        Graph::Edge(e), backward(_backward) { }
+      Edge(Invalid i) : Graph::Edge(i), backward(true) { }
 //the unique invalid iterator
-      friend bool operator==(const Edge& u, const Edge& v) { 
-        return (v.backward==u.backward && 
-                static_cast<typename Graph::Edge>(u)==
+//       friend bool operator==(const Edge& u, const Edge& v) { 
+//      return (u.backward==v.backward && 
+//              static_cast<typename Graph::Edge>(u)==
+//              static_cast<typename Graph::Edge>(v));
+//       } 
+//       friend bool operator!=(const Edge& u, const Edge& v) { 
+//      return (u.backward!=v.backward || 
+//              static_cast<typename Graph::Edge>(u)!=
+//              static_cast<typename Graph::Edge>(v));
+//       }
+      bool operator==(const Edge& v) const { 
+        return (this->backward==v.backward && 
+                static_cast<typename Graph::Edge>(*this)==
                 static_cast<typename Graph::Edge>(v));
       } 
-      friend bool operator!=(const Edge& u, const Edge& v) { 
-        return (v.backward!=u.backward || 
-                static_cast<typename Graph::Edge>(u)!=
+      bool operator!=(const Edge& v) const { 
+        return (this->backward!=v.backward || 
+                static_cast<typename Graph::Edge>(*this)!=
                 static_cast<typename Graph::Edge>(v));
-      } 
-    };
-
-    class OutEdgeIt {
+      }
+    };
+
+    class OutEdgeIt : public Edge {
       friend class SubBidirGraphWrapper<Graph, 
                                         ForwardFilterMap, BackwardFilterMap>;
     protected:
-      typename Graph::OutEdgeIt out;
-      typename Graph::InEdgeIt in;
-      bool backward;
+      const SubBidirGraphWrapper<Graph, 
+                                 ForwardFilterMap, BackwardFilterMap>* gw;
     public:
       OutEdgeIt() { }
-      //FIXME
-//      OutEdgeIt(const Edge& e) : Edge(e) { }
-      OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
+      OutEdgeIt(Invalid i) : Edge(i) { }
 //the unique invalid iterator
       OutEdgeIt(const SubBidirGraphWrapper<Graph, 
-                ForwardFilterMap, BackwardFilterMap>& _G, Node v) { 
-        backward=false;
-        _G.graph->first(out, v);
-        while(_G.graph->valid(out) && !(*_G.forward_filter)[*this]) { _G.graph->next(out); }
-        if (!_G.graph->valid(out)) {
-          backward=true;
-          _G.graph->first(in, v);
-          while(_G.graph->valid(in) && !(*_G.backward_filter)[*this]) { _G.graph->next(in); }
+                ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) : 
+        Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) { 
+        while (*static_cast<GraphEdge*>(this)!=INVALID && 
+               !(*(gw->forward_filter))[*this]) 
+          *(static_cast<GraphEdge*>(this))=
+            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
+        if (*static_cast<GraphEdge*>(this)==INVALID) 
+          *static_cast<Edge*>(this)=
+            Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true);
+        while (*static_cast<GraphEdge*>(this)!=INVALID && 
+               !(*(gw->backward_filter))[*this]) 
+          *(static_cast<GraphEdge*>(this))=
+            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
+      }
+      OutEdgeIt(const SubBidirGraphWrapper<Graph, 
+                ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) : 
+        Edge(e), gw(&_gw) { }
+      OutEdgeIt& operator++() { 
+        if (!this->backward) {
+          Node n=gw->tail(*this);
+          *(static_cast<GraphEdge*>(this))=
+            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
+          while (*static_cast<GraphEdge*>(this)!=INVALID && 
+                 !(*(gw->forward_filter))[*this]) 
+            *(static_cast<GraphEdge*>(this))=
+              ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
+          if (*static_cast<GraphEdge*>(this)==INVALID) 
+            *static_cast<Edge*>(this)=
+              Edge(typename Graph::InEdgeIt(*(gw->graph), n), true);
+          while (*static_cast<GraphEdge*>(this)!=INVALID && 
+                 !(*(gw->backward_filter))[*this]) 
+            *(static_cast<GraphEdge*>(this))=
+              ++(typename Graph::InEdgeIt(*(gw->graph), *this));
+        } else {
+          *(static_cast<GraphEdge*>(this))=
+            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
+          while (*static_cast<GraphEdge*>(this)!=INVALID && 
+                 !(*(gw->backward_filter))[*this]) 
+            *(static_cast<GraphEdge*>(this))=
+              ++(typename Graph::InEdgeIt(*(gw->graph), *this));
         }
-      }
-      operator Edge() const { 
-//      Edge e;
-//      e.forward=this->forward;
-//      if (this->forward) e=out; else e=in;
-//      return e;
-        if (this->backward) 
-          return Edge(in, this->backward); 
-        else 
-          return Edge(out, this->backward);
-      }
-    };
-
-    class InEdgeIt {
+        return *this;
+      }
+    };
+
+    class InEdgeIt : public Edge {
       friend class SubBidirGraphWrapper<Graph, 
                                         ForwardFilterMap, BackwardFilterMap>;
     protected:
-      typename Graph::OutEdgeIt out;
-      typename Graph::InEdgeIt in;
-      bool backward;
+      const SubBidirGraphWrapper<Graph, 
+                                 ForwardFilterMap, BackwardFilterMap>* gw;
     public:
       InEdgeIt() { }
-      //FIXME
-//      OutEdgeIt(const Edge& e) : Edge(e) { }
-      InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
+      InEdgeIt(Invalid i) : Edge(i) { }
 //the unique invalid iterator
       InEdgeIt(const SubBidirGraphWrapper<Graph, 
-               ForwardFilterMap, BackwardFilterMap>& _G, Node v) { 
-        backward=false;
-        _G.graph->first(in, v);
-        while(_G.graph->valid(in) && !(*_G.forward_filter)[*this]) { _G.graph->next(in); }
-        if (!_G.graph->valid(in)) {
-          backward=true;
-          _G.graph->first(out, v);
-          while(_G.graph->valid(out) && !(*_G.backward_filter)[*this]) { _G.graph->next(out); }
+               ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) : 
+        Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) { 
+        while (*static_cast<GraphEdge*>(this)!=INVALID && 
+               !(*(gw->forward_filter))[*this]) 
+          *(static_cast<GraphEdge*>(this))=
+            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
+        if (*static_cast<GraphEdge*>(this)==INVALID) 
+          *static_cast<Edge*>(this)=
+            Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true);
+        while (*static_cast<GraphEdge*>(this)!=INVALID && 
+               !(*(gw->backward_filter))[*this]) 
+          *(static_cast<GraphEdge*>(this))=
+            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
+      }
+      InEdgeIt(const SubBidirGraphWrapper<Graph, 
+               ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) : 
+        Edge(e), gw(&_gw) { }
+      InEdgeIt& operator++() { 
+        if (!this->backward) {
+          Node n=gw->head(*this);
+          *(static_cast<GraphEdge*>(this))=
+            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
+          while (*static_cast<GraphEdge*>(this)!=INVALID && 
+                 !(*(gw->forward_filter))[*this]) 
+            *(static_cast<GraphEdge*>(this))=
+              ++(typename Graph::InEdgeIt(*(gw->graph), *this));
+          if (*static_cast<GraphEdge*>(this)==INVALID) 
+            *static_cast<Edge*>(this)=
+              Edge(typename Graph::OutEdgeIt(*(gw->graph), n), true);
+          while (*static_cast<GraphEdge*>(this)!=INVALID && 
+                 !(*(gw->backward_filter))[*this]) 
+            *(static_cast<GraphEdge*>(this))=
+              ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
+        } else {
+          *(static_cast<GraphEdge*>(this))=
+            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
+          while (*static_cast<GraphEdge*>(this)!=INVALID && 
+                 !(*(gw->backward_filter))[*this]) 
+            *(static_cast<GraphEdge*>(this))=
+              ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
         }
-      }
-      operator Edge() const { 
-//      Edge e;
-//      e.forward=this->forward;
-//      if (this->forward) e=out; else e=in;
-//      return e;
-        if (this->backward) 
-          return Edge(out, this->backward); 
-        else 
-          return Edge(in, this->backward);
-      }
-    };
-
-    class EdgeIt {
+        return *this;
+      }
+    };
+
+    class EdgeIt : public Edge {
       friend class SubBidirGraphWrapper<Graph, 
                                         ForwardFilterMap, BackwardFilterMap>;
     protected:
-      typename Graph::EdgeIt e;
-      bool backward;
+      const SubBidirGraphWrapper<Graph, 
+                                 ForwardFilterMap, BackwardFilterMap>* gw;
     public:
       EdgeIt() { }
-      EdgeIt(const Invalid& i) : e(i), backward(true) { }
+      EdgeIt(Invalid i) : Edge(i) { }
+//the unique invalid iterator
       EdgeIt(const SubBidirGraphWrapper<Graph, 
-             ForwardFilterMap, BackwardFilterMap>& _G) { 
-        backward=false;
-        _G.graph->first(e);
-        while (_G.graph->valid(e) && !(*_G.forward_filter)[*this]) _G.graph->next(e);
-        if (!_G.graph->valid(e)) {
-          backward=true;
-          _G.graph->first(e);
-          while (_G.graph->valid(e) && !(*_G.backward_filter)[*this]) _G.graph->next(e);
+                ForwardFilterMap, BackwardFilterMap>& _gw) : 
+        Edge(typename Graph::EdgeIt(*(_gw.graph)), false), gw(&_gw) { 
+        while (*static_cast<GraphEdge*>(this)!=INVALID && 
+               !(*(gw->forward_filter))[*this]) 
+          *(static_cast<GraphEdge*>(this))=
+            ++(typename Graph::EdgeIt(*(gw->graph), *this));
+        if (*static_cast<GraphEdge*>(this)==INVALID) 
+          *static_cast<Edge*>(this)=
+            Edge(typename Graph::EdgeIt(*(_gw.graph)), true);
+        while (*static_cast<GraphEdge*>(this)!=INVALID && 
+               !(*(gw->backward_filter))[*this]) 
+          *(static_cast<GraphEdge*>(this))=
+            ++(typename Graph::EdgeIt(*(gw->graph), *this));
+      }
+      EdgeIt(const SubBidirGraphWrapper<Graph, 
+             ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) : 
+        Edge(e), gw(&_gw) { }
+      EdgeIt& operator++() { 
+        if (!this->backward) {
+          *(static_cast<GraphEdge*>(this))=
+            ++(typename Graph::EdgeIt(*(gw->graph), *this));
+          while (*static_cast<GraphEdge*>(this)!=INVALID && 
+                 !(*(gw->forward_filter))[*this]) 
+            *(static_cast<GraphEdge*>(this))=
+              ++(typename Graph::EdgeIt(*(gw->graph), *this));
+          if (*static_cast<GraphEdge*>(this)==INVALID) 
+            *static_cast<Edge*>(this)=
+              Edge(typename Graph::EdgeIt(*(gw->graph)), true);
+          while (*static_cast<GraphEdge*>(this)!=INVALID && 
+                 !(*(gw->backward_filter))[*this]) 
+            *(static_cast<GraphEdge*>(this))=
+              ++(typename Graph::EdgeIt(*(gw->graph), *this));
+        } else {
+          *(static_cast<GraphEdge*>(this))=
+            ++(typename Graph::EdgeIt(*(gw->graph), *this));
+          while (*static_cast<GraphEdge*>(this)!=INVALID && 
+                 !(*(gw->backward_filter))[*this]) 
+            *(static_cast<GraphEdge*>(this))=
+              ++(typename Graph::EdgeIt(*(gw->graph), *this));
         }
-      }
-      operator Edge() const { 
-        return Edge(e, this->backward);
+        return *this;
       }
     };
@@ -800 +919 @@
     }
   
-    using GraphWrapper<Graph>::next;
-//    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
-    OutEdgeIt& next(OutEdgeIt& e) const { 
-      if (!e.backward) {
-        Node v=this->graph->aNode(e.out);
-        this->graph->next(e.out);
-        while(this->graph->valid(e.out) && !(*forward_filter)[e]) { 
-          this->graph->next(e.out); }
-        if (!this->graph->valid(e.out)) {
-          e.backward=true;
-          this->graph->first(e.in, v); 
-          while(this->graph->valid(e.in) && !(*backward_filter)[e]) { 
-            this->graph->next(e.in); }
-        }
-      } else {
-        this->graph->next(e.in);
-        while(this->graph->valid(e.in) && !(*backward_filter)[e]) { 
-          this->graph->next(e.in); } 
-      }
-      return e;
-    }
-//     FIXME Not tested
-    InEdgeIt& next(InEdgeIt& e) const { 
-      if (!e.backward) {
-        Node v=this->graph->aNode(e.in);
-        this->graph->next(e.in);
-        while(this->graph->valid(e.in) && !(*forward_filter)[e]) { 
-          this->graph->next(e.in); }
-        if (!this->graph->valid(e.in)) {
-          e.backward=true;
-          this->graph->first(e.out, v); 
-          while(this->graph->valid(e.out) && !(*backward_filter)[e]) { 
-            this->graph->next(e.out); }
-        }
-      } else {
-        this->graph->next(e.out);
-        while(this->graph->valid(e.out) && !(*backward_filter)[e]) { 
-          this->graph->next(e.out); } 
-      }
-      return e;
-    }
-    EdgeIt& next(EdgeIt& e) const {
-      if (!e.backward) {
-        this->graph->next(e.e);
-        while(this->graph->valid(e.e) && !(*forward_filter)[e]) { 
-          this->graph->next(e.e); }
-        if (!this->graph->valid(e.e)) {
-          e.backward=true;
-          this->graph->first(e.e); 
-          while(this->graph->valid(e.e) && !(*backward_filter)[e]) { 
-            this->graph->next(e.e); }
-        }
-      } else {
-        this->graph->next(e.e);
-        while(this->graph->valid(e.e) && !(*backward_filter)[e]) { 
-          this->graph->next(e.e); } 
-      }
-      return e;
-    }
+//     using GraphWrapper<Graph>::next;
+// //    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
+//     OutEdgeIt& next(OutEdgeIt& e) const { 
+//       if (!e.backward) {
+//      Node v=this->graph->aNode(e.out);
+//      this->graph->next(e.out);
+//      while(this->graph->valid(e.out) && !(*forward_filter)[e]) { 
+//        this->graph->next(e.out); }
+//      if (!this->graph->valid(e.out)) {
+//        e.backward=true;
+//        this->graph->first(e.in, v); 
+//        while(this->graph->valid(e.in) && !(*backward_filter)[e]) { 
+//          this->graph->next(e.in); }
+//      }
+//       } else {
+//      this->graph->next(e.in);
+//      while(this->graph->valid(e.in) && !(*backward_filter)[e]) { 
+//        this->graph->next(e.in); } 
+//       }
+//       return e;
+//     }
+// //     FIXME Not tested
+//     InEdgeIt& next(InEdgeIt& e) const { 
+//       if (!e.backward) {
+//      Node v=this->graph->aNode(e.in);
+//      this->graph->next(e.in);
+//      while(this->graph->valid(e.in) && !(*forward_filter)[e]) { 
+//        this->graph->next(e.in); }
+//      if (!this->graph->valid(e.in)) {
+//        e.backward=true;
+//        this->graph->first(e.out, v); 
+//        while(this->graph->valid(e.out) && !(*backward_filter)[e]) { 
+//          this->graph->next(e.out); }
+//      }
+//       } else {
+//      this->graph->next(e.out);
+//      while(this->graph->valid(e.out) && !(*backward_filter)[e]) { 
+//        this->graph->next(e.out); } 
+//       }
+//       return e;
+//     }
+//     EdgeIt& next(EdgeIt& e) const {
+//       if (!e.backward) {
+//      this->graph->next(e.e);
+//      while(this->graph->valid(e.e) && !(*forward_filter)[e]) { 
+//        this->graph->next(e.e); }
+//      if (!this->graph->valid(e.e)) {
+//        e.backward=true;
+//        this->graph->first(e.e); 
+//        while(this->graph->valid(e.e) && !(*backward_filter)[e]) { 
+//          this->graph->next(e.e); }
+//      }
+//       } else {
+//      this->graph->next(e.e);
+//      while(this->graph->valid(e.e) && !(*backward_filter)[e]) { 
+//        this->graph->next(e.e); } 
+//       }
+//       return e;
+//     }
 
     Node tail(Edge e) const { 
@@ -865 +984 @@
       return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
 
-    Node aNode(OutEdgeIt e) const { 
-      return ((!e.backward) ? this->graph->aNode(e.out) : 
-              this->graph->aNode(e.in)); }
-    Node bNode(OutEdgeIt e) const { 
-      return ((!e.backward) ? this->graph->bNode(e.out) : 
-              this->graph->bNode(e.in)); }
-
-    Node aNode(InEdgeIt e) const { 
-      return ((!e.backward) ? this->graph->aNode(e.in) : 
-              this->graph->aNode(e.out)); }
-    Node bNode(InEdgeIt e) const { 
-      return ((!e.backward) ? this->graph->bNode(e.in) : 
-              this->graph->bNode(e.out)); }
+//     Node aNode(OutEdgeIt e) const { 
+//       return ((!e.backward) ? this->graph->aNode(e.out) : 
+//            this->graph->aNode(e.in)); }
+//     Node bNode(OutEdgeIt e) const { 
+//       return ((!e.backward) ? this->graph->bNode(e.out) : 
+//            this->graph->bNode(e.in)); }
+
+//     Node aNode(InEdgeIt e) const { 
+//       return ((!e.backward) ? this->graph->aNode(e.in) : 
+//            this->graph->aNode(e.out)); }
+//     Node bNode(InEdgeIt e) const { 
+//       return ((!e.backward) ? this->graph->bNode(e.in) : 
+//            this->graph->bNode(e.out)); }
 
     /// Gives back the opposite edge.
@@ -894 +1013 @@
 //    int id(Node v) const { return graph->id(v); }
 
-    bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
-    bool valid(Edge e) const { 
-      return this->graph->valid(e);
-        //return e.forward ? graph->valid(e.out) : graph->valid(e.in); 
-    }
+//     bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
+//     bool valid(Edge e) const { 
+//       return this->graph->valid(e);
+//      //return e.forward ? graph->valid(e.out) : graph->valid(e.in); 
+//     }
 
     bool forward(const Edge& e) const { return !e.backward; }
@@ -940 +1059 @@
       typedef Edge KeyType;
       EdgeMap(const SubBidirGraphWrapper<Graph, 
-              ForwardFilterMap, BackwardFilterMap>& _G) : 
-        forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
+              ForwardFilterMap, BackwardFilterMap>& g) : 
+        forward_map(*(g.graph)), backward_map(*(g.graph)) { }
       EdgeMap(const SubBidirGraphWrapper<Graph, 
-              ForwardFilterMap, BackwardFilterMap>& _G, T a) : 
-        forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
+              ForwardFilterMap, BackwardFilterMap>& g, T a) : 
+        forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
       void set(Edge e, T a) { 
         if (!e.backward) 

src/hugo/list_graph.h

@@ -132 +132 @@
     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; }
@@ -147 +141 @@
       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; }
-
-    static bool valid(Edge e) { return e.n!=-1; }
-    static bool valid(Node n) { return n.n!=-1; }
-    
-    static void setInvalid(Edge &e) { e.n=-1; }
-    static void setInvalid(Node &n) { n.n=-1; }
-    
-    template <typename It> static It getNext(It it)
-    { It tmp(it); return next(tmp); }
-
-    NodeIt& next(NodeIt& it) const { 
-      it.n=nodes[it.n].next; 
-      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 {
-      if(edges[it.n].next_in!=-1) { 
-        it.n=edges[it.n].next_in;
-      }
-      else {
-        int n;
-        for(n=nodes[edges[it.n].head].next;
-            n!=-1 && nodes[n].first_in == -1;
-            n = nodes[n].next) ;
-        it.n = (n==-1)?-1:nodes[n].first_in;
-      }
-      return it;
-    }
-
     static int id(Node v) { return v.n; }
     static int id(Edge e) { return e.n; }
@@ -251 +208 @@
       return e;
     }
-
+    
+    /// Finds an edge between two nodes.
+
+    /// Finds an edge from node \c u to node \c v.
+    ///
+    /// If \c prev is \ref INVALID (this is the default value), then
+    /// It finds the first edge from \c u to \c v. Otherwise it looks for
+    /// the next edge from \c u to \c v after \c prev.
+    /// \return The found edge or INVALID if there is no such an edge.
+    Edge findEdge(Node u,Node v, Edge prev = INVALID) 
+    {
+      int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out;
+      while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out;
+      prev.n=e;
+      return prev;
+    }
+    
   private:
     void eraseEdge(int n) {
@@ -325 +298 @@
       bool operator!=(const Node i) const {return n!=i.n;}
       bool operator<(const Node i) const {return n<i.n;}
+      //      ///Validity check
+      //      operator bool() { return n!=-1; }
     };
     
     class NodeIt : public Node {
+      const ListGraph *G;
       friend class ListGraph;
     public:
       NodeIt() : Node() { }
       NodeIt(Invalid i) : Node(i) { }
-      NodeIt(const ListGraph& G) : Node(G.first_node) { }
+      NodeIt(const ListGraph& _G) : Node(_G.first_node), G(&_G) { }
       ///\todo Undocumented conversion Node -\> NodeIt.
-      NodeIt(const ListGraph& G, const Node &n) : Node(n) { }
+      NodeIt(const ListGraph& _G,Node n) : Node(n), G(&_G) { }
+      NodeIt &operator++() {
+        n=G->nodes[n].next; 
+        return *this; 
+      }
+      //      ///Validity check
+      //      operator bool() { return Node::operator bool(); }      
     };
 
@@ -365 +347 @@
       ///make class \c SymListGraph::SymEdgeMap friend of Edge
       int &idref() {return n;}
-      const int &idref() const {return n;}
-    };
+      const int &idref() const {return n;} 
+      //      ///Validity check
+      //      operator bool() { return n!=-1; }
+   };
     
     class EdgeIt : public Edge {
+      const ListGraph *G;
       friend class ListGraph;
     public:
-      EdgeIt(const ListGraph& G) : Edge() {
+      EdgeIt(const ListGraph& _G) : Edge(), G(&_G) {
         int m;
-        for(m=G.first_node;
-            m!=-1 && G.nodes[m].first_in == -1; m = G.nodes[m].next);
-        n = (m==-1)?-1:G.nodes[m].first_in;
+        for(m=_G.first_node;
+            m!=-1 && _G.nodes[m].first_in == -1; m = _G.nodes[m].next);
+        n = (m==-1)?-1:_G.nodes[m].first_in;
       }
       EdgeIt (Invalid i) : Edge(i) { }
+      EdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
       EdgeIt() : Edge() { }
       ///\bug This is a workaround until somebody tells me how to
       ///make class \c SymListGraph::SymEdgeMap friend of Edge
       int &idref() {return n;}
+      EdgeIt &operator++() {
+        if(G->edges[n].next_in!=-1) n=G->edges[n].next_in;
+        else {
+          int nn;
+          for(nn=G->nodes[G->edges[n].head].next;
+              nn!=-1 && G->nodes[nn].first_in == -1;
+              nn = G->nodes[nn].next) ;
+          n = (nn==-1)?-1:G->nodes[nn].first_in;
+        }
+        return *this;
+      }
+      //      ///Validity check
+      //      operator bool() { return Edge::operator bool(); }      
     };
     
     class OutEdgeIt : public Edge {
+      const ListGraph *G;
       friend class ListGraph;
     public: 
       OutEdgeIt() : Edge() { }
+      OutEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
       OutEdgeIt (Invalid i) : Edge(i) { }
 
-      OutEdgeIt(const ListGraph& G,const Node v)
-        : Edge(G.nodes[v.n].first_out) {}
+      OutEdgeIt(const ListGraph& _G,const Node v)
+        : Edge(_G.nodes[v.n].first_out), G(&_G) {}
+      OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; }
+      //      ///Validity check
+      //      operator bool() { return Edge::operator bool(); }      
     };
     
     class InEdgeIt : public Edge {
+      const ListGraph *G;
       friend class ListGraph;
     public: 
       InEdgeIt() : Edge() { }
+      InEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
       InEdgeIt (Invalid i) : Edge(i) { }
-      InEdgeIt(const ListGraph& G,Node v) :Edge(G.nodes[v.n].first_in) {}
+      InEdgeIt(const ListGraph& _G,Node v)
+        : Edge(_G.nodes[v.n].first_in), G(&_G) { }
+      InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
+      //      ///Validity check
+      //      operator bool() { return Edge::operator bool(); }      
     };
 
@@ -839 +849 @@
     Node head(Edge e) const { return INVALID; }
 
-    Node aNode(OutEdgeIt e) const { return INVALID; }
-    Node aNode(InEdgeIt e) const { return INVALID; }
-
-    Node bNode(OutEdgeIt e) const { return INVALID; }
-    Node bNode(InEdgeIt e) const { return INVALID; }
-
     NodeIt& first(NodeIt& v) const { 
       v=NodeIt(*this); return v; }
@@ -854 +858 @@
       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 false; }
-    bool valid(Node n) const { return n.n!=-1; }
-    
-    void setInvalid(Edge &e) { }
-    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=nodes[it.n].next; 
-      return it; 
-    }
-    OutEdgeIt& next(OutEdgeIt& it) const { return it; }
-    InEdgeIt& next(InEdgeIt& it) const { return it; }
-    EdgeIt& next(EdgeIt& it) const { return it; }
-
     int id(Node v) const { return v.n; }
     int id(Edge e) const { return -1; }
@@ -928 +909 @@
     }
     
+        
+    Edge findEdge(Node u,Node v, Edge prev = INVALID) 
+    {
+      return INVALID;
+    }
+    
     ///\bug Dynamic maps must be updated!
     ///
@@ -956 +943 @@
     
     class NodeIt : public Node {
+      const NodeSet *G;
       friend class NodeSet;
     public:
       NodeIt() : Node() { }
+      NodeIt(const NodeSet& _G,Node n) : Node(n), G(&_G) { }
       NodeIt(Invalid i) : Node(i) { }
-      NodeIt(const NodeSet& G) : Node(G.first_node) { }
-      ///\todo Undocumented conversion Node -\> NodeIt.
-      NodeIt(const NodeSet& G, const Node &n) : Node(n) { }
-
+      NodeIt(const NodeSet& _G) : Node(_G.first_node), G(&_G) { }
+      NodeIt &operator++() {
+        n=G->nodes[n].next; 
+        return *this; 
+      }
     };
 
@@ -994 +984 @@
     public:
       EdgeIt(const NodeSet& G) : Edge() { }
+      EdgeIt(const NodeSet&, Edge) : Edge() { }
       EdgeIt (Invalid i) : Edge(i) { }
       EdgeIt() : Edge() { }
@@ -999 +990 @@
       ///make class \c SymNodeSet::SymEdgeMap friend of Edge
       //      int idref() {return -1;}
+      EdgeIt operator++() { return INVALID; }
     };
     
@@ -1005 +997 @@
     public: 
       OutEdgeIt() : Edge() { }
+      OutEdgeIt(const NodeSet&, Edge) : Edge() { }
       OutEdgeIt (Invalid i) : Edge(i) { }
       OutEdgeIt(const NodeSet& G,const Node v)  : Edge() {}
+      OutEdgeIt operator++() { return INVALID; }
     };
     
@@ -1013 +1007 @@
     public: 
       InEdgeIt() : Edge() { }
+      InEdgeIt(const NodeSet&, Edge) : Edge() { }
       InEdgeIt (Invalid i) : Edge(i) { }
       InEdgeIt(const NodeSet& G,Node v) :Edge() {}
+      InEdgeIt operator++() { return INVALID; }
     };
 
@@ -1200 +1196 @@
     public:
       NodeIt() : NodeGraphType::NodeIt() { }
+      NodeIt(const EdgeSet& _G,Node n) : NodeGraphType::NodeIt(_G.G,n) { }
       NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {}
       NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { }
       NodeIt(const typename NodeGraphType::NodeIt &n)
         : NodeGraphType::NodeIt(n) {}
-      ///\todo Undocumented conversion Node -\> NodeIt.
-      NodeIt(const EdgeSet& _G, const Node &n)
-        : NodeGraphType::NodeIt(_G.G,n) { }
 
       operator Node() { return Node(*this);}
+      NodeIt &operator++()
+      { this->NodeGraphType::NodeIt::operator++(); return *this;} 
     };
 
@@ -1311 +1307 @@
     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 { 
@@ -1327 +1317 @@
       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 G.valid(n); }
-    
-    void setInvalid(Edge &e) { e.n=-1; }
-    void setInvalid(Node &n) { G.setInvalid(n); }
-    
-    template <typename It> It getNext(It it) const
-    { It tmp(it); return next(tmp); }
-
-    NodeIt& next(NodeIt& it) const { G.next(it); 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 {
-      if(edges[it.n].next_in!=-1) { 
-        it.n=edges[it.n].next_in;
-      }
-      else {
-        NodeIt n(*this,edges[it.n].head);
-        for(n=next(n);
-            valid(n) && nodes[n].first_in == -1;
-            next(n)) ;
-        it.n = (valid(n))?-1:nodes[n].first_in;
-      }
-      return it;
-    }
-
     int id(Edge e) const { return e.n; }
 
@@ -1399 +1355 @@
     }
 
+    /// Finds an edge between two nodes.
+
+    /// Finds an edge from node \c u to node \c v.
+    ///
+    /// If \c prev is \ref INVALID (this is the default value), then
+    /// It finds the first edge from \c u to \c v. Otherwise it looks for
+    /// the next edge from \c u to \c v after \c prev.
+    /// \return The found edge or INVALID if there is no such an edge.
+    Edge findEdge(Node u,Node v, Edge prev = INVALID) 
+    {
+      int e = (prev.n==-1)? nodes[u].first_out : edges[prev.n].next_out;
+      while(e!=-1 && edges[e].tail!=v) e = edges[e].next_out;
+      prev.n=e;
+      return prev;
+    }
+    
   private:
     void eraseEdge(int n) {
@@ -1461 +1433 @@
       friend class NodeIt;
     public:
-      ///\bug It shoud be at least protected
+      ///\bug It should be at least protected
       ///
       int n;
@@ -1484 +1456 @@
       template <typename T> friend class EdgeMap;
     
-      
-    public:
-      EdgeIt(const EdgeSet& G) : Edge() {
+      const EdgeSet *G;
+    public:
+      EdgeIt(const EdgeSet& _G) : Edge(), G(&_G) {
         //              typename NodeGraphType::Node m;
         NodeIt m;
-        for(G.first(m);
-            G.valid(m) && G.nodes[m].first_in == -1;  G.next(m));
-        //AJJAJ! This is a non sense!!!!!!!
-        this->n = G.valid(m)?-1:G.nodes[m].first_in;
-      }
+        for(G->first(m);
+            m!=INVALID && G->nodes[m].first_in == -1;  ++m);
+        ///\bug AJJAJ! This is a non sense!!!!!!!
+        this->n = m!=INVALID?-1:G->nodes[m].first_in;
+      }
+      EdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
       EdgeIt (Invalid i) : Edge(i) { }
       EdgeIt() : Edge() { }
-      ///\bug This is a workaround until somebody tells me how to
+      ///.
+      
+      ///\bug UNIMPLEMENTED!!!!!
+      //
+      EdgeIt &operator++() {
+        return *this;
+      }
+       ///\bug This is a workaround until somebody tells me how to
       ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
       int &idref() {return this->n;}
@@ -1502 +1482 @@
     
     class OutEdgeIt : public Edge {
+      const EdgeSet *G;
       friend class EdgeSet;
     public: 
       OutEdgeIt() : Edge() { }
       OutEdgeIt (Invalid i) : Edge(i) { }
-
-      OutEdgeIt(const EdgeSet& G,const Node v) : Edge(G.nodes[v].first_out) { }
+      OutEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
+
+      OutEdgeIt(const EdgeSet& _G,const Node v) :
+        Edge(_G.nodes[v].first_out), G(&_G) { }
+      OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; }
     };
     
     class InEdgeIt : public Edge {
+      const EdgeSet *G;
       friend class EdgeSet;
     public: 
       InEdgeIt() : Edge() { }
       InEdgeIt (Invalid i) : Edge(i) { }
-      InEdgeIt(const EdgeSet& G,Node v) :Edge(G.nodes[v].first_in) { }
+      InEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
+      InEdgeIt(const EdgeSet& _G,Node v)
+        : Edge(_G.nodes[v].first_in), G(&_G) { }
+      InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
     };
 
@@ -1555 +1543 @@
         //FIXME: What if there are empty Id's?
         //FIXME: Can I use 'this' in a constructor?
-        G->dyn_edge_maps.push_back(this);
+        this->G->dyn_edge_maps.push_back(this);
       }
       EdgeMap(const EdgeSet &_G,const T &t) :
         DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
       {
-        G->dyn_edge_maps.push_back(this);
+        this->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);
+        this->G->dyn_edge_maps.push_back(this);
       }
 
@@ -1573 +1561 @@
         DynMapBase<Edge>(*m.G), container(m.container.size())
       {
-        G->dyn_edge_maps.push_back(this);
+        this->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();
@@ -1582 +1570 @@
       ~EdgeMap()
       {
-        if(G) {
+        if(this->G) {
           typename std::vector<DynMapBase<Edge>* >::iterator i;
-          for(i=G->dyn_edge_maps.begin();
-              i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
+          for(i=this->G->dyn_edge_maps.begin();
+              i!=this->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();
+            *i=this->G->dyn_edge_maps.back();
+            this->G->dyn_edge_maps.pop_back();
           }
         }
@@ -1603 +1591 @@
       ///\bug This doesn't work. Why?
       ///      void set(Edge n, T a) { container[n.n]=a; }
-      void set(Edge n, T a) { container[G->id(n)]=a; }
+      void set(Edge n, T a) { container[this->G->id(n)]=a; }
       //T get(Edge n) const { return container[n.n]; }
       typename std::vector<T>::reference
       ///\bug This doesn't work. Why?
       ///      operator[](Edge n) { return container[n.n]; }
-      operator[](Edge n) { return container[G->id(n)]; }
+      operator[](Edge n) { return container[this->G->id(n)]; }
       typename std::vector<T>::const_reference
       ///\bug This doesn't work. Why?
       ///      operator[](Edge n) const { return container[n.n]; }
-      operator[](Edge n) const { return container[G->id(n)]; }
+      operator[](Edge n) const { return container[this->G->id(n)]; }
 
       ///\warning There is no safety check at all!

src/hugo/max_flow.h

@@ -6 +6 @@
 #include <queue>
 
-#include <hugo/graph_wrapper.h>
+//#include <hugo/graph_wrapper.h>
 #include <hugo/invalid.h>
 #include <hugo/maps.h>
@@ -63 +63 @@
     FlowMap* flow;
     int n;      //the number of nodes of G
-    typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;   
+    //    typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;   
     //typedef ExpResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;
-    typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
-    typedef typename ResGW::Edge ResGWEdge;
+    //    typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
+    //    typedef typename ResGW::Edge ResGWEdge;
     typedef typename Graph::template NodeMap<int> ReachedMap;
 
@@ -113 +113 @@
     StatusEnum status;
 
-//     int number_of_augmentations;
-
-
-//     template<typename IntMap>
-//     class TrickyReachedMap {
-//     protected:
-//       IntMap* map;
-//       int* number_of_augmentations;
-//     public:
-//       TrickyReachedMap(IntMap& _map, int& _number_of_augmentations) : 
-//      map(&_map), number_of_augmentations(&_number_of_augmentations) { }
-//       void set(const Node& n, bool b) {
-//      if (b)
-//        map->set(n, *number_of_augmentations);
-//      else 
-//        map->set(n, *number_of_augmentations-1);
-//       }
-//       bool operator[](const Node& n) const { 
-//      return (*map)[n]==*number_of_augmentations; 
-//       }
-//     };
+    //     int number_of_augmentations;
+
+
+    //     template<typename IntMap>
+    //     class TrickyReachedMap {
+    //     protected:
+    //       IntMap* map;
+    //       int* number_of_augmentations;
+    //     public:
+    //       TrickyReachedMap(IntMap& _map, int& _number_of_augmentations) : 
+    //  map(&_map), number_of_augmentations(&_number_of_augmentations) { }
+    //       void set(const Node& n, bool b) {
+    //  if (b)
+    //    map->set(n, *number_of_augmentations);
+    //  else 
+    //    map->set(n, *number_of_augmentations-1);
+    //       }
+    //       bool operator[](const Node& n) const { 
+    //  return (*map)[n]==*number_of_augmentations; 
+    //       }
+    //     };
     
     ///Constructor
@@ -235 +235 @@
         }
 
-        if ( !g->valid(first[b]) ) --b;
+        if ( first[b]==INVALID ) --b;
         else {
           end=false;
@@ -290 +290 @@
         int l=level[v]+1;
 
-        InEdgeIt e;
-        for(g->first(e,v); g->valid(e); g->next(e)) {
+        for(InEdgeIt e(*g,v); e!=INVALID; ++e) {
           if ( (*capacity)[e] <= (*flow)[e] ) continue;
           Node u=g->tail(e);
@@ -304 +303 @@
         }
 
-        OutEdgeIt f;
-        for(g->first(f,v); g->valid(f); g->next(f)) {
-          if ( 0 >= (*flow)[f] ) continue;
-          Node u=g->head(f);
+        for(OutEdgeIt e(*g,v); e!=INVALID; ++e) {
+          if ( 0 >= (*flow)[e] ) continue;
+          Node u=g->head(e);
           if ( level[u] >= n ) {
             bfs_queue.push(u);
@@ -324 +322 @@
         if ( b == 0 ) break;
 
-        if ( !g->valid(first[b]) ) --b;
+        if ( first[b]==INVALID ) --b;
         else {
 
@@ -352 +350 @@
     /// It can be called already after running \ref preflowPhase1.
     Num flowValue() const {
-//       Num a=0;
-//       for(InEdgeIt e(*g,t);g->valid(e);g->next(e)) a+=(*flow)[e];
-//       for(OutEdgeIt e(*g,t);g->valid(e);g->next(e)) a-=(*flow)[e];
-//       return a;
+      //       Num a=0;
+      //       for(InEdgeIt e(*g,t);g->valid(e);g->next(e)) a+=(*flow)[e];
+      //       for(OutEdgeIt e(*g,t);g->valid(e);g->next(e)) a-=(*flow)[e];
+      //       return a;
       return excess[t];
       //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan   
@@ -375 +373 @@
     template<typename _CutMap>
     void actMinCut(_CutMap& M) const {
-      NodeIt v;
       switch (status) {
-      case AFTER_PRE_FLOW_PHASE_1:
-        for(g->first(v); g->valid(v); g->next(v)) {
+        case AFTER_PRE_FLOW_PHASE_1:
+        for(NodeIt v(*g); v!=INVALID; ++v) {
           if (level[v] < n) {
             M.set(v, false);
@@ -386 +383 @@
         }
         break;
-      case AFTER_PRE_FLOW_PHASE_2:
-      case AFTER_NOTHING:
-      case AFTER_AUGMENTING:
-      case AFTER_FAST_AUGMENTING:
+        case AFTER_PRE_FLOW_PHASE_2:
+        case AFTER_NOTHING:
+        case AFTER_AUGMENTING:
+        case AFTER_FAST_AUGMENTING:
         minMinCut(M);
         break;
@@ -413 +410 @@
         queue.pop();
 
-        OutEdgeIt e;
-        for(g->first(e,w) ; g->valid(e); g->next(e)) {
+        for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) {
           Node v=g->head(e);
           if (!M[v] && (*flow)[e] < (*capacity)[e] ) {
@@ -422 +418 @@
         }
 
-        InEdgeIt f;
-        for(g->first(f,w) ; g->valid(f); g->next(f)) {
-          Node v=g->tail(f);
-          if (!M[v] && (*flow)[f] > 0 ) {
+        for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) {
+          Node v=g->tail(e);
+          if (!M[v] && (*flow)[e] > 0 ) {
             queue.push(v);
             M.set(v, true);
@@ -443 +438 @@
     void maxMinCut(_CutMap& M) const {
 
-      NodeIt v;
-      for(g->first(v) ; g->valid(v); g->next(v)) {
-        M.set(v, true);
-      }
+      for(NodeIt v(*g) ; v!=INVALID; ++v) M.set(v, true);
 
       std::queue<Node> queue;
@@ -457 +449 @@
         queue.pop();
 
-        InEdgeIt e;
-        for(g->first(e,w) ; g->valid(e); g->next(e)) {
+        for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) {
           Node v=g->tail(e);
           if (M[v] && (*flow)[e] < (*capacity)[e] ) {
@@ -466 +457 @@
         }
 
-        OutEdgeIt f;
-        for(g->first(f,w) ; g->valid(f); g->next(f)) {
-          Node v=g->head(f);
-          if (M[v] && (*flow)[f] > 0 ) {
+        for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) {
+          Node v=g->head(e);
+          if (M[v] && (*flow)[e] > 0 ) {
             queue.push(v);
             M.set(v, false);
@@ -519 +509 @@
       int newlevel=n;       //bound on the next level of w
 
-      OutEdgeIt e;
-      for(g->first(e,w); g->valid(e); g->next(e)) {
-
+      for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) {
         if ( (*flow)[e] >= (*capacity)[e] ) continue;
         Node v=g->head(e);
 
         if( lev > level[v] ) { //Push is allowed now
-
+          
           if ( excess[v]<=0 && v!=t && v!=s ) {
             next.set(v,first[level[v]]);
@@ -535 +523 @@
           Num flo=(*flow)[e];
           Num remcap=cap-flo;
-
+          
           if ( remcap >= exc ) { //A nonsaturating push.
-
+            
             flow->set(e, flo+exc);
             excess.set(v, excess[v]+exc);
@@ -552 +540 @@
 
       if ( exc > 0 ) {
-        InEdgeIt e;
-        for(g->first(e,w); g->valid(e); g->next(e)) {
-
+        for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) {
+          
           if( (*flow)[e] <= 0 ) continue;
           Node v=g->tail(e);
@@ -585 +572 @@
 
       excess.set(w, exc);
-
+      
       return newlevel;
     }
-
-
-
+    
+    
+    
     void preflowPreproc(FlowEnum fe, NNMap& next, VecFirst& first,
                         VecNode& level_list, NNMap& left, NNMap& right)
     {
-      switch (fe) { //setting excess
+      switch (fe) {  //setting excess
         case NO_FLOW: 
+        for(EdgeIt e(*g); e!=INVALID; ++e) flow->set(e,0);
+        for(NodeIt v(*g); v!=INVALID; ++v) excess.set(v,0);
+        break;
+        case ZERO_FLOW: 
+        for(NodeIt v(*g); v!=INVALID; ++v) excess.set(v,0);
+        break;
+        case GEN_FLOW:
+        for(NodeIt v(*g); v!=INVALID; ++v) excess.set(v,0);
         {
-          EdgeIt e;
-          for(g->first(e); g->valid(e); g->next(e)) flow->set(e,0);
-          
-          NodeIt v;
-          for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
-          break;
-        }
-        case ZERO_FLOW: 
-        {
-          NodeIt v;
-          for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
-          break;
-        }
-        case GEN_FLOW:
-        {
-          NodeIt v;
-          for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
-
           Num exc=0;
-          InEdgeIt e;
-          for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e];
-          OutEdgeIt f;
-          for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f];
+          for(InEdgeIt e(*g,t) ; e!=INVALID; ++e) exc+=(*flow)[e];
+          for(OutEdgeIt e(*g,t) ; e!=INVALID; ++e) exc-=(*flow)[e];
           excess.set(t,exc);
-          break;
-        }
-        default: break;
-      }
-
-      NodeIt v;
-      for(g->first(v); g->valid(v); g->next(v)) level.set(v,n);
+        }
+        break;
+        default:
+        break;
+      }
+      
+      for(NodeIt v(*g); v!=INVALID; ++v) level.set(v,n);
       //setting each node to level n
       
@@ -636 +611 @@
       case NO_FLOW:   //flow is already set to const zero
       case ZERO_FLOW:
-        {
-          //Reverse_bfs from t, to find the starting level.
-          level.set(t,0);
-          bfs_queue.push(t);
-
-          while (!bfs_queue.empty()) {
-
-            Node v=bfs_queue.front();
-            bfs_queue.pop();
-            int l=level[v]+1;
-
-            InEdgeIt e;
-            for(g->first(e,v); g->valid(e); g->next(e)) {
-              Node w=g->tail(e);
-              if ( level[w] == n && w != s ) {
-                bfs_queue.push(w);
-                Node z=level_list[l];
-                if ( g->valid(z) ) left.set(z,w);
-                right.set(w,z);
-                level_list[l]=w;
-                level.set(w, l);
-              }
-            }
-          }
-
-          //the starting flow
-          OutEdgeIt e;
-          for(g->first(e,s); g->valid(e); g->next(e))
+        //Reverse_bfs from t, to find the starting level.
+        level.set(t,0);
+        bfs_queue.push(t);
+        
+        while (!bfs_queue.empty()) {
+          
+          Node v=bfs_queue.front();
+          bfs_queue.pop();
+          int l=level[v]+1;
+          
+          for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) {
+            Node w=g->tail(e);
+            if ( level[w] == n && w != s ) {
+              bfs_queue.push(w);
+              Node z=level_list[l];
+              if ( z!=INVALID ) left.set(z,w);
+              right.set(w,z);
+              level_list[l]=w;
+              level.set(w, l);
+            }
+          }
+        }
+        
+        //the starting flow
+        for(OutEdgeIt e(*g,s) ; e!=INVALID; ++e)
+          {
+            Num c=(*capacity)[e];
+            if ( c <= 0 ) continue;
+            Node w=g->head(e);
+            if ( level[w] < n ) {
+              if ( excess[w] <= 0 && w!=t ) //putting into the stack
+                { 
+                  next.set(w,first[level[w]]);
+                  first[level[w]]=w;
+                }
+              flow->set(e, c);
+              excess.set(w, excess[w]+c);
+            }
+          }
+        break;
+      case GEN_FLOW:
+        //Reverse_bfs from t in the residual graph,
+        //to find the starting level.
+        level.set(t,0);
+        bfs_queue.push(t);
+        
+        while (!bfs_queue.empty()) {
+          
+          Node v=bfs_queue.front();
+          bfs_queue.pop();
+          int l=level[v]+1;
+          
+          for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) {
+            if ( (*capacity)[e] <= (*flow)[e] ) continue;
+            Node w=g->tail(e);
+            if ( level[w] == n && w != s ) {
+              bfs_queue.push(w);
+              Node z=level_list[l];
+              if ( z!=INVALID ) left.set(z,w);
+              right.set(w,z);
+              level_list[l]=w;
+              level.set(w, l);
+            }
+          }
+          
+          for(OutEdgeIt e(*g,v) ; e!=INVALID; ++e) {
+            if ( 0 >= (*flow)[e] ) continue;
+            Node w=g->head(e);
+            if ( level[w] == n && w != s ) {
+              bfs_queue.push(w);
+              Node z=level_list[l];
+              if ( z!=INVALID ) left.set(z,w);
+              right.set(w,z);
+              level_list[l]=w;
+              level.set(w, l);
+            }
+          }
+        }
+        
+        //the starting flow
+        for(OutEdgeIt e(*g,s); e!=INVALID; ++e)
+          {
+            Num rem=(*capacity)[e]-(*flow)[e];
+            if ( rem <= 0 ) continue;
+            Node w=g->head(e);
+            if ( level[w] < n ) {
+              if ( excess[w] <= 0 && w!=t ) //putting into the stack
+                {
+                  next.set(w,first[level[w]]);
+                  first[level[w]]=w;
+                }   
+              flow->set(e, (*capacity)[e]);
+              excess.set(w, excess[w]+rem);
+            }
+          }
+        
+        for(InEdgeIt e(*g,s); e!=INVALID; ++e)
+          {
+            if ( (*flow)[e] <= 0 ) continue;
+            Node w=g->tail(e);
+            if ( level[w] < n ) {
+              if ( excess[w] <= 0 && w!=t )
+                {
+                  next.set(w,first[level[w]]);
+                  first[level[w]]=w;
+                }  
+              excess.set(w, excess[w]+(*flow)[e]);
+              flow->set(e, 0);
+            }
+          }
+        break;
+      case PRE_FLOW:
+        //Reverse_bfs from t in the residual graph,
+        //to find the starting level.
+        level.set(t,0);
+        bfs_queue.push(t);
+        
+        while (!bfs_queue.empty()) {
+          
+          Node v=bfs_queue.front();
+          bfs_queue.pop();
+          int l=level[v]+1;
+          
+          for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) {
+            if ( (*capacity)[e] <= (*flow)[e] ) continue;
+            Node w=g->tail(e);
+            if ( level[w] == n && w != s ) {
+              bfs_queue.push(w);
+              Node z=level_list[l];
+              if ( z!=INVALID ) left.set(z,w);
+              right.set(w,z);
+              level_list[l]=w;
+              level.set(w, l);
+            }
+          }
+          
+          for(OutEdgeIt e(*g,v) ; e!=INVALID; ++e) {
+            if ( 0 >= (*flow)[e] ) continue;
+            Node w=g->head(e);
+            if ( level[w] == n && w != s ) {
+              bfs_queue.push(w);
+              Node z=level_list[l];
+              if ( z!=INVALID ) left.set(z,w);
+              right.set(w,z);
+              level_list[l]=w;
+              level.set(w, l);
+            }
+          }
+        }
+        
+        
+        //the starting flow
+        for(OutEdgeIt e(*g,s) ; e!=INVALID; ++e) {
+          Num rem=(*capacity)[e]-(*flow)[e];
+          if ( rem <= 0 ) continue;
+          Node w=g->head(e);
+          if ( level[w] < n ) {
+            flow->set(e, (*capacity)[e]);
+            excess.set(w, excess[w]+rem);
+          }
+        }
+        
+        for(InEdgeIt e(*g,s) ; e!=INVALID; ++e) {
+          if ( (*flow)[e] <= 0 ) continue;
+          Node w=g->tail(e);
+          if ( level[w] < n ) {
+            excess.set(w, excess[w]+(*flow)[e]);
+            flow->set(e, 0);
+          }
+        }
+        
+        //computing the excess
+        for(NodeIt w(*g); w!=INVALID; ++w) {
+          Num exc=0;
+          
+          for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) exc+=(*flow)[e];
+          for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) exc-=(*flow)[e];
+          
+          excess.set(w,exc);
+          
+          //putting the active nodes into the stack
+          int lev=level[w];
+            if ( exc > 0 && lev < n && Node(w) != t ) 
+              ///\bug       if ( exc > 0 && lev < n && w != t ) temporarily for working with wrappers. 
             {
-              Num c=(*capacity)[e];
-              if ( c <= 0 ) continue;
-              Node w=g->head(e);
-              if ( level[w] < n ) {
-                if ( excess[w] <= 0 && w!=t ) //putting into the stack
-                  { 
-                    next.set(w,first[level[w]]);
-                    first[level[w]]=w;
-                  }
-                flow->set(e, c);
-                excess.set(w, excess[w]+c);
-              }
-            }
-          break;
-        }
-
-      case GEN_FLOW:
-        {
-          //Reverse_bfs from t in the residual graph,
-          //to find the starting level.
-          level.set(t,0);
-          bfs_queue.push(t);
-
-          while (!bfs_queue.empty()) {
-
-            Node v=bfs_queue.front();
-            bfs_queue.pop();
-            int l=level[v]+1;
-
-            InEdgeIt e;
-            for(g->first(e,v); g->valid(e); g->next(e)) {
-              if ( (*capacity)[e] <= (*flow)[e] ) continue;
-              Node w=g->tail(e);
-              if ( level[w] == n && w != s ) {
-                bfs_queue.push(w);
-                Node z=level_list[l];
-                if ( g->valid(z) ) left.set(z,w);
-                right.set(w,z);
-                level_list[l]=w;
-                level.set(w, l);
-              }
-            }
-
-            OutEdgeIt f;
-            for(g->first(f,v); g->valid(f); g->next(f)) {
-              if ( 0 >= (*flow)[f] ) continue;
-              Node w=g->head(f);
-              if ( level[w] == n && w != s ) {
-                bfs_queue.push(w);
-                Node z=level_list[l];
-                if ( g->valid(z) ) left.set(z,w);
-                right.set(w,z);
-                level_list[l]=w;
-                level.set(w, l);
-              }
-            }
-          }
-
-          //the starting flow
-          OutEdgeIt e;
-          for(g->first(e,s); g->valid(e); g->next(e))
-            {
-              Num rem=(*capacity)[e]-(*flow)[e];
-              if ( rem <= 0 ) continue;
-              Node w=g->head(e);
-              if ( level[w] < n ) {
-                if ( excess[w] <= 0 && w!=t ) //putting into the stack
-                  {
-                    next.set(w,first[level[w]]);
-                    first[level[w]]=w;
-                  }   
-                flow->set(e, (*capacity)[e]);
-                excess.set(w, excess[w]+rem);
-              }
-            }
-
-          InEdgeIt f;
-          for(g->first(f,s); g->valid(f); g->next(f))
-            {
-              if ( (*flow)[f] <= 0 ) continue;
-              Node w=g->tail(f);
-              if ( level[w] < n ) {
-                if ( excess[w] <= 0 && w!=t )
-                  {
-                    next.set(w,first[level[w]]);
-                    first[level[w]]=w;
-                  }  
-                excess.set(w, excess[w]+(*flow)[f]);
-                flow->set(f, 0);
-              }
-            }
-          break;
-        } //case GEN_FLOW
-    
-      case PRE_FLOW:
-        {
-          //Reverse_bfs from t in the residual graph,
-          //to find the starting level.
-          level.set(t,0);
-          bfs_queue.push(t);
-
-          while (!bfs_queue.empty()) {
-
-            Node v=bfs_queue.front();
-            bfs_queue.pop();
-            int l=level[v]+1;
-
-            InEdgeIt e;
-            for(g->first(e,v); g->valid(e); g->next(e)) {
-              if ( (*capacity)[e] <= (*flow)[e] ) continue;
-              Node w=g->tail(e);
-              if ( level[w] == n && w != s ) {
-                bfs_queue.push(w);
-                Node z=level_list[l];
-                if ( g->valid(z) ) left.set(z,w);
-                right.set(w,z);
-                level_list[l]=w;
-                level.set(w, l);
-              }
-            }
-
-            OutEdgeIt f;
-            for(g->first(f,v); g->valid(f); g->next(f)) {
-              if ( 0 >= (*flow)[f] ) continue;
-              Node w=g->head(f);
-              if ( level[w] == n && w != s ) {
-                bfs_queue.push(w);
-                Node z=level_list[l];
-                if ( g->valid(z) ) left.set(z,w);
-                right.set(w,z);
-                level_list[l]=w;
-                level.set(w, l);
-              }
-            }
-          }
-
-
-          //the starting flow
-          OutEdgeIt e;
-          for(g->first(e,s); g->valid(e); g->next(e))
-            {
-              Num rem=(*capacity)[e]-(*flow)[e];
-              if ( rem <= 0 ) continue;
-              Node w=g->head(e);
-              if ( level[w] < n ) {
-                flow->set(e, (*capacity)[e]);
-                excess.set(w, excess[w]+rem);
-              }
-            }
-
-          InEdgeIt f;
-          for(g->first(f,s); g->valid(f); g->next(f))
-            {
-              if ( (*flow)[f] <= 0 ) continue;
-              Node w=g->tail(f);
-              if ( level[w] < n ) {
-                excess.set(w, excess[w]+(*flow)[f]);
-                flow->set(f, 0);
-              }
-            }
-          
-          NodeIt w; //computing the excess
-          for(g->first(w); g->valid(w); g->next(w)) {
-            Num exc=0;
-
-            InEdgeIt e;
-            for(g->first(e,w); g->valid(e); g->next(e)) exc+=(*flow)[e];
-            OutEdgeIt f;
-            for(g->first(f,w); g->valid(f); g->next(f)) exc-=(*flow)[f];
-
-            excess.set(w,exc);
-
-            //putting the active nodes into the stack
-            int lev=level[w];
-            if ( exc > 0 && lev < n && Node(w) != t ) 
-///\bug     if ( exc > 0 && lev < n && w != t ) tempararily for working with wrappers. in hugo 0.2 it will work. Amugy mukodik sage_graph-fal, de smart_graph-fal nem, azt hozzatennem.
-              {
-                next.set(w,first[lev]);
-                first[lev]=w;
-              }
-          }
-          break;
-        } //case PRE_FLOW
-      }
+              next.set(w,first[lev]);
+              first[lev]=w;
+            }
+        }
+        break;
+      } //switch
     } //preflowPreproc
 
@@ -863 +816 @@
 
       //unlacing starts
-      if ( g->valid(right_n) ) {
-        if ( g->valid(left_n) ) {
+      if ( right_n!=INVALID ) {
+        if ( left_n!=INVALID ) {
           right.set(left_n, right_n);
           left.set(right_n, left_n);
@@ -872 +825 @@
         }
       } else {
-        if ( g->valid(left_n) ) {
+        if ( left_n!=INVALID ) {
           right.set(left_n, INVALID);
         } else {
@@ -880 +833 @@
       //unlacing ends
 
-      if ( !g->valid(level_list[lev]) ) {
+      if ( level_list[lev]==INVALID ) {
 
         //gapping starts
         for (int i=lev; i!=k ; ) {
           Node v=level_list[++i];
-          while ( g->valid(v) ) {
+          while ( v!=INVALID ) {
             level.set(v,n);
             v=right[v];
@@ -908 +861 @@
           if ( k < newlevel ) ++k;      //now k=newlevel
           Node z=level_list[newlevel];
-          if ( g->valid(z) ) left.set(z,w);
+          if ( z!=INVALID ) left.set(z,w);
           right.set(w,z);
           left.set(w,INVALID);
@@ -919 +872 @@
       std::cout << "Excesses:" <<std::endl;
 
-      NodeIt v;
-      for(g->first(v); g->valid(v); g->next(v)) {
+      for(NodeIt v(*g); v!=INVALID ; ++v) {
         std::cout << 1+(g->id(v)) << ":" << excess[v]<<std::endl; 
       }
     }
 
- void printlevel() {////
+    void printlevel() {////
       std::cout << "Levels:" <<std::endl;
 
-      NodeIt v;
-      for(g->first(v); g->valid(v); g->next(v)) {
+      for(NodeIt v(*g); v!=INVALID ; ++v) {
         std::cout << 1+(g->id(v)) << ":" << level[v]<<std::endl; 
       }
     }
 
-void printactive() {////
+    void printactive() {////
       std::cout << "Levels:" <<std::endl;
 
-      NodeIt v;
-      for(g->first(v); g->valid(v); g->next(v)) {
+      for(NodeIt v(*g); v!=INVALID ; ++v) {
         std::cout << 1+(g->id(v)) << ":" << level[v]<<std::endl; 
       }

src/hugo/skeletons/graph.h

@@ -35 +35 @@
     public:
       /// Defalult constructor.
-      StaticGraphSkeleton() {}
+      StaticGraphSkeleton() { }
       ///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?
-      StaticGraphSkeleton(const StaticGraphSkeleton &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.
+      StaticGraphSkeleton(const StaticGraphSkeleton& g) { }
+
+      /// The base type of node iterators, 
+      /// or in other words, the trivial node iterator.
+
+      /// This is the base type of each node iterator,
+      /// thus each kind of node iterator converts to this.
+      /// More precisely each kind of node iterator have to be inherited 
+      /// from the trivial node iterator.
       class Node {
       public:
         /// @warning The default constructor sets the iterator
         /// to an undefined value.
-        Node() {}   //FIXME
+        Node() { }
+        /// Copy constructor.
+        Node(const Node&) { }
         /// Invalid constructor \& conversion.
 
         /// This constructor initializes the iterator to be invalid.
         /// \sa Invalid for more details.
-
-        Node(Invalid) {}
-        //Node(const Node &) {}
-
+        Node(Invalid) { }
         /// Two iterators are equal if and only if they point to the
         /// same object or both are invalid.
@@ -74 +76 @@
       /// 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:
+      /// 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++;
+      /// int count=0;
+      /// for (Graph::NodeIt n(g); g.valid(n); ++n) ++count;
       /// \endcode
       class NodeIt : public Node {
@@ -83 +85 @@
         /// @warning The default constructor sets the iterator
         /// to an undefined value.
-        NodeIt() {} //FIXME
+        NodeIt() { }
+        /// Copy constructor.
+        NodeIt(const NodeIt&) { }
         /// Invalid constructor \& conversion.
 
-        /// Initialize the iterator to be invalid
+        /// 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 StaticGraphSkeleton &) {}
-        /// @warning The default constructor sets the iterator
-        /// to an undefined value.
-        NodeIt(const NodeIt &n) : Node(n) {}
+        NodeIt(Invalid) { }
+        /// Sets the iterator to the first node of \c g.
+        NodeIt(const StaticGraphSkeleton& g) { }
+        /// Sets the iterator to the node of \c g pointed by the trivial 
+        /// iterator n. This feature necessitates that each time we 
+        /// iterate the node-set, the iteration order is the same.
+        NodeIt(const StaticGraphSkeleton& g, const Node& n) { }
+        /// Assign the iterator to the next node.
+        NodeIt& operator++() { return *this; }
       };
     
@@ -102 +109 @@
         /// @warning The default constructor sets the iterator
         /// to an undefined value.
-        Edge() {}   //FIXME
-        /// Initialize the iterator to be invalid
-        Edge(Invalid) {}
+        Edge() { }
+        /// Copy constructor.
+        Edge(const Edge&) { }
+        /// 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.
@@ -118 +127 @@
       /// 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.
+      /// 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++;
+      /// int count=0;
+      /// for (Graph::OutEdgeIt e(g, n); g.valid(e); ++e) ++count;
       /// \endcode
     
@@ -128 +137 @@
         /// @warning The default constructor sets the iterator
         /// to an undefined value.
-        OutEdgeIt() {}
-        /// Initialize the iterator to be invalid
-        OutEdgeIt(Invalid) {}
+        OutEdgeIt() { }
+        /// Copy constructor.
+        OutEdgeIt(const OutEdgeIt&) { }
+        /// Initialize the iterator to be invalid.
+        OutEdgeIt(Invalid) { }
         /// This constructor sets the iterator to first outgoing edge.
     
@@ -136 +147 @@
         /// node
         ///@param n the node
-        ///@param G the graph
-        OutEdgeIt(const StaticGraphSkeleton &, Node) {}
+        ///@param g the graph
+        OutEdgeIt(const StaticGraphSkeleton& g, const Node& n) { }
+        /// Sets the iterator to the value of the trivial iterator \c e.
+        /// This feature necessitates that each time we 
+        /// iterate the edge-set, the iteration order is the same.
+        OutEdgeIt(const StaticGraphSkeleton& g, const Edge& e) { }
+        /// Assign the iterator to the next outedge of the corresponding node.
+        OutEdgeIt& operator++() { return *this; }
       };
 
@@ -146 +163 @@
       /// 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.
+      /// 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++;
+      /// int count=0;
+      /// for(Graph::InEdgeIt e(g, n); g.valid(e); ++) ++count;
       /// \endcode
 
@@ -156 +173 @@
         /// @warning The default constructor sets the iterator
         /// to an undefined value.
-        InEdgeIt() {}
-        /// Initialize the iterator to be invalid
-        InEdgeIt(Invalid) {}
-        InEdgeIt(const StaticGraphSkeleton &, Node) {}    
+        InEdgeIt() { }
+        /// Copy constructor.
+        InEdgeIt(const InEdgeIt&) { }
+        /// Initialize the iterator to be invalid.
+        InEdgeIt(Invalid) { }
+        /// .
+        InEdgeIt(const StaticGraphSkeleton&, const Node&) { }
+        /// .
+        InEdgeIt(const StaticGraphSkeleton&, const Edge&) { }
+        /// Assign the iterator to the next inedge of the corresponding node.
+        InEdgeIt& operator++() { return *this; }
       };
       //  class SymEdgeIt : public Edge {};
@@ -167 +191 @@
       /// 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:
+      /// 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++;
+      /// int count=0;
+      /// for(Graph::EdgeIt e(g); g.valid(e); ++e) ++count;
       /// \endcode
       class EdgeIt : public Edge {
@@ -176 +200 @@
         /// @warning The default constructor sets the iterator
         /// to an undefined value.
-        EdgeIt() {}
-        /// Initialize the iterator to be invalid
-        EdgeIt(Invalid) {}
-        EdgeIt(const StaticGraphSkeleton &) {}
+        EdgeIt() { }
+        /// Copy constructor.
+        EdgeIt(const EdgeIt&) { }
+        /// Initialize the iterator to be invalid.
+        EdgeIt(Invalid) { }
+        /// .
+        EdgeIt(const StaticGraphSkeleton&) { }
+        /// .
+        EdgeIt(const StaticGraphSkeleton&, const Edge&) { } 
+        EdgeIt& operator++() { return *this; }
       };
 
@@ -187 +217 @@
       /// \return the first node.
       ///
-      NodeIt &first(NodeIt &i) const { return i;}
+      NodeIt& first(NodeIt& i) const { return i; }
 
       /// The first incoming edge.
-      InEdgeIt &first(InEdgeIt &i, Node) const { return i;}
+      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;}
+      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;}
+      EdgeIt& first(EdgeIt& i) const { return i; }
 
       //     Node getNext(Node) const {}
@@ -204 +234 @@
 
       /// Go to the next node.
-      NodeIt &next(NodeIt &i) const { return i;}
+      NodeIt& next(NodeIt& i) const { return i; }
       /// Go to the next incoming edge.
-      InEdgeIt &next(InEdgeIt &i) const { return i;}
+      InEdgeIt& next(InEdgeIt& i) const { return i; }
       /// Go to the next outgoing edge.
-      OutEdgeIt &next(OutEdgeIt &i) const { return i;}
-      //SymEdgeIt &next(SymEdgeIt &) const {}
+      OutEdgeIt& next(OutEdgeIt& i) const { return i; }
+      //SymEdgeIt& next(SymEdgeIt&) const { }
       /// Go to the next edge.
-      EdgeIt &next(EdgeIt &i) const { return i;}
+      EdgeIt& next(EdgeIt& i) const { return i; }
 
       ///Gives back the head node of an edge.
@@ -230 +260 @@
       ///\todo Maybe, it would be better if iterator converted to
       ///bool directly, as Jacint prefers.
-      bool valid(const Node&) const { return true;}
+      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;}
+      bool valid(const Edge&) const { return true; }
 
       ///Gives back the \e id of a node.
@@ -241 +271 @@
       ///\warning Not all graph structures provide this feature.
       ///
-      int id(const Node&) const { return 0;}
+      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;}
+      int id(const Edge&) const { return 0; }
 
       /// Resets the graph.
@@ -252 +282 @@
       /// 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;}
-
+      void clear() { }
+
+      int nodeNum() const { return 0; }
+      int edgeNum() const { return 0; }
 
 
@@ -271 +300 @@
       public:
 
-        class ReferenceMap<Node,T>;
-
-        NodeMap(const StaticGraphSkeleton &) {}
-        NodeMap(const StaticGraphSkeleton &, T) {}
+        NodeMap(const StaticGraphSkeleton&) { }
+        NodeMap(const StaticGraphSkeleton&, T) { }
 
         ///Copy constructor
-        template<typename TT> NodeMap(const NodeMap<TT> &) {}
+        template<typename TT> NodeMap(const NodeMap<TT>&) { }
         ///Assignment operator
-        template<typename TT> NodeMap &operator=(const NodeMap<TT> &)
-        {return *this;}
+        template<typename TT> NodeMap& operator=(const NodeMap<TT>&)
+        { return *this; }
       };
 
@@ -296 +323 @@
         typedef Edge KeyType;
 
-        EdgeMap(const StaticGraphSkeleton &) {}
-        EdgeMap(const StaticGraphSkeleton &, T ) {}
+        EdgeMap(const StaticGraphSkeleton&) { }
+        EdgeMap(const StaticGraphSkeleton&, T) { }
     
         ///Copy constructor
-        template<typename TT> EdgeMap(const EdgeMap<TT> &) {}
+        template<typename TT> EdgeMap(const EdgeMap<TT>&) { }
         ///Assignment operator
-        template<typename TT> EdgeMap &operator=(const EdgeMap<TT> &)
-        {return *this;}
+        template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&)
+        { return *this; }
       };
     };
@@ -318 +345 @@
     public:
       /// Defalult constructor.
-      GraphSkeleton() {}
+      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) {}
+      GraphSkeleton(const GraphSkeleton&) { }
 
       ///Add a new node to the graph.
@@ -329 +356 @@
       /// \return the new node.
       ///
-      Node addNode() { return INVALID;}
+      Node addNode() { return INVALID; }
       ///Add a new edge to the graph.
 
@@ -335 +362 @@
       ///and head node \c head.
       ///\return the new edge.
-      Edge addEdge(Node, Node) { return INVALID;}
+      Edge addEdge(Node, Node) { return INVALID; }
     
       /// Resets the graph.
@@ -342 +369 @@
       /// It also frees the memory allocated to store them.
       /// \todo It might belong to \c EraseableGraphSkeleton.
-      void clear() {}
+      void clear() { }
     };
 
@@ -353 +380 @@
     public:
       /// Deletes a node.
-      void erase(Node n) {}
+      void erase(Node n) { }
       /// Deletes an edge.
-      void erase(Edge e) {}
+      void erase(Edge e) { }
 
       /// Defalult constructor.
-      EraseableGraphSkeleton() {}
+      EraseableGraphSkeleton() { }
       ///Copy consructor.
-      EraseableGraphSkeleton(const GraphSkeleton &G) {}
+      EraseableGraphSkeleton(const GraphSkeleton&) { }
     };
 

src/hugo/smart_graph.h

@@ -122 +122 @@
     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; }
@@ -137 +131 @@
       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; }
-
-    static bool valid(Edge e) { return e.n!=-1; }
-    static bool valid(Node n) { return n.n!=-1; }
-    
-    ///\deprecated Use
-    ///\code
-    ///  e=INVALID;
-    ///\endcode
-    ///instead.
-    static void setInvalid(Edge &e) { e.n=-1; }
-    ///\deprecated Use
-    ///\code
-    ///  e=INVALID;
-    ///\endcode
-    ///instead.
-    static 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; }
-
     static int id(Node v) { return v.n; }
     static int id(Edge e) { return e.n; }
@@ -198 +157 @@
     }
 
+    /// Finds an edge between two nodes.
+
+    /// Finds an edge from node \c u to node \c v.
+    ///
+    /// If \c prev is \ref INVALID (this is the default value), then
+    /// It finds the first edge from \c u to \c v. Otherwise it looks for
+    /// the next edge from \c u to \c v after \c prev.
+    /// \return The found edge or INVALID if there is no such an edge.
+    Edge findEdge(Node u,Node v, Edge prev = INVALID) 
+    {
+      int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out;
+      while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out;
+      prev.n=e;
+      return prev;
+    }
+    
     void clear() {nodes.clear();edges.clear();}
 
@@ -219 +194 @@
       bool operator!=(const Node i) const {return n!=i.n;}
       bool operator<(const Node i) const {return n<i.n;}
+      //      ///Validity check
+      //      operator bool() { return n!=-1; }
     };
     
     class NodeIt : public Node {
+      const SmartGraph *G;
       friend class SmartGraph;
     public:
       NodeIt() : Node() { }
+      NodeIt(const SmartGraph& _G,Node n) : Node(n), G(&_G) { }
       NodeIt(Invalid i) : Node(i) { }
-      NodeIt(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { }
-      ///\todo Undocumented conversion Node -\> NodeIt.
-      NodeIt(const SmartGraph& G, const Node &n) : Node(n) { }
+      NodeIt(const SmartGraph& _G) : Node(_G.nodes.size()?0:-1), G(&_G) { }
+      NodeIt &operator++() {
+        n=(n+2)%(G->nodes.size()+1)-1; 
+        return *this; 
+      }
+//       ///Validity check
+//       operator bool() { return Node::operator bool(); }      
     };
 
@@ -258 +241 @@
       ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
       int &idref() {return n;}
-      const int &idref() const {return n;}
-    };
+      const int &idref() const {return n;} 
+//       ///Validity check
+//       operator bool() { return n!=-1; }
+   };
     
     class EdgeIt : public Edge {
+      const SmartGraph *G;
       friend class SmartGraph;
     public:
-      EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { }
+      EdgeIt(const SmartGraph& _G) : Edge(_G.edges.size()-1), G(&_G) { }
+      EdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
       EdgeIt (Invalid i) : Edge(i) { }
       EdgeIt() : Edge() { }
@@ -270 +257 @@
       ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
       int &idref() {return n;}
+      EdgeIt &operator++() { --n; return *this; }
+//       ///Validity check
+//       operator bool() { return Edge::operator bool(); }      
     };
     
     class OutEdgeIt : public Edge {
+      const SmartGraph *G;
       friend class SmartGraph;
     public: 
       OutEdgeIt() : Edge() { }
+      OutEdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
       OutEdgeIt (Invalid i) : Edge(i) { }
 
-      OutEdgeIt(const SmartGraph& G,const Node v)
-        : Edge(G.nodes[v.n].first_out) {}
+      OutEdgeIt(const SmartGraph& _G,const Node v)
+        : Edge(_G.nodes[v.n].first_out), G(&_G) {}
+      OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; }
+//       ///Validity check
+//       operator bool() { return Edge::operator bool(); }      
     };
     
     class InEdgeIt : public Edge {
+      const SmartGraph *G;
       friend class SmartGraph;
     public: 
       InEdgeIt() : Edge() { }
+      InEdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
       InEdgeIt (Invalid i) : Edge(i) { }
-      InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
+      InEdgeIt(const SmartGraph& _G,Node v)
+        : Edge(_G.nodes[v.n].first_in), G(&_G) { }
+      InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
+//       ///Validity check
+//       operator bool() { return Edge::operator bool(); }      
     };
 

src/hugo/unionfind.h

@@ -6 +6 @@
 //!\file
 //!\brief Union-Find data structures.
+//!
+//!\bug unionfind_test.cc doesn't work with Intel compiler. It compiles but
+//!fails to run (Segmentation fault).