Changeset 1820:22099ef840d7 in lemon-0.x for lemon/smart_graph.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/smart_graph.h (modified) (2 diffs)

lemon/smart_graph.h

@@ -34 +34 @@
 
 #include <lemon/utility.h>
+#include <lemon/error.h>
 
 namespace lemon {
@@ -375 +376 @@
   };
 
+
+  class SmartUndirBipartiteGraphBase {
+  public:
+
+    class NodeSetError : public LogicError {
+      virtual const char* exceptionName() const { 
+        return "lemon::FullUndirBipartiteGraph::NodeSetError";
+      }
+    };
+
+  protected:
+
+    struct NodeT {
+      int first;
+      NodeT() {}
+      NodeT(int _first) : first(_first) {}
+    };
+
+    struct EdgeT {
+      int upper, next_down;
+      int lower, next_up;
+    };
+
+    std::vector<NodeT> upperNodes;
+    std::vector<NodeT> lowerNodes;
+
+    std::vector<EdgeT> edges;
+
+  public:
+  
+    class Node {
+      friend class SmartUndirBipartiteGraphBase;
+    protected:
+      int id;
+
+      Node(int _id) : id(_id) {}
+    public:
+      Node() {}
+      Node(Invalid) { id = -1; }
+      bool operator==(const Node i) const {return id==i.id;}
+      bool operator!=(const Node i) const {return id!=i.id;}
+      bool operator<(const Node i) const {return id<i.id;}
+    };
+
+    class Edge {
+      friend class SmartUndirBipartiteGraphBase;
+    protected:
+      int id;
+
+      Edge(int _id) { id = _id;}
+    public:
+      Edge() {}
+      Edge (Invalid) { id = -1; }
+      bool operator==(const Edge i) const {return id==i.id;}
+      bool operator!=(const Edge i) const {return id!=i.id;}
+      bool operator<(const Edge i) const {return id<i.id;}
+    };
+
+    void firstUpper(Node& node) const {
+      node.id = 2 * upperNodes.size() - 2;
+      if (node.id < 0) node.id = -1; 
+    }
+    void nextUpper(Node& node) const {
+      node.id -= 2;
+      if (node.id < 0) node.id = -1; 
+    }
+
+    void firstLower(Node& node) const {
+      node.id = 2 * lowerNodes.size() - 1;
+    }
+    void nextLower(Node& node) const {
+      node.id -= 2;
+    }
+
+    void first(Node& node) const {
+      if (upperNodes.size() > 0) {
+        node.id = 2 * upperNodes.size() - 2;
+      } else {
+        node.id = 2 * lowerNodes.size() - 1;
+      }
+    }
+    void next(Node& node) const {
+      node.id -= 2;
+      if (node.id == -2) {
+        node.id = 2 * lowerNodes.size() - 1;
+      }
+    }
+  
+    void first(Edge& edge) const {
+      edge.id = edges.size() - 1;
+    }
+    void next(Edge& edge) const {
+      --edge.id;
+    }
+
+    void firstDown(Edge& edge, const Node& node) const {
+      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
+      edge.id = upperNodes[node.id >> 1].first;
+    }
+    void nextDown(Edge& edge) const {
+      edge.id = edges[edge.id].next_down;
+    }
+
+    void firstUp(Edge& edge, const Node& node) const {
+      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
+      edge.id = lowerNodes[node.id >> 1].first;
+    }
+    void nextUp(Edge& edge) const {
+      edge.id = edges[edge.id].next_up;
+    }
+
+    static int id(const Node& node) {
+      return node.id;
+    }
+    static Node nodeFromId(int id) {
+      return Node(id);
+    }
+    int maxNodeId() const {
+      return upperNodes.size() > lowerNodes.size() ?
+        upperNodes.size() * 2 - 2 : lowerNodes.size() * 2 - 1;
+    }
+  
+    static int id(const Edge& edge) {
+      return edge.id;
+    }
+    static Edge edgeFromId(int id) {
+      return Edge(id);
+    }
+    int maxEdgeId() const {
+      return edges.size();
+    }
+  
+    static int upperId(const Node& node) {
+      return node.id >> 1;
+    }
+    static Node fromUpperId(int id, Node) {
+      return Node(id << 1);
+    }
+    int maxUpperId() const {
+      return upperNodes.size();
+    }
+
+    static int lowerId(const Node& node) {
+      return node.id >> 1;
+    }
+    static Node fromLowerId(int id) {
+      return Node((id << 1) + 1);
+    }
+    int maxLowerId() const {
+      return lowerNodes.size();
+    }
+
+    Node upperNode(const Edge& edge) const {
+      return Node(edges[edge.id].upper);
+    }
+    Node lowerNode(const Edge& edge) const {
+      return Node(edges[edge.id].lower);
+    }
+
+    static bool upper(const Node& node) {
+      return (node.id & 1) == 0;
+    }
+
+    static bool lower(const Node& node) {
+      return (node.id & 1) == 1;
+    }
+
+    Node addUpperNode() {
+      NodeT nodeT;
+      nodeT.first = -1;
+      upperNodes.push_back(nodeT);
+      return Node(upperNodes.size() * 2 - 2);
+    }
+
+    Node addLowerNode() {
+      NodeT nodeT;
+      nodeT.first = -1;
+      lowerNodes.push_back(nodeT);
+      return Node(lowerNodes.size() * 2 - 1);
+    }
+
+    Edge addEdge(const Node& source, const Node& target) {
+      LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
+      EdgeT edgeT;
+      if ((source.id & 1) == 0) {
+        edgeT.upper = source.id;
+        edgeT.lower = target.id;
+      } else {
+        edgeT.upper = target.id;
+        edgeT.lower = source.id;
+      }
+      edgeT.next_down = upperNodes[edgeT.upper >> 1].first;
+      upperNodes[edgeT.upper >> 1].first = edges.size();
+      edgeT.next_up = lowerNodes[edgeT.lower >> 1].first;
+      lowerNodes[edgeT.lower >> 1].first = edges.size();
+      edges.push_back(edgeT);
+      return Edge(edges.size() - 1);
+    }
+
+    void clear() {
+      upperNodes.clear();
+      lowerNodes.clear();
+      edges.clear();
+    }
+
+  };
+
+
+  typedef ClearableUndirBipartiteGraphExtender<
+    ExtendableUndirBipartiteGraphExtender<
+    MappableUndirBipartiteGraphExtender<
+    IterableUndirBipartiteGraphExtender<
+    AlterableUndirBipartiteGraphExtender<
+    UndirBipartiteGraphExtender <
+    SmartUndirBipartiteGraphBase> > > > > >
+  ExtendedSmartUndirBipartiteGraphBase;
+
+
+  class SmartUndirBipartiteGraph : 
+    public ExtendedSmartUndirBipartiteGraphBase {
+  };
+
   
   /// @}