Changeset 70:851ca9a60e90 in lemon-0.x for src

Timestamp:

02/10/04 14:29:15 (20 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

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

Message:

.

Location:

src

Files:

• include/graph.h (modified) (29 diffs)
• work/alpar/gwrapper.h (modified) (1 diff)

src/include/graph.h

@@ -19 +19 @@
     typedef N NodeType;
     
-    class EdgePoint
+    class EdgeIt
     {
     public:
       NEGRO::EdgePoint e;
-      bool isValid() { return e; }
-    };
-    
-    class InEdgePoint : public EdgePoint {};
-    class OutEdgePoint : public EdgePoint {};
-    class BiEdgePoint : public EdgePoint {};
-    class SymEdgePoint : public EdgePoint {};
-    
-    typedef int NodePoint;
+      bool valid() { return e; }
+    };
+    
+    class InEdgeIt : public EdgeIt {};
+    class OutEdgeIt : public EdgeIt {};
+    class BiEdgeIt : public EdgeIt {};
+    class SymEdgeIt : public EdgeIt {};
+    
+    typedef int NodeIt;
+    
+    typedef NodeIt EachNodeIt;
     
     class NodeIterator;
@@ -50 +52 @@
     friend class BiEdgeIterator;
     friend class SymEdgeIterator;
-    friend class AllEdgeIterator;
+    friend class EachEdgeIterator;
     
     class NodeIterator
@@ -63 +65 @@
       NodeIterator(const NodeIterator &i) {G=i.G;n=i.n;}
       
-      NodeIterator &GoNext() { n=G->NextNode(n); return *this;}
-      NodeIterator Next() const { return NodeIterator(*this).GoNext();}
-      NodeIterator &operator++() { return GoNext();} 
+      NodeIterator &goNext() { n=G->NextNode(n); return *this;}
+      NodeIterator next() const { return NodeIterator(*this).goNext();}
+      NodeIterator &operator++() { return goNext();} 
       NodeIterator operator++(int)
-      {NodeIterator tmp(*this); GoNext(); return tmp;}
-      bool isValid() { return n!=INVALID; }
+      {NodeIterator tmp(*this); goNext(); return tmp;}
+      bool valid() { return n!=INVALID; }
       
       N &operator*() const { return G->Data(n); }
@@ -76 +78 @@
       bool operator!=(const NodeIterator &i) const {return n!=i.n;}
       
-      int Index() const { return n; } //If the nodes are indexable 
+      int index() const { return n; } //If the nodes are indexable 
       friend class Graph;
       friend class EdgeIterator;
@@ -83 +85 @@
       friend class BiEdgeIterator;
       friend class SymEdgeIterator;
-      friend class AllEdgeIterator;
+      friend class EachEdgeIterator;
       friend class FirstAnythingTypeNode;
 
@@ -97 +99 @@
       // Meg a From() es To() miatt!!!!!!!!!!
       
-      NEGRO::EdgePoint e;
+      NEGRO::EdgeIt e;
       
     public:
@@ -105 +107 @@
       // Lehet, hogy ez a ketto nem kell!!!
       
-      NodeIterator From() const {NodeIterator i;i.G=G;i.n=e->From();return i;}
-      NodeIterator To() const {NodeIterator i;i.G=G;i.n=e->To();return i;}
-      
-      bool isValid() {return e;}
+      NodeIterator tail() const {NodeIterator i;i.G=G;i.n=e->From();return i;}
+      NodeIterator head() const {NodeIterator i;i.G=G;i.n=e->To();return i;}
+      NodeIterator opposite(const NodeIterator &n) const
+      {return n==tail()?head():tail();}
+      
+      bool valid() {return e;}
       E &operator*() const { return G->Data(e); }
       E *operator->() const { return &G->Data(e); }
@@ -120 +124 @@
       bool operator!=(const EdgeIterator &i) const {return e!=i.e;}
        
-      int Index() const { return e.index.block*EDGE_BLOCK_SIZE+e.index.index; }
+      int Index() const {return e->index.block*EDGE_BLOCK_SIZE+e->index.index;}
       //If the edges are indexable 
 
@@ -128 +132 @@
       friend class BiEdgeIterator;
       friend class SymEdgeIterator;
-      friend class AllEdgeIterator;
+      friend class EachEdgeIterator;
     };
     
