Changeset 1820:22099ef840d7 in lemon-0.x for lemon/bits/graph_extender.h

Timestamp:

11/21/05 18:48:00 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

Undir Bipartite Graph/Full? and Smart/ without concept, doc and concept
checking

File:

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

lemon/bits/graph_extender.h

@@ -20 +20 @@
 
 #include <lemon/invalid.h>
+#include <lemon/error.h>
 
 namespace lemon {
@@ -377 +378 @@
   };
 
+
+  template <typename _Base>
+  class UndirBipartiteGraphExtender : public _Base {
+  public:
+    typedef _Base Parent;
+    typedef UndirBipartiteGraphExtender Graph;
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge UndirEdge;
+
+    using Parent::first;
+    using Parent::next;
+
+    using Parent::id;
+
+    Node source(const UndirEdge& edge) const {
+      return upperNode(edge);
+    }
+    Node target(const UndirEdge& edge) const {
+      return lowerNode(edge);
+    }
+
+    void firstInc(UndirEdge& edge, bool& direction, const Node& node) const {
+      if (Parent::upper(node)) {
+        Parent::firstDown(edge, node);
+        direction = true;
+      } else {
+        Parent::firstUp(edge, node);
+        direction = static_cast<UndirEdge&>(edge) == INVALID;
+      }
+    }
+    void nextInc(UndirEdge& edge, bool& direction) const {
+      if (direction) {
+        Parent::nextDown(edge);
+      } else {
+        Parent::nextUp(edge);
+        if (edge == INVALID) direction = true;
+      }
+    }
+
+    int maxUndirEdgeId() const {
+      return Parent::maxEdgeId();
+    }
+
+    UndirEdge undirEdgeFromId(int id) const {
+      return Parent::edgeFromId(id);
+    }
+
+    class Edge : public UndirEdge {
+      friend class UndirBipartiteGraphExtender;
+    protected:
+      bool forward;
+
+      Edge(const UndirEdge& edge, bool _forward)
+        : UndirEdge(edge), forward(_forward) {}
+
+    public:
+      Edge() {}
+      Edge (Invalid) : UndirEdge(INVALID), forward(true) {}
+      bool operator==(const Edge& i) const {
+        return UndirEdge::operator==(i) && forward == i.forward;
+      }
+      bool operator!=(const Edge& i) const {
+        return UndirEdge::operator!=(i) || forward != i.forward;
+      }
+      bool operator<(const Edge& i) const {
+        return UndirEdge::operator<(i) || 
+          (!(i.forward<forward) && UndirEdge(*this)<UndirEdge(i));
+      }
+    };
+
+    void first(Edge& edge) const {
+      Parent::first(static_cast<UndirEdge&>(edge));
+      edge.forward = true;
+    }
+
+    void next(Edge& edge) const {
+      if (!edge.forward) {
+        Parent::next(static_cast<UndirEdge&>(edge));
+      }
+      edge.forward = !edge.forward;
+    }
+
+    void firstOut(Edge& edge, const Node& node) const {
+      if (Parent::upper(node)) {
+        Parent::firstDown(edge, node);
+        edge.forward = true;
+      } else {
+        Parent::firstUp(edge, node);
+        edge.forward = static_cast<UndirEdge&>(edge) == INVALID;
+      }
+    }
+    void nextOut(Edge& edge) const {
+      if (edge.forward) {
+        Parent::nextDown(edge);
+      } else {
+        Parent::nextUp(edge);
+        if (edge == INVALID) {
+          edge.forward = true;
+        }       
+      }
+    }
+
+    void firstIn(Edge& edge, const Node& node) const {
+      if (Parent::lower(node)) {
+        Parent::firstUp(edge, node);
+        edge.forward = true;    
+      } else {
+        Parent::firstDown(edge, node);
+        edge.forward = static_cast<UndirEdge&>(edge) == INVALID;
+      }
+    }
+    void nextIn(Edge& edge) const {
+      if (edge.forward) {
+        Parent::nextUp(edge);
+      } else {
+        Parent::nextDown(edge);
+        if (edge == INVALID) {
+          edge.forward = true;
+        }       
+      }
+    }
+
+    Node source(const Edge& edge) const {
+      return edge.forward ? Parent::upperNode(edge) : Parent::lowerNode(edge);
+    }
+    Node target(const Edge& edge) const {
+      return edge.forward ? Parent::lowerNode(edge) : Parent::upperNode(edge);
+    }
+
+    bool direction(const Edge& edge) const {
+      return edge.forward;
+    }
+
+    Edge direct(const UndirEdge& edge, const Node& node) const {
+      return Edge(edge, node == Parent::source(edge));
+    }
+
+    Edge direct(const UndirEdge& edge, bool direction) const {
+      return Edge(edge, direction);
+    }
+
+    Node oppositeNode(const UndirEdge& edge, const Node& node) const {
+      return source(edge) == node ? 
+        target(edge) : source(edge);
+    }
+
+    Edge oppositeEdge(const Edge& edge) const {
+      return Edge(edge, !edge.forward);
+    }
+
+    int id(const Edge& edge) const {
+      return (Parent::id(edge) << 1) + (edge.forward ? 0 : 1);
+    }
+    Edge edgeFromId(int id) const {
+      return Edge(Parent::fromId(id >> 1, UndirEdge()), (id & 1) == 0);
+    }
+    int maxEdgeId() const {
+      return (Parent::maxId(UndirEdge()) << 1) + 1;
+    }
+
+    class UpperNode : public Node {
+      friend class UndirBipartiteGraphExtender;
+    public:
+      UpperNode() {}
+      UpperNode(const Node& node) : Node(node) {
+        LEMON_ASSERT(Parent::upper(node) || node == INVALID, 
+                     typename Parent::NodeSetError());
+      }
+      UpperNode(Invalid) : Node(INVALID) {}
+    };
+
+    void first(UpperNode& node) const {
+      Parent::firstUpper(static_cast<Node&>(node));
+    }
+    void next(UpperNode& node) const {
+      Parent::nextUpper(static_cast<Node&>(node));
+    }
+
+    int id(const UpperNode& node) const {
+      return Parent::upperId(node);
+    }
+
+    class LowerNode : public Node {
+      friend class UndirBipartiteGraphExtender;
+    public:
+      LowerNode() {}
+      LowerNode(const Node& node) : Node(node) {
+        LEMON_ASSERT(Parent::lower(node) || node == INVALID,
+                     typename Parent::NodeSetError());
+      }
+      LowerNode(Invalid) : Node(INVALID) {}
+    };
+
+    void first(LowerNode& node) const {
+      Parent::firstLower(static_cast<Node&>(node));
+    }
+    void next(LowerNode& node) const {
+      Parent::nextLower(static_cast<Node&>(node));
+    }
+  
+    int id(const LowerNode& node) const {
+      return Parent::upperId(node);
+    }
+
+
+
+    int maxId(Node) const {
+      return Parent::maxNodeId();
+    }
+    int maxId(LowerNode) const {
+      return Parent::maxLowerId();
+    }
+    int maxId(UpperNode) const {
+      return Parent::maxUpperId();
+    }
+    int maxId(Edge) const {
+      return maxEdgeId();
+    }
+    int maxId(UndirEdge) const {
+      return maxUndirEdgeId();
+    }
+
+
+    Node fromId(int id, Node) const {
+      return Parent::nodeFromId(id);
+    }
+    UpperNode fromId(int id, UpperNode) const {
+      return Parent::fromUpperId(id);
+    }
+    LowerNode fromId(int id, LowerNode) const {
+      return Parent::fromLowerId(id);
+    }
+    Edge fromId(int id, Edge) const {
+      return edgeFromId(id);
+    }
+    UndirEdge fromId(int id, UndirEdge) const {
+      return undirEdgeFromId(id);
+    }
+
+  };
+
 }