Changeset 1909:2d806130e700 in lemon-0.x for lemon/bits/graph_extender.h

Timestamp:

01/26/06 16:42:13 (18 years ago)

Author:

Mihaly Barasz

Branch:

default

Phase:

public

Convert:

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

Message:

Undir -> U transition

File:

• lemon/bits/graph_extender.h (modified) (35 diffs)

lemon/bits/graph_extender.h

@@ -62 +62 @@
 
   template <typename _Base>
-  class UndirGraphExtender : public _Base {
+  class UGraphExtender : public _Base {
     typedef _Base Parent;
-    typedef UndirGraphExtender Graph;
+    typedef UGraphExtender Graph;
 
   public:
 
-    typedef typename Parent::Edge UndirEdge;
+    typedef typename Parent::Edge UEdge;
     typedef typename Parent::Node Node;
 
-    class Edge : public UndirEdge {
-      friend class UndirGraphExtender;
+    class Edge : public UEdge {
+      friend class UGraphExtender;
 
     protected:
@@ -79 +79 @@
       bool forward;
 
-      Edge(const UndirEdge &ue, bool _forward) :
-        UndirEdge(ue), forward(_forward) {}
+      Edge(const UEdge &ue, bool _forward) :
+        UEdge(ue), forward(_forward) {}
 
     public:
@@ -86 +86 @@
 
       /// Invalid edge constructor
-      Edge(Invalid i) : UndirEdge(i), forward(true) {}
+      Edge(Invalid i) : UEdge(i), forward(true) {}
 
       bool operator==(const Edge &that) const {
-        return forward==that.forward && UndirEdge(*this)==UndirEdge(that);
+        return forward==that.forward && UEdge(*this)==UEdge(that);
       }
       bool operator!=(const Edge &that) const {
-        return forward!=that.forward || UndirEdge(*this)!=UndirEdge(that);
+        return forward!=that.forward || UEdge(*this)!=UEdge(that);
       }
       bool operator<(const Edge &that) const {
         return forward<that.forward ||
-          (!(that.forward<forward) && UndirEdge(*this)<UndirEdge(that));
+          (!(that.forward<forward) && UEdge(*this)<UEdge(that));
       }
     };
@@ -127 +127 @@
     }
 
-    Node oppositeNode(const Node &n, const UndirEdge &e) const {
+    Node oppositeNode(const Node &n, const UEdge &e) const {
       if( n == Parent::source(e))
         return Parent::target(e);
@@ -138 +138 @@
     /// \brief Directed edge from an undirected edge and a source node.
     ///
-    /// Returns a (directed) Edge corresponding to the specified UndirEdge
+    /// Returns a (directed) Edge corresponding to the specified UEdge
     /// and source Node.
     ///
-    Edge direct(const UndirEdge &ue, const Node &s) const {
+    Edge direct(const UEdge &ue, const Node &s) const {
       return Edge(ue, s == source(ue));
     }
@@ -147 +147 @@
     /// \brief Directed edge from an undirected edge.
     ///
-    /// Returns a directed edge corresponding to the specified UndirEdge.
+    /// Returns a directed edge corresponding to the specified UEdge.
     /// If the given bool is true the given undirected edge and the
     /// returned edge have the same source node.
-    Edge direct(const UndirEdge &ue, bool d) const {
+    Edge direct(const UEdge &ue, bool d) const {
       return Edge(ue, d);
     }
@@ -183 +183 @@
     void firstOut(Edge &e, const Node &n) const {
       Parent::firstIn(e,n);
-      if( UndirEdge(e) != INVALID ) {
+      if( UEdge(e) != INVALID ) {
         e.forward = false;
       }
@@ -195 +195 @@
         Node n = Parent::target(e);
         Parent::nextIn(e);
-        if( UndirEdge(e) == INVALID ) {
+        if( UEdge(e) == INVALID ) {
           Parent::firstOut(e, n);
           e.forward = true;
@@ -207 +207 @@
     void firstIn(Edge &e, const Node &n) const {
       Parent::firstOut(e,n);
-      if( UndirEdge(e) != INVALID ) {
+      if( UEdge(e) != INVALID ) {
         e.forward = false;
       }
@@ -219 +219 @@
         Node n = Parent::source(e);
         Parent::nextOut(e);
-        if( UndirEdge(e) == INVALID ) {
+        if( UEdge(e) == INVALID ) {
           Parent::firstIn(e, n);
           e.forward = true;
@@ -229 +229 @@
     }
 
-    void firstInc(UndirEdge &e, const Node &n) const {
+    void firstInc(UEdge &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 {
+    void nextInc(UEdge &e, const Node &n) const {
       if (Parent::source(e) == n) {
         Parent::nextOut(e);
@@ -244 +244 @@
     }
 
-    void firstInc(UndirEdge &e, bool &d, const Node &n) const {
+    void firstInc(UEdge &e, bool &d, const Node &n) const {
       d = true;
       Parent::firstOut(e, n);
@@ -251 +251 @@
       Parent::firstIn(e, n);
     }
-    void nextInc(UndirEdge &e, bool &d) const {
+    void nextInc(UEdge &e, bool &d) const {
       if (d) {
         Node s = Parent::source(e);
@@ -276 +276 @@
     }
 
-    int id(const UndirEdge &e) const {
+    int id(const UEdge &e) const {
       return Parent::id(e);
     }
@@ -292 +292 @@
     }
 
-    int maxUndirEdgeId() const {
+    int maxUEdgeId() const {
       return Parent::maxEdgeId();
     }
@@ -303 +303 @@
       return maxEdgeId();
     }
-    int maxId(UndirEdge) const {
-      return maxUndirEdgeId();
+    int maxId(UEdge) const {
+      return maxUEdgeId();
     }
 
@@ -311 +311 @@
     }
 
-    int undirEdgeNum() const {
+    int uEdgeNum() const {
       return Parent::edgeNum();
     }
@@ -323 +323 @@
     }
 
-    UndirEdge undirEdgeFromId(int id) const {
+    UEdge uEdgeFromId(int id) const {
       return Parent::edgeFromId(id >> 1);
     }
@@ -335 +335 @@
     }
 
-    UndirEdge fromId(int id, UndirEdge) const {
-      return undirEdgeFromId(id);
+    UEdge fromId(int id, UEdge) const {
+      return uEdgeFromId(id);
     }
 
@@ -342 +342 @@
     Edge findEdge(Node source, Node target, Edge prev) const {
       if (prev == INVALID) {
-        UndirEdge edge = Parent::findEdge(source, target);
+        UEdge 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);
+        UEdge 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);
+        UEdge edge = Parent::findEdge(target, source, prev);
         if (edge != INVALID) return direct(edge, false);              
       }
@@ -358 +358 @@
     }
 
-    UndirEdge findUndirEdge(Node source, Node target, UndirEdge prev) const {
+    UEdge findUEdge(Node source, Node target, UEdge prev) const {
       if (prev == INVALID) {
-        UndirEdge edge = Parent::findEdge(source, target);
+        UEdge 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);
+        UEdge 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);
+        UEdge edge = Parent::findEdge(target, source, prev);
         if (edge != INVALID) return edge;             
       }
@@ -380 +380 @@
 
   template <typename _Base>
-  class UndirBipartiteGraphExtender : public _Base {
+  class UBipartiteGraphExtender : public _Base {
   public:
     typedef _Base Parent;
-    typedef UndirBipartiteGraphExtender Graph;
+    typedef UBipartiteGraphExtender Graph;
 
     typedef typename Parent::Node Node;
-    typedef typename Parent::Edge UndirEdge;
+    typedef typename Parent::Edge UEdge;
 
     using Parent::first;
@@ -393 +393 @@
     using Parent::id;
 
-    Node source(const UndirEdge& edge) const {
+    Node source(const UEdge& edge) const {
       return upperNode(edge);
     }
-    Node target(const UndirEdge& edge) const {
+    Node target(const UEdge& edge) const {
       return lowerNode(edge);
     }
 
-    void firstInc(UndirEdge& edge, bool& direction, const Node& node) const {
+    void firstInc(UEdge& edge, bool& direction, const Node& node) const {
       if (Parent::upper(node)) {
         Parent::firstDown(edge, node);
@@ -406 +406 @@
       } else {
         Parent::firstUp(edge, node);
-        direction = static_cast<UndirEdge&>(edge) == INVALID;
-      }
-    }
-    void nextInc(UndirEdge& edge, bool& direction) const {
+        direction = static_cast<UEdge&>(edge) == INVALID;
+      }
+    }
+    void nextInc(UEdge& edge, bool& direction) const {
       if (direction) {
         Parent::nextDown(edge);
@@ -418 +418 @@
     }
 
-    int maxUndirEdgeId() const {
+    int maxUEdgeId() const {
       return Parent::maxEdgeId();
     }
 
-    UndirEdge undirEdgeFromId(int id) const {
+    UEdge uEdgeFromId(int id) const {
       return Parent::edgeFromId(id);
     }
 
-    class Edge : public UndirEdge {
-      friend class UndirBipartiteGraphExtender;
+    class Edge : public UEdge {
+      friend class UBipartiteGraphExtender;
     protected:
       bool forward;
 
-      Edge(const UndirEdge& edge, bool _forward)
-        : UndirEdge(edge), forward(_forward) {}
+      Edge(const UEdge& edge, bool _forward)
+        : UEdge(edge), forward(_forward) {}
 
     public:
       Edge() {}
-      Edge (Invalid) : UndirEdge(INVALID), forward(true) {}
+      Edge (Invalid) : UEdge(INVALID), forward(true) {}
       bool operator==(const Edge& i) const {
-        return UndirEdge::operator==(i) && forward == i.forward;
+        return UEdge::operator==(i) && forward == i.forward;
       }
       bool operator!=(const Edge& i) const {
-        return UndirEdge::operator!=(i) || forward != i.forward;
+        return UEdge::operator!=(i) || forward != i.forward;
       }
       bool operator<(const Edge& i) const {
-        return UndirEdge::operator<(i) || 
-          (!(i.forward<forward) && UndirEdge(*this)<UndirEdge(i));
+        return UEdge::operator<(i) || 
+          (!(i.forward<forward) && UEdge(*this)<UEdge(i));
       }
     };
 
     void first(Edge& edge) const {
-      Parent::first(static_cast<UndirEdge&>(edge));
+      Parent::first(static_cast<UEdge&>(edge));
       edge.forward = true;
     }
@@ -456 +456 @@
     void next(Edge& edge) const {
       if (!edge.forward) {
-        Parent::next(static_cast<UndirEdge&>(edge));
+        Parent::next(static_cast<UEdge&>(edge));
       }
       edge.forward = !edge.forward;
@@ -467 +467 @@
       } else {
         Parent::firstUp(edge, node);
-        edge.forward = static_cast<UndirEdge&>(edge) == INVALID;
+        edge.forward = static_cast<UEdge&>(edge) == INVALID;
       }
     }
@@ -475 +475 @@
       } else {
         Parent::nextUp(edge);
-        edge.forward = static_cast<UndirEdge&>(edge) == INVALID;
+        edge.forward = static_cast<UEdge&>(edge) == INVALID;
       }
     }
@@ -485 +485 @@
       } else {
         Parent::firstDown(edge, node);
-        edge.forward = static_cast<UndirEdge&>(edge) == INVALID;
+        edge.forward = static_cast<UEdge&>(edge) == INVALID;
       }
     }
@@ -493 +493 @@
       } else {
         Parent::nextDown(edge);
-        edge.forward = static_cast<UndirEdge&>(edge) == INVALID;
+        edge.forward = static_cast<UEdge&>(edge) == INVALID;
       }
     }
@@ -508 +508 @@
     }
 
-    Edge direct(const UndirEdge& edge, const Node& node) const {
+    Edge direct(const UEdge& edge, const Node& node) const {
       return Edge(edge, node == Parent::source(edge));
     }
 
-    Edge direct(const UndirEdge& edge, bool direction) const {
+    Edge direct(const UEdge& edge, bool direction) const {
       return Edge(edge, direction);
     }
 
-    Node oppositeNode(const UndirEdge& edge, const Node& node) const {
+    Node oppositeNode(const UEdge& edge, const Node& node) const {
       return source(edge) == node ? 
         target(edge) : source(edge);
@@ -529 +529 @@
     }
     Edge edgeFromId(int id) const {
-      return Edge(Parent::fromId(id >> 1, UndirEdge()), (id & 1) == 0);
+      return Edge(Parent::fromId(id >> 1, UEdge()), (id & 1) == 0);
     }
     int maxEdgeId() const {
-      return (Parent::maxId(UndirEdge()) << 1) + 1;
+      return (Parent::maxId(UEdge()) << 1) + 1;
     }
 
     class UpperNode : public Node {
-      friend class UndirBipartiteGraphExtender;
+      friend class UBipartiteGraphExtender;
     public:
       UpperNode() {}
@@ -558 +558 @@
 
     class LowerNode : public Node {
-      friend class UndirBipartiteGraphExtender;
+      friend class UBipartiteGraphExtender;
     public:
       LowerNode() {}
@@ -593 +593 @@
       return maxEdgeId();
     }
-    int maxId(UndirEdge) const {
-      return maxUndirEdgeId();
+    int maxId(UEdge) const {
+      return maxUEdgeId();
     }
 
@@ -610 +610 @@
       return edgeFromId(id);
     }
-    UndirEdge fromId(int id, UndirEdge) const {
-      return undirEdgeFromId(id);
+    UEdge fromId(int id, UEdge) const {
+      return uEdgeFromId(id);
     }