@@ -134 +138 @@
     {
     public:
-      BiEdgeIterator &GoNextIn()  { e=e->NextIn(); return *this;}
-      BiEdgeIterator &GoNextOut() { e=e->NextOut(); return *this;}
-      BiEdgeIterator NextIn() const  {return BiEdgeIterator(*this).GoNextIn();}
-      BiEdgeIterator NextOut() const {return BiEdgeIterator(*this).GoNextOut();}
+      BiEdgeIterator &goNextIn()  { e=e->NextIn(); return *this;}
+      BiEdgeIterator &goNextOut() { e=e->NextOut(); return *this;}
+      BiEdgeIterator nextIn() const  {return BiEdgeIterator(*this).goNextIn();}
+      BiEdgeIterator nextOut() const {return BiEdgeIterator(*this).goNextOut();}
       
       operator InEdgeIterator ()
@@ -153 +157 @@
     public:
       InEdgeIterator() {}
-      InEdgeIterator(const Graph<N,E> &Gr,const NodeIterator &n)
+      InEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n)
       { G=&Gr; e=Gr.OldGraph<N,E>::FirstIn(n.n);}
 
@@ -181 +185 @@
       { G=&Gr; e=Gr.OldGraph<N,E>::FirstOut(n.n);}
 
-      OutEdgeIterator &GoNext() { e=e->NextOut(); return *this;}
-      OutEdgeIterator Next() const {return OutEdgeIterator(*this).GoNext();}
-      OutEdgeIterator &operator++() { return GoNext();}
+      OutEdgeIterator &goNext() { e=e->NextOut(); return *this;}
+      OutEdgeIterator next() const {return OutEdgeIterator(*this).goNext();}
+      OutEdgeIterator &operator++() { return goNext();}
       OutEdgeIterator operator++(int)
-      {OutEdgeIterator tmp(*this); GoNext(); return tmp;}
-      
-      NodeIterator Anode() const {return From();}
-      NodeIterator Bnode() const {return To();}
+      {OutEdgeIterator tmp(*this); goNext(); return tmp;}
+      
+      NodeIterator aNode() const {return tail();}
+      NodeIterator bNode() const {return head();}
       
       operator const InEdgeIterator ()
@@ -205 +209 @@
     public:
       SymEdgeIterator() {}
-      SymEdgeIterator(const Graph<N,E> &Gr,const NodeIterator &nn)
-      { G=&Gr; n=nn; e=Gr.FirstSym(nn.n); }
-
-      SymEdgeIterator &GoNext() { e=e->NextEdge(n.n); return *this;}
-      SymEdgeIterator Next() const {return SymEdgeIterator(*this).GoNext();}
-      SymEdgeIterator &operator++() { return GoNext();}
+      SymEdgeIterator(Graph<N,E> &Gr,const NodeIterator &nn)
+      { G=&Gr; n=nn; e=Gr.OldGraph<N,E>::FirstEdge(nn.n); }
+
+      SymEdgeIterator &goNext() { e=G->NextEdge(n.n,e); return *this;}
+      SymEdgeIterator next() const {return SymEdgeIterator(*this).goNext();}
+      SymEdgeIterator &operator++() { return goNext();}
       SymEdgeIterator operator++(int)
-      {SymEdgeIterator tmp(*this); GoNext(); return tmp;}
-      
-      NodeIterator Anode() const {return n;}
-      NodeIterator Bnode() const {return n.n==From().n?To():From();}
+      {SymEdgeIterator tmp(*this); goNext(); return tmp;}
+      
+      NodeIterator aNode() const {return n;}
+      NodeIterator bNode() const {return n.n==tail().n?head():tail();}
       
       operator const InEdgeIterator ()
@@ -227 +231 @@
     };
     
