Changeset 1704:467d7927a901 in lemon-0.x for lemon/bits/undir_graph_extender.h

Timestamp:

10/05/05 15:17:42 (19 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

findUndirEdge, ConUndirEdgeIt?
some modification in the undir graph extenders

File:

• lemon/bits/undir_graph_extender.h (modified) (8 diffs)

lemon/bits/undir_graph_extender.h

@@ -72 +72 @@
     }
 
-  protected:
-
-    template <typename E>
-    Node _dirSource(const E &e) const {
-      return e.forward ? Parent::source(e) : Parent::target(e);
-    }
-
-    template <typename E>
-    Node _dirTarget(const E &e) const {
-      return e.forward ? Parent::target(e) : Parent::source(e);
-    }
-
   public:
     /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
@@ -91 +79 @@
     /// Source of the given Edge.
     Node source(const Edge &e) const {
-      return _dirSource(e);
+      return e.forward ? Parent::source(e) : Parent::target(e);
     }
 
@@ -100 +88 @@
     /// Target of the given Edge.
     Node target(const Edge &e) const {
-      return _dirTarget(e);
+      return e.forward ? Parent::target(e) : Parent::source(e);
     }
 
@@ -155 +143 @@
     }
 
-    
-  protected:
-
-    template <typename E>
-    void _dirFirstOut(E &e, const Node &n) const {
+  public:
+
+    void firstOut(Edge &e, const Node &n) const {
       Parent::firstIn(e,n);
       if( UndirEdge(e) != INVALID ) {
@@ -169 +155 @@
       }
     }
-    template <typename E>
-    void _dirFirstIn(E &e, const Node &n) const {
-      Parent::firstOut(e,n);
-      if( UndirEdge(e) != INVALID ) {
-        e.forward = false;
-      }
-      else {
-        Parent::firstIn(e,n);
-        e.forward = true;
-      }
-    }
-
-    template <typename E>
-    void _dirNextOut(E &e) const {
+    void nextOut(Edge &e) const {
       if( ! e.forward ) {
         Node n = Parent::target(e);
@@ -195 +168 @@
       }
     }
-    template <typename E>
-    void _dirNextIn(E &e) const {
+
+    void firstIn(Edge &e, const Node &n) const {
+      Parent::firstOut(e,n);
+      if( UndirEdge(e) != INVALID ) {
+        e.forward = false;
+      }
+      else {
+        Parent::firstIn(e,n);
+        e.forward = true;
+      }
+    }
+    void nextIn(Edge &e) const {
       if( ! e.forward ) {
         Node n = Parent::source(e);
@@ -210 +193 @@
     }
 
-  public:
-
-    void firstOut(Edge &e, const Node &n) const {
-      _dirFirstOut(e, n);
-    }
-    void firstIn(Edge &e, const Node &n) const {
-      _dirFirstIn(e, n);
-    }
-
-    void nextOut(Edge &e) const {
-      _dirNextOut(e);
-    }
-    void nextIn(Edge &e) const {
-      _dirNextIn(e);
+    void firstInc(UndirEdge &e, const Node &n) const {
+      Parent::firstOut(e, n);
+      if (e != INVALID) return;
+      Parent::firstIn(e, n);
+    }
+    void nextInc(UndirEdge &e, const Node &n) const {
+      if (Parent::source(e) == n) {
+        Parent::nextOut(e);
+        if (e != INVALID) return;
+        Parent::firstIn(e, n);
+      } else {
+        Parent::nextIn(e);
+      }
+    }
+
+    void firstInc(UndirEdge &e, bool &d, const Node &n) const {
+      d = true;
+      Parent::firstOut(e, n);
+      if (e != INVALID) return;
+      d = false;
+      Parent::firstIn(e, n);
+    }
+    void nextInc(UndirEdge &e, bool &d) const {
+      if (d) {
+        Node s = Parent::source(e);
+        Parent::nextOut(e);
+        if (e != INVALID) return;
+        d = false;
+        Parent::firstIn(e, s);
+      } else {
+        Parent::nextIn(e);
+      }
     }
 
@@ -263 +264 @@
       return 2 * Parent::edgeNum();
     }
+
     int undirEdgeNum() const {
       return Parent::edgeNum();
     }
 
+    Edge findEdge(Node source, Node target, Edge prev) const {
+      if (prev == INVALID) {
+        UndirEdge edge = Parent::findEdge(source, target);
+        if (edge != INVALID) return direct(edge, true);
+        edge = Parent::findEdge(target, source);
+        if (edge != INVALID) return direct(edge, false);
+      } else if (direction(prev)) {
+        UndirEdge edge = Parent::findEdge(source, target, prev);
+        if (edge != INVALID) return direct(edge, true);
+        edge = Parent::findEdge(target, source);
+        if (edge != INVALID) return direct(edge, false);        
+      } else {
+        UndirEdge edge = Parent::findEdge(target, source, prev);
+        if (edge != INVALID) return direct(edge, false);              
+      }
+      return INVALID;
+    }
+
+    UndirEdge findUndirEdge(Node source, Node target, UndirEdge prev) const {
+      if (prev == INVALID) {
+        UndirEdge edge = Parent::findEdge(source, target);
+        if (edge != INVALID) return edge;
+        edge = Parent::findEdge(target, source);
+        if (edge != INVALID) return edge;
+      } else if (Parent::source(prev) == source) {
+        UndirEdge edge = Parent::findEdge(source, target, prev);
+        if (edge != INVALID) return edge;
+        edge = Parent::findEdge(target, source);
+        if (edge != INVALID) return edge;       
+      } else {
+        UndirEdge edge = Parent::findEdge(target, source, prev);
+        if (edge != INVALID) return edge;             
+      }
+      return INVALID;
+    }
+
   };