Changeset 1982:f0eb6b79dcdf in lemon-0.x for lemon

Timestamp:

02/23/06 16:10:45 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

ListBpUGraph

File:

• lemon/list_graph.h (modified) (1 diff)

lemon/list_graph.h

@@ -637 +637 @@
   };
 
+
+  class ListBpUGraphBase {
+  public:
+
+    class NodeSetError : public LogicError {
+      virtual const char* exceptionName() const { 
+        return "lemon::ListBpUGraph::NodeSetError";
+      }
+    };
+
+  protected:
+
+    struct NodeT {
+      int first_edge, next_node;
+    };
+
+    struct EdgeT {
+      int aNode, prev_out, next_out;
+      int bNode, prev_in, next_in;
+    };
+
+    std::vector<NodeT> aNodes;
+    std::vector<NodeT> bNodes;
+
+    std::vector<EdgeT> edges;
+
+    int first_anode;
+    int first_free_anode;
+
+    int first_bnode;
+    int first_free_bnode;
+
+    int first_free_edge;
+
+  public:
+  
+    class Node {
+      friend class ListBpUGraphBase;
+    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 ListBpUGraphBase;
+    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;}
+    };
+
+    ListBpUGraphBase()
+      : first_anode(-1), first_free_anode(-1),
+        first_bnode(-1), first_free_bnode(-1),
+        first_free_edge(-1) {}
+
+    void firstANode(Node& node) const {
+      node.id = first_anode != -1 ? (first_anode << 1) : -1;
+    }
+    void nextANode(Node& node) const {
+      node.id = aNodes[node.id >> 1].next_node;
+    }
+
+    void firstBNode(Node& node) const {
+      node.id =  first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
+    }
+    void nextBNode(Node& node) const {
+      node.id = aNodes[node.id >> 1].next_node;
+    }
+
+    void first(Node& node) const {
+      if (first_anode != -1) {
+        node.id = (first_anode << 1);
+      } else if (first_bnode != -1) {
+        node.id = (first_bnode << 1) + 1;
+      } else {
+        node.id = -1;
+      }
+    }
+    void next(Node& node) const {
+      if (aNode(node)) {
+        node.id = aNodes[node.id >> 1].next_node;
+        if (node.id == -1) {
+          if (first_bnode != -1) {
+            node.id = (first_bnode << 1) + 1;
+          }
+        }
+      } else {
+        node.id = bNodes[node.id >> 1].next_node;
+      }
+    }
+  
+    void first(Edge& edge) const {
+      int aNodeId = first_anode;
+      while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
+        aNodeId = aNodes[aNodeId].next_node != -1 ? 
+          aNodes[aNodeId].next_node >> 1 : -1;
+      }
+      if (aNodeId != -1) {
+        edge.id = aNodes[aNodeId].first_edge;
+      } else {
+        edge.id = -1;
+      }
+    }
+    void next(Edge& edge) const {
+      int aNodeId = edges[edge.id].aNode >> 1;
+      edge.id = edges[edge.id].next_out;
+      if (edge.id == -1) {
+        aNodeId = aNodes[aNodeId].next_node != -1 ? 
+          aNodes[aNodeId].next_node >> 1 : -1;
+        while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
+          aNodeId = aNodes[aNodeId].next_node != -1 ? 
+          aNodes[aNodeId].next_node >> 1 : -1;
+        }
+        if (aNodeId != -1) {
+          edge.id = aNodes[aNodeId].first_edge;
+        } else {
+          edge.id = -1;
+        }
+      }
+    }
+
+    void firstOut(Edge& edge, const Node& node) const {
+      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
+      edge.id = aNodes[node.id >> 1].first_edge;
+    }
+    void nextOut(Edge& edge) const {
+      edge.id = edges[edge.id].next_out;
+    }
+
+    void firstIn(Edge& edge, const Node& node) const {
+      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
+      edge.id = bNodes[node.id >> 1].first_edge;
+    }
+    void nextIn(Edge& edge) const {
+      edge.id = edges[edge.id].next_in;
+    }
+
+    static int id(const Node& node) {
+      return node.id;
+    }
+    static Node nodeFromId(int id) {
+      return Node(id);
+    }
+    int maxNodeId() const {
+      return aNodes.size() > bNodes.size() ?
+        aNodes.size() * 2 - 2 : bNodes.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 aNodeId(const Node& node) {
+      return node.id >> 1;
+    }
+    static Node fromANodeId(int id, Node) {
+      return Node(id << 1);
+    }
+    int maxANodeId() const {
+      return aNodes.size();
+    }
+
+    static int bNodeId(const Node& node) {
+      return node.id >> 1;
+    }
+    static Node fromBNodeId(int id) {
+      return Node((id << 1) + 1);
+    }
+    int maxBNodeId() const {
+      return bNodes.size();
+    }
+
+    Node aNode(const Edge& edge) const {
+      return Node(edges[edge.id].aNode);
+    }
+    Node bNode(const Edge& edge) const {
+      return Node(edges[edge.id].bNode);
+    }
+
+    static bool aNode(const Node& node) {
+      return (node.id & 1) == 0;
+    }
+
+    static bool bNode(const Node& node) {
+      return (node.id & 1) == 1;
+    }
+
+    Node addANode() {
+      int aNodeId;
+      if (first_free_anode == -1) {
+        aNodeId = aNodes.size();
+        aNodes.push_back(NodeT());
+      } else {
+        aNodeId = first_free_anode;
+        first_free_anode = aNodes[first_free_anode].next_node;
+      }
+      aNodes[aNodeId].next_node = 
+        first_anode != -1 ? (first_anode << 1) : -1;
+      first_anode = aNodeId;
+      aNodes[aNodeId].first_edge = -1;
+      return Node(aNodeId << 1);
+    }
+
+    Node addBNode() {
+      int bNodeId;
+      if (first_free_anode == -1) {
+        bNodeId = bNodes.size();
+        bNodes.push_back(NodeT());
+      } else {
+        bNodeId = first_free_bnode;
+        first_free_bnode = bNodes[first_free_bnode].next_node;
+      }
+      bNodes[bNodeId].next_node = 
+        first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
+      first_bnode = bNodeId;
+      bNodes[bNodeId].first_edge = -1;
+      return Node((bNodeId << 1) + 1);
+    }
+
+    Edge addEdge(const Node& source, const Node& target) {
+      LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
+      int edgeId;
+      if (first_free_edge != -1) {
+        edgeId = first_free_edge;
+        first_free_edge = edges[edgeId].next_out;
+      } else {
+        edgeId = edges.size();
+        edges.push_back(EdgeT());
+      }
+      if ((source.id & 1) == 0) {
+        edges[edgeId].aNode = source.id;
+        edges[edgeId].bNode = target.id;
+      } else {
+        edges[edgeId].aNode = target.id;
+        edges[edgeId].bNode = source.id;
+      }
+      edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;
+      edges[edgeId].prev_out = -1;
+      if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {
+        edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;
+      }
+      aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;
+      edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;
+      edges[edgeId].prev_in = -1;
+      if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {
+        edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;
+      }
+      bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
+      return Edge(edgeId);
+    }
+
+    void erase(const Node& node) {
+      if (aNode(node)) {
+        int aNodeId = node.id >> 1;
+        aNodes[aNodeId].next_node = first_free_anode;
+        first_free_anode = aNodeId;
+      } else {
+        int bNodeId = node.id >> 1;
+        bNodes[bNodeId].next_node = first_free_bnode;
+        first_free_bnode = bNodeId;
+      }
+    }
+
+    void erase(const Edge& edge) {
+      if (edges[edge.id].prev_out != -1) {
+        edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
+      } else {
+        aNodes[edges[edge.id].aNode].first_edge = edges[edge.id].next_out;
+      }
+      if (edges[edge.id].next_out != -1) {
+        edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
+      }
+      if (edges[edge.id].prev_in != -1) {
+        edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
+      } else {
+        bNodes[edges[edge.id].bNode].first_edge = edges[edge.id].next_in;
+      }
+      if (edges[edge.id].next_in != -1) {
+        edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
+      }
+      edges[edge.id].next_out = first_free_edge;
+      first_free_edge = edge.id;
+    }
+
+    void clear() {
+      aNodes.clear();
+      bNodes.clear();
+      edges.clear();
+      first_anode = -1;
+      first_free_anode = -1;
+      first_bnode = -1;
+      first_free_bnode = -1;
+      first_free_edge = -1;
+    }
+
+  };
+
+
+  typedef BpUGraphExtender< BpUGraphBaseExtender<
+    ListBpUGraphBase> > ExtendedListBpUGraphBase;
+
+  /// \ingroup graphs
+  ///
+  /// \brief A smart bipartite undirected graph class.
+  ///
+  /// This is a bipartite undirected graph implementation.
+  /// Except from this it conforms to 
+  /// the \ref concept::BpUGraph "BpUGraph" concept.
+  /// \sa concept::BpUGraph.
+  ///
+  class ListBpUGraph : public ExtendedListBpUGraphBase {};
+
   
   /// @}