-    class AllEdgeIterator : public EdgeIterator
+    class EachEdgeIterator : public EdgeIterator
     {
       NodeIterator n;  // Itt ketszer van a G
       
     public:
-      AllEdgeIterator() {}
-      AllEdgeIterator(Graph<N,E> &Gr) : n(Gr)
+      EachEdgeIterator() {}
+      EachEdgeIterator(Graph<N,E> &Gr) : n(Gr)
       {
-        e=n.isValid()?Gr.OldGraph<N,E>::FirstOut(n.n):NULL;
+        e=n.valid()?Gr.OldGraph<N,E>::FirstOut(n.n):NULL;
       }  
 
-      AllEdgeIterator &GoNext()
+      EachEdgeIterator &goNext()
       {
         e=e->NextOut();
-        if(!e && (++n).isValid()) e=G->OldGraph<N,E>::FirstOut(n.n);
+        if(!e && (++n).valid()) e=G->OldGraph<N,E>::FirstOut(n.n);
         return *this;
       }
-      AllEdgeIterator Next() const {return AllEdgeIterator(*this).GoNext();}
-      AllEdgeIterator &operator++() { return GoNext();}
-      AllEdgeIterator operator++(int)
-        {AllEdgeIterator tmp(*this); GoNext(); return tmp;}
-      
-      
-      NodeIterator Anode() const {return n;}
-      NodeIterator Bnode() const {return n.n==From().n?To():From();}
-      
+      EachEdgeIterator next() const {return EachEdgeIterator(*this).goNext();}
+      EachEdgeIterator &operator++() { return goNext();}
+      EachEdgeIterator operator++(int)
+        {EachEdgeIterator tmp(*this); goNext(); return tmp;}
+      
+      
+      NodeIterator aNode() const {return n;}
+      NodeIterator bNode() const {return n.n==tail().n?head():tail();}
+      
+      operator const EdgeIterator ()
+      {EdgeIterator i; i.G=G;i.e=e;return i;}
       operator const InEdgeIterator ()
       {InEdgeIterator i; i.G=G;i.e=e;return i;}
@@ -270 +276 @@
     typedef SymEdgeIterator DeletingSymEdgeIterator;
     
-    const NodeIterator FirstNode()
+    const NodeIterator firstNode()
     {
       NodeIterator i;
@@ -277 +283 @@
     }
     
-    void GetFirst(NodePoint &p)   { p=OldGraph<N,E>::FirstNode(); }
-    
-    void GetFirst(InEdgePoint &p,const NodePoint &n)
+    void getFirst(NodeIt &p)   { p=OldGraph<N,E>::FirstNode(); }
+    
+    void getFirst(InEdgeIt &p,const NodeIt &n)
     { p=OldGraph<N,E>::FirstIn(n); }
-    void GetFirst(OutEdgePoint &p,const NodePoint &n)
+    void getFirst(OutEdgeIt &p,const NodeIt &n)
     { p=OldGraph<N,E>::FirstOut(n); }
-    void GetFirst(SymEdgePoint &p,const NodePoint &n)
+    void getFirst(SymEdgeIt &p,const NodeIt &n)
     { p=OldGraph<N,E>::FirstEdge(n); }
-    void GetFirst(EdgePoint &p) //Vegigmegy mindenen
-    { p.e=NodeNum()?OldGraph<N,E>::FirstOut(OldGraph<N,E>::FirstNode()):NULL;}
-
-    void GetFirst(NodeIterator &i) { i.G=this;i.n=OldGraph<N,E>::FirstNode();}
-    
-    void GetFirst(InEdgeIterator &i,const NodeIterator &n)
+    void getFirst(EdgeIt &p) //Vegigmegy mindenen
+    { p.e=nodeNum()?OldGraph<N,E>::FirstOut(OldGraph<N,E>::FirstNode()):NULL;}
+
+    void getFirst(NodeIterator &i) { i.G=this;i.n=OldGraph<N,E>::FirstNode();}
+    
+    void getFirst(InEdgeIterator &i,const NodeIterator &n)
     { i.G=this;i.e=OldGraph<N,E>::FirstIn(n.n); }
-    void GetFirst(OutEdgeIterator &i,const NodeIterator &n)
+    void getFirst(OutEdgeIterator &i,const NodeIterator &n)
     { i.G=this;i.e=OldGraph<N,E>::FirstOut(n.n); }
-    void GetFirst(SymEdgeIterator &i,const NodeIterator &n)
-    { i.G=this;i.e=OldGraph<N,E>::FirstSym(n.n); }
-    void GetFirst(AllEdgeIterator &i) //Vegigmegy mindenen
+    void getFirst(SymEdgeIterator &i,const NodeIterator &n)
+    { i.G=this;i.e=OldGraph<N,E>::FirstEdge(n.n); }
+    void getFirst(EachEdgeIterator &i) //Vegigmegy mindenen
     {
       i.G=this;
-      GetFirst(i.n);
+      getFirst(i.n);
       i.e=OldGraph<N,E>::NodeNum()?OldGraph<N,E>::FirstOut(i.n.n):NULL;
     }  
@@ -306 +312 @@
     
     //Vagy beginnode()?
-    const DeletingEdgeIterator FirstOut(const NodeIterator &n)
+    const DeletingEdgeIterator firstOut(const NodeIterator &n)
     {
       EdgeIterator i;
@@ -312 +318 @@
       return i;
     }
-    const DeletingEdgeIterator FirstIn(const NodeIterator &n)
+    const DeletingEdgeIterator firstIn(const NodeIterator &n)
     {
       EdgeIterator i;
@@ -318 +324 @@
       return i;
     }
-    const DeletingSymEdgeIterator FirstSym(const NodeIterator &n)
+    const DeletingSymEdgeIterator firstSym(const NodeIterator &n)
     {
       EdgeIterator i;
@@ -342 +348 @@
       {SymEdgeIterator i; n.G->GetFirst(i,n);return i;}
   
-      operator const InEdgePoint () const
-      {InEdgePoint i; n.G->GetFirst(i,n);return i;}
-      operator const OutEdgePoint () const
-      {OutEdgePoint i; n.G->GetFirst(i,n);return i;}
-      operator const SymEdgePoint () const
-      {SymEdgePoint i; n.G->GetFirst(i,n);return i;}
+      operator const InEdgeIt () const
+      {InEdgeIt i; n.G->GetFirst(i,n);return i;}
+      operator const OutEdgeIt () const
+      {OutEdgeIt i; n.G->GetFirst(i,n);return i;}
+      operator const SymEdgeIt () const
+      {SymEdgeIt i; n.G->GetFirst(i,n);return i;}
     };
     
@@ -356 +362 @@
       FirstAnythingType(Graph<N,E> *gg) : G(gg) {}
 
-      operator const AllEdgeIterator () const
-      {AllEdgeIterator i; G->GetFirst(i);return i;}  
-      operator const EdgePoint () const
-      {EdgePoint i; G->GetFirst(i);return i;}
+      operator const EachEdgeIterator () const
+      {EachEdgeIterator i; G->GetFirst(i);return i;}  
+      operator const EdgeIt () const
+      {EdgeIt i; G->GetFirst(i);return i;}
       operator const NodeIterator () const
       {NodeIterator i; G->GetFirst(i);return i;}  
-      operator const NodePoint () const
-      {NodePoint i; G->GetFirst(i);return i;}
+      operator const NodeIt () const
+      {NodeIt i; G->GetFirst(i);return i;}
     } _FST;
     
     //    const NodeIterator First() {NodeIterator i;GetFirst(i); return i;}
-    FirstAnythingTypeNode First(NodeIterator &i)
+    FirstAnythingTypeNode first(NodeIterator &i)
     {FirstAnythingTypeNode t(i); return t;}
-    const FirstAnythingType &First() {return _FST;}
+    const FirstAnythingType &first() {return _FST;}
     
     // LastNode() vagy endnode() stb. Nem kell?
     
-    DeletingNodeIterator AddNode()
+    DeletingNodeIterator addNode()
     {
       DeletingNodeIterator i;
@@ -380 +386 @@
     }
     DeletingEdgeIterator
-    AddEdge(const NodeIterator from,const NodeIterator to)
+    addEdge(const NodeIterator from,const NodeIterator to)
     {
       DeletingEdgeIterator i;
@@ -389 +395 @@
     void Delete(DeletingEdgeIterator e) {e.G->OldGraph<N,E>::Delete(e.e);}
     
-    int NodeNum() { OldGraph<N,E>::NodeNum(); }
-    void Clean() { OldGraph<N,E>::Clean(); }
+    int nodeNum() { OldGraph<N,E>::NodeNum(); }
+    void clean() { OldGraph<N,E>::Clean(); }
 
     Graph() : _FST(this) {}
@@ -402 +408 @@
     public:
       typedef T value_type;
-      void Put(const NodeIterator i, const T &t) {map[i.Index()]=t;}
-      T Get(const NodeIterator i) const {return map[i.Index()];}
+      void put(const NodeIterator i, const T &t) {map[i.Index()]=t;}
+      T get(const NodeIterator i) const {return map[i.Index()];}
       T operator[](NodeIterator i) {return map[i.Index()];}
 
@@ -409 +415 @@
 
       NodeMap() {}
-      void SetG(Graph<N,E> &Gr) { G=&Gr; update();}      
+      void setG(Graph<N,E> &Gr) { G=&Gr; update();}      
     };
 
@@ -419 +425 @@
     public:
       typedef T value_type;
-      void Put(const NodeIterator i, const T &t) {map[i.Index()]=t;}
-      T &Get(const NodeIterator i) {return map[i.Index()];}
-      T &operator[](NodeIterator i) {return map[i.Index()];}
+      void put(const EdgeIterator i, const T &t) {map[i.Index()]=t;}
+      T get(const EdgeIterator i) const {return map[i.Index()];}
+      T &operator[](EdgeIterator i) {return map[i.Index()];}
       
       void update()
@@ -427 +433 @@
       
       EdgeMap() {}
-      void SetG(Graph<N,E> &Gr) 
+      void setG(Graph<N,E> &Gr) 
       { G=&Gr ;update();}
       
@@ -433 +439 @@
     
 
-    int MaxNode() { return OldGraph<N,E>::MaxNode();}
-    int MaxEdge() { return ::edge_block_num*EDGE_BLOCK_SIZE;}
-    
+    int maxNode() { return OldGraph<N,E>::MaxNode();}
+    int maxEdge() { return ::edge_block_num*EDGE_BLOCK_SIZE;}
+    
+  };
+  
+  template <class G> //G is a graph-type
+  class Path
+  {
+  public:
+    typedef G Graph;
+    typedef typename G::NodeIterator NodeIterator;
+    typedef typename G::EdgeIterator EdgeIterator;
+    typedef typename G::SymEdgeIterator SymEdgeIterator;
+    
+  private:
+    std::vector<EdgeIterator> path;
+    std::vector<bool> reversed;
+
+  public:
+    void setLength(int n) { path.resize(n);reversed.resize(n);}
+    int getLength() { return path.size(); }
+    EdgeIterator &operator[](int n) {return path[n];}
+    NodeIterator GetNode(int n) // What about path of length 1?
+    {
+      return n?
+        reversed[n-1]?path[n-1].tail():path[n-1].head():
+        reversed[0]?path[0].head():path[0].tail();
+    }
+    void setRevert(int n,bool r=true) {reversed[n]=r;}
+    void setEdge(int n,SymEdgeIterator i)
+    {
+      path[n]=i;
+      reversed[n] = i.head()==i.aNode();
+    }
+    void setEdge(int n,EdgeIterator i,bool r)
+    {
+      path[n]=i;
+      reversed[n] = r;
+    }
+
+    NodeIterator tail() { return getNode(0); }
+    NodeIterator head() { return getNode(getLength()); }
   };
   
@@ -444 +489 @@
        mcmn   
   */
-  
-}
+};
 
 #endif

src/work/alpar/gwrapper.h

@@ -84 +84 @@
   NodeIt tail(const EdgeIt &e);
   { return graph->head(e); }
+  
+  template<typename I> NodeIt aNode(const I e);
+  { return graph->aNode(e); }
+  template<typename I> NodeIt bNode(const I e);
+  { return graph->bNode(e); }
+  
+  template<typename I> bool valid(const I i);
+  { return graph->valid(i); }
+  
+  template<typename I> void setInvalid(const I &i);
+  { return graph->setInvalid(i); }
+  
+  NodeIt addNode(); { return graph->addNode(); }
+  EdgeIt addEdge(const NodeIt from,const NodeIt to);
+  { return graph->addEdge(to,from); }
+  
+  template<I> void delete(I i); { graph->delete(i); }
+  
+  void clean();  { graph->clean(); }
+  
+  template<class T> class NodeMap : public typename G::NodeMap<T>;
+  template<class T> class EdgeMap : public typename G::EdgeMap<T>;
+  
+  void SetG(G &g) {graph = &g;}
+  
+  RevGraphWrapper() {graph = NULL;}
+  RevGraphWrapper(G &g) {graph = &g;}
+};
+
+template<typename G>
+class SymGraphWrapper
+{
+  G *graph;
+  
+public:
+  typedef G BaseGraph;
+
+  typedef typename G::EdgeIt EdgeIt;
+  
+  typedef typename G::InEdgeIt SymEdgeIt;
+  typedef typename G::OutEdgeIt SymEdgeIt;
+  typedef typename G::SymEdgeIt SymEdgeIt;
+  typedef typename G::EachEdgeIt EachEdgeIt;
+
+  typedef typename G::NodeIt NodeIt;
+    
+  template<typename I> I &getFirst(I &i); { return graph->getFirst(i); }
+  template<typename I,typename P> I &getFirst(I &i,const P &p);
+  { return graph->getFirst(i,p); }
+  template<typename I> I next(const I i); { return graph->goNext(i); }
+  template<typename I> I &goNext(I &i); { return graph->goNext(i); }
+
+  NodeIt head(const EdgeIt &e);
+  { return graph->head(e); }
+  NodeIt tail(const EdgeIt &e);
+  { return graph->tail(e); }
+  
+  template<typename I> NodeIt aNode(const I e);
+  { return graph->aNode(e); }
+  template<typename I> NodeIt bNode(const I e);
+  { return graph->bNode(e); }
+  
+  template<typename I> bool valid(const I i);
+  { return graph->valid(i); }
+  
+  template<typename I> void setInvalid(const I &i);
+  { return graph->setInvalid(i); }
+  
+  NodeIt addNode(); { return graph->addNode(); }
+  EdgeIt addEdge(const NodeIt from,const NodeIt to);
+  { return graph->addEdge(to,from); }
+  
+  template<I> void delete(I i); { graph->delete(i); }
+  
+  void clean();  { graph->clean(); }
+  
+  template<class T> class NodeMap : public typename G::NodeMap<T>;
+  template<class T> class EdgeMap : public typename G::EdgeMap<T>;
+  
+  void SetG(G &g) {graph = &g;}
+  
+  RevGraphWrapper() {graph = NULL;}
+  RevGraphWrapper(G &g) {graph = &g;}
+};
+
+
+// FIXME: comparison should be made better!!!
+template<typename G, typename lomap, typename fmap, typename himap>
+class ResGraphWrapper
+{
+  G *graph;
+  
+public:
+  typedef G BaseGraph;
+
+  typedef typename G::EdgeIt EdgeIt;
+  
+  class InEdgeIt 
+  {
+  public:
+    G::NodeIt n;
+    G::InEdgeIt i;   
+    G::OutEdgeIt o;
+  }
+  class OutEdgeIt 
+  {
+  public:
+    G::NodeIt n;
+    G::InEdgeIt i;   
+    G::OutEdgeIt o;
+  }
+  typedef typename G::SymEdgeIt SymEdgeIt;
+  typedef typename G::EachEdgeIt EachEdgeIt;
+
+  typedef typename G::NodeIt NodeIt;
+    
+  NodeIt &getFirst(NodeIt &n); { return graph->getFirst(n); }
+
+  // EachEdge and SymEdge  is missing!!!!
+  // EdgeIt <-> In/OutEdgeIt conversion is missing!!!!
+
+  InEdgeIt &getFirst(InEdgeIt &e,const NodeIt &n)
+  {
+    e.n=n;
+    graph->getFirst(e.i,n);
+    while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
+      graph->goNext(e.i);
+    if(!graph->valid(e.i)) {
+      graph->getFirst(e.o,n);
+      while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
+        graph->goNext(e.o);
+    }
+    return e;
+  }
+  InEdgeIt &goNext(InEdgeIt &e)
+  {
+    if(graph->valid(e.i)) {
+      while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
+        graph->goNext(e.i);
+      if(graph->valid(e.i)) return e;
+      else graph->getFirst(e.o,e.n);
+    }
+    else {
+      while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
+        graph->goNext(e.o);
+      return e;
+    }
+  }
+  InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
+  bool valid(const InEdgeIt e) { return graph->valid(e.i)||graph->valid(e.o);}
+
+  OutEdgeIt &getFirst(OutEdgeIt &e,const NodeIt &n)
+  {
+    e.n=n;
+    graph->getFirst(e.o,n);
+    while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
+      graph->goNext(e.o);
+    if(!graph->valid(e.o)) {
+      graph->getFirst(e.i,n);
+      while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
+        graph->goNext(e.i);
+    }
+    return e;
+  }
+  OutEdgeIt &goNext(OutEdgeIt &e)
+  {
+    if(graph->valid(e.o)) {
+      while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
+        graph->goNext(e.o);
+      if(graph->valid(e.o)) return e;
+      else graph->getFirst(e.i,e.n);
+    }
+    else {
+      while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
+        graph->goNext(e.i);
+      return e;
+    }
+  }
+  OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
+  bool valid(const OutEdgeIt e) { return graph->valid(e.o)||graph->valid(e.i);}
+
+  template<typename I> I &goNext(I &i); { return graph->goNext(i); }
+  template<typename I> I next(const I i); { return graph->goNext(i); }
+
+  NodeIt head(const EdgeIt &e);
+  { return graph->head(e); }
+  NodeIt tail(const EdgeIt &e);
+  { return graph->tail(e); }
   
   template<typename I> NodeIt aNode(const I e);