Changeset 2116:b6a68c15a6a3 in lemon-0.x for lemon/smart_graph.h

Timestamp:

06/30/06 14:15:45 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

Revert splitted files

File:

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

lemon/smart_graph.h

@@ -22 +22 @@
 ///\ingroup graphs
 ///\file
-///\brief SmartGraph class.
+///\brief SmartGraph and SmartUGraph classes.
 
 #include <vector>
@@ -28 +28 @@
 #include <lemon/bits/invalid.h>
 
+#include <lemon/bits/base_extender.h>
 #include <lemon/bits/graph_extender.h>
 
 #include <lemon/bits/utility.h>
+#include <lemon/error.h>
 
 #include <lemon/bits/graph_extender.h>
@@ -355 +357 @@
 
 
+  /**************** Undirected List Graph ****************/
+
+  typedef UGraphExtender<UndirGraphExtender<SmartGraphBase> >
+  ExtendedSmartUGraphBase;
+
+  /// \ingroup graphs
+  ///
+  /// \brief A smart undirected graph class.
+  ///
+  /// This is a simple and fast undirected graph implementation.
+  /// It is also quite memory efficient, but at the price
+  /// that <b> it does support only limited (only stack-like)
+  /// node and edge deletions</b>.
+  /// Except from this it conforms to 
+  /// the \ref concept::UGraph "UGraph" concept.
+  /// \sa concept::UGraph.
+  ///
+  /// \todo Snapshot hasn't been implemented yet.
+  ///
+  class SmartUGraph : public ExtendedSmartUGraphBase {
+  };
+
+
+  class SmartBpUGraphBase {
+  public:
+
+    class NodeSetError : public LogicError {
+      virtual const char* exceptionName() const { 
+        return "lemon::SmartBpUGraph::NodeSetError";
+      }
+    };
+
+  protected:
+
+    struct NodeT {
+      int first;
+      NodeT() {}
+      NodeT(int _first) : first(_first) {}
+    };
+
+    struct UEdgeT {
+      int aNode, next_out;
+      int bNode, next_in;
+    };
+
+    std::vector<NodeT> aNodes;
+    std::vector<NodeT> bNodes;
+
+    std::vector<UEdgeT> edges;
+
+  public:
+  
+    class Node {
+      friend class SmartBpUGraphBase;
+    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 UEdge {
+      friend class SmartBpUGraphBase;
+    protected:
+      int id;
+
+      UEdge(int _id) { id = _id;}
+    public:
+      UEdge() {}
+      UEdge (Invalid) { id = -1; }
+      bool operator==(const UEdge i) const {return id==i.id;}
+      bool operator!=(const UEdge i) const {return id!=i.id;}
+      bool operator<(const UEdge i) const {return id<i.id;}
+    };
+
+    void firstANode(Node& node) const {
+      node.id = 2 * aNodes.size() - 2;
+      if (node.id < 0) node.id = -1; 
+    }
+    void nextANode(Node& node) const {
+      node.id -= 2;
+      if (node.id < 0) node.id = -1; 
+    }
+
+    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 (aNodes.size() > 0) {
+        node.id = 2 * aNodes.size() - 2;
+      } else {
+        node.id = 2 * bNodes.size() - 1;
+      }
+    }
+    void next(Node& node) const {
+      node.id -= 2;
+      if (node.id == -2) {
+        node.id = 2 * bNodes.size() - 1;
+      }
+    }
+  
+    void first(UEdge& edge) const {
+      edge.id = edges.size() - 1;
+    }
+    void next(UEdge& edge) const {
+      --edge.id;
+    }
+
+    void firstFromANode(UEdge& edge, const Node& node) const {
+      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
+      edge.id = aNodes[node.id >> 1].first;
+    }
+    void nextFromANode(UEdge& edge) const {
+      edge.id = edges[edge.id].next_out;
+    }
+
+    void firstFromBNode(UEdge& edge, const Node& node) const {
+      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
+      edge.id = bNodes[node.id >> 1].first;
+    }
+    void nextFromBNode(UEdge& 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 UEdge& edge) {
+      return edge.id;
+    }
+    static UEdge uEdgeFromId(int id) {
+      return UEdge(id);
+    }
+    int maxUEdgeId() const {
+      return edges.size();
+    }
+  
+    static int aNodeId(const Node& node) {
+      return node.id >> 1;
+    }
+    static Node fromANodeId(int id) {
+      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 UEdge& edge) const {
+      return Node(edges[edge.id].aNode);
+    }
+    Node bNode(const UEdge& 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() {
+      NodeT nodeT;
+      nodeT.first = -1;
+      aNodes.push_back(nodeT);
+      return Node(aNodes.size() * 2 - 2);
+    }
+
+    Node addBNode() {
+      NodeT nodeT;
+      nodeT.first = -1;
+      bNodes.push_back(nodeT);
+      return Node(bNodes.size() * 2 - 1);
+    }
+
+    UEdge addEdge(const Node& source, const Node& target) {
+      LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
+      UEdgeT edgeT;
+      if ((source.id & 1) == 0) {
+        edgeT.aNode = source.id;
+        edgeT.bNode = target.id;
+      } else {
+        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 UEdge(edges.size() - 1);
+    }
+
+    void clear() {
+      aNodes.clear();
+      bNodes.clear();
+      edges.clear();
+    }
+
+    typedef True NodeNumTag;
+    int nodeNum() const { return aNodes.size() + bNodes.size(); }
+    int aNodeNum() const { return aNodes.size(); }
+    int bNodeNum() const { return bNodes.size(); }
+
+    typedef True EdgeNumTag;
+    int uEdgeNum() const { return edges.size(); }
+
+  };
+
+
+  typedef 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 {};
+
+  
+  /// @}  
 } //namespace lemon