Changeset 2115:4cd528a30ec1 in lemon-0.x for lemon/smart_graph.h

Timestamp:

06/30/06 14:14:36 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

Splitted graph files

File:

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

lemon/smart_graph.h

@@ -22 +22 @@
 ///\ingroup graphs
 ///\file
-///\brief SmartGraph and SmartUGraph classes.
+///\brief SmartGraph class.
 
 #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>
@@ -357 +355 @@
 
 
-  /**************** 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