Changeset 1910:f95eea8c34b0 in lemon-0.x for lemon/smart_graph.h

Timestamp:

01/26/06 17:24:40 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

Bipartite => Bp
Upper => A
Lower => B

+ some bug fix

File:

• lemon/smart_graph.h (modified) (12 diffs)

lemon/smart_graph.h

@@ -379 +379 @@
 
 
-  class SmartUBipartiteGraphBase {
+  class SmartBpUGraphBase {
   public:
 
     class NodeSetError : public LogicError {
       virtual const char* exceptionName() const { 
-        return "lemon::FullUBipartiteGraph::NodeSetError";
+        return "lemon::SmartBpUGraph::NodeSetError";
       }
     };
@@ -397 +397 @@
 
     struct EdgeT {
-      int upper, next_down;
-      int lower, next_up;
-    };
-
-    std::vector<NodeT> upperNodes;
-    std::vector<NodeT> lowerNodes;
+      int aNode, next_out;
+      int bNode, next_in;
+    };
+
+    std::vector<NodeT> aNodes;
+    std::vector<NodeT> bNodes;
 
     std::vector<EdgeT> edges;
@@ -409 +409 @@
   
     class Node {
-      friend class SmartUBipartiteGraphBase;
+      friend class SmartBpUGraphBase;
     protected:
       int id;
@@ -423 +423 @@
 
     class Edge {
-      friend class SmartUBipartiteGraphBase;
+      friend class SmartBpUGraphBase;
     protected:
       int id;
@@ -436 +436 @@
     };
 
-    void firstUpper(Node& node) const {
-      node.id = 2 * upperNodes.size() - 2;
+    void firstANode(Node& node) const {
+      node.id = 2 * aNodes.size() - 2;
       if (node.id < 0) node.id = -1; 
     }
-    void nextUpper(Node& node) const {
+    void nextANode(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 {
+    void firstBNode(Node& node) const {
+      node.id = 2 * bNodes.size() - 1;
+    }
+    void nextBNode(Node& node) const {
       node.id -= 2;
     }
 
     void first(Node& node) const {
-      if (upperNodes.size() > 0) {
-        node.id = 2 * upperNodes.size() - 2;
+      if (aNodes.size() > 0) {
+        node.id = 2 * aNodes.size() - 2;
       } else {
-        node.id = 2 * lowerNodes.size() - 1;
+        node.id = 2 * bNodes.size() - 1;
       }
     }
@@ -462 +462 @@
       node.id -= 2;
       if (node.id == -2) {
-        node.id = 2 * lowerNodes.size() - 1;
+        node.id = 2 * bNodes.size() - 1;
       }
     }
@@ -473 +473 @@
     }
 
-    void firstDown(Edge& edge, const Node& node) const {
+    void firstOut(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 {
+      edge.id = aNodes[node.id >> 1].first;
+    }
+    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 = lowerNodes[node.id >> 1].first;
-    }
-    void nextUp(Edge& edge) const {
-      edge.id = edges[edge.id].next_up;
+      edge.id = bNodes[node.id >> 1].first;
+    }
+    void nextIn(Edge& edge) const {
+      edge.id = edges[edge.id].next_in;
     }
 
@@ -496 +496 @@
     }
     int maxNodeId() const {
-      return upperNodes.size() > lowerNodes.size() ?
-        upperNodes.size() * 2 - 2 : lowerNodes.size() * 2 - 1;
+      return aNodes.size() > bNodes.size() ?
+        aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
     }
   
@@ -510 +510 @@
     }
   
-    static int upperId(const Node& node) {
+    static int aNodeId(const Node& node) {
       return node.id >> 1;
     }
-    static Node fromUpperId(int id, Node) {
+    static Node fromANodeId(int id, Node) {
       return Node(id << 1);
     }
-    int maxUpperId() const {
-      return upperNodes.size();
-    }
-
-    static int lowerId(const Node& node) {
+    int maxANodeId() const {
+      return aNodes.size();
+    }
+
+    static int bNodeId(const Node& node) {
       return node.id >> 1;
     }
-    static Node fromLowerId(int id) {
+    static Node fromBNodeId(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) {
+    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 lower(const Node& node) {
+    static bool bNode(const Node& node) {
       return (node.id & 1) == 1;
     }
 
-    Node addUpperNode() {
+    Node addANode() {
       NodeT nodeT;
       nodeT.first = -1;
-      upperNodes.push_back(nodeT);
-      return Node(upperNodes.size() * 2 - 2);
-    }
-
-    Node addLowerNode() {
+      aNodes.push_back(nodeT);
+      return Node(aNodes.size() * 2 - 2);
+    }
+
+    Node addBNode() {
       NodeT nodeT;
       nodeT.first = -1;
-      lowerNodes.push_back(nodeT);
-      return Node(lowerNodes.size() * 2 - 1);
+      bNodes.push_back(nodeT);
+      return Node(bNodes.size() * 2 - 1);
     }
 
@@ -563 +563 @@
       EdgeT edgeT;
       if ((source.id & 1) == 0) {
-        edgeT.upper = source.id;
-        edgeT.lower = target.id;
+        edgeT.aNode = source.id;
+        edgeT.bNode = 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();
+        edgeT.aNode = target.id;
+        edgeT.bNode = source.id;
+      }
+      edgeT.next_out = aNodes[edgeT.aNode >> 1].first;
+      aNodes[edgeT.aNode >> 1].first = edges.size();
+      edgeT.next_in = bNodes[edgeT.bNode >> 1].first;
+      bNodes[edgeT.bNode >> 1].first = edges.size();
       edges.push_back(edgeT);
       return Edge(edges.size() - 1);
@@ -578 +578 @@
 
     void clear() {
-      upperNodes.clear();
-      lowerNodes.clear();
+      aNodes.clear();
+      bNodes.clear();
       edges.clear();
     }
@@ -586 +586 @@
 
 
-  typedef ClearableUBipartiteGraphExtender<
-    ExtendableUBipartiteGraphExtender<
-    MappableUBipartiteGraphExtender<
-    IterableUBipartiteGraphExtender<
-    AlterableUBipartiteGraphExtender<
-    UBipartiteGraphExtender <
-    SmartUBipartiteGraphBase> > > > > >
-  ExtendedSmartUBipartiteGraphBase;
-
-
-  class SmartUBipartiteGraph : 
-    public ExtendedSmartUBipartiteGraphBase {
-  };
+  typedef ClearableBpUGraphExtender<
+    ExtendableBpUGraphExtender<
+    MappableBpUGraphExtender<
+    IterableBpUGraphExtender<
+    AlterableBpUGraphExtender<
+    BpUGraphExtender <
+    SmartBpUGraphBase> > > > > >
+  ExtendedSmartBpUGraphBase;
+
+  /// \ingroup graphs
+  ///
+  /// \brief A smart bipartite undirected graph class.
+  ///
+  /// This is a simple and fast bipartite undirected graph implementation.
+  /// It is also quite memory efficient, but at the price
+  /// that <b> it does not support node and edge deletions</b>.
+  /// Except from this it conforms to 
+  /// the \ref concept::BpUGraph "BpUGraph" concept.
+  /// \sa concept::BpUGraph.
+  ///
+  class SmartBpUGraph : public ExtendedSmartBpUGraphBase {};