COIN-OR::LEMON - Graph Library

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


Ignore:
Timestamp:
06/30/06 14:15:45 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2822
Message:

Revert splitted files

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/smart_graph.h

    r2115 r2116  
    2222///\ingroup graphs
    2323///\file
    24 ///\brief SmartGraph class.
     24///\brief SmartGraph and SmartUGraph classes.
    2525
    2626#include <vector>
     
    2828#include <lemon/bits/invalid.h>
    2929
     30#include <lemon/bits/base_extender.h>
    3031#include <lemon/bits/graph_extender.h>
    3132
    3233#include <lemon/bits/utility.h>
     34#include <lemon/error.h>
    3335
    3436#include <lemon/bits/graph_extender.h>
     
    355357
    356358
     359  /**************** Undirected List Graph ****************/
     360
     361  typedef UGraphExtender<UndirGraphExtender<SmartGraphBase> >
     362  ExtendedSmartUGraphBase;
     363
     364  /// \ingroup graphs
     365  ///
     366  /// \brief A smart undirected graph class.
     367  ///
     368  /// This is a simple and fast undirected graph implementation.
     369  /// It is also quite memory efficient, but at the price
     370  /// that <b> it does support only limited (only stack-like)
     371  /// node and edge deletions</b>.
     372  /// Except from this it conforms to
     373  /// the \ref concept::UGraph "UGraph" concept.
     374  /// \sa concept::UGraph.
     375  ///
     376  /// \todo Snapshot hasn't been implemented yet.
     377  ///
     378  class SmartUGraph : public ExtendedSmartUGraphBase {
     379  };
     380
     381
     382  class SmartBpUGraphBase {
     383  public:
     384
     385    class NodeSetError : public LogicError {
     386      virtual const char* exceptionName() const {
     387        return "lemon::SmartBpUGraph::NodeSetError";
     388      }
     389    };
     390
     391  protected:
     392
     393    struct NodeT {
     394      int first;
     395      NodeT() {}
     396      NodeT(int _first) : first(_first) {}
     397    };
     398
     399    struct UEdgeT {
     400      int aNode, next_out;
     401      int bNode, next_in;
     402    };
     403
     404    std::vector<NodeT> aNodes;
     405    std::vector<NodeT> bNodes;
     406
     407    std::vector<UEdgeT> edges;
     408
     409  public:
     410 
     411    class Node {
     412      friend class SmartBpUGraphBase;
     413    protected:
     414      int id;
     415
     416      Node(int _id) : id(_id) {}
     417    public:
     418      Node() {}
     419      Node(Invalid) { id = -1; }
     420      bool operator==(const Node i) const {return id==i.id;}
     421      bool operator!=(const Node i) const {return id!=i.id;}
     422      bool operator<(const Node i) const {return id<i.id;}
     423    };
     424
     425    class UEdge {
     426      friend class SmartBpUGraphBase;
     427    protected:
     428      int id;
     429
     430      UEdge(int _id) { id = _id;}
     431    public:
     432      UEdge() {}
     433      UEdge (Invalid) { id = -1; }
     434      bool operator==(const UEdge i) const {return id==i.id;}
     435      bool operator!=(const UEdge i) const {return id!=i.id;}
     436      bool operator<(const UEdge i) const {return id<i.id;}
     437    };
     438
     439    void firstANode(Node& node) const {
     440      node.id = 2 * aNodes.size() - 2;
     441      if (node.id < 0) node.id = -1;
     442    }
     443    void nextANode(Node& node) const {
     444      node.id -= 2;
     445      if (node.id < 0) node.id = -1;
     446    }
     447
     448    void firstBNode(Node& node) const {
     449      node.id = 2 * bNodes.size() - 1;
     450    }
     451    void nextBNode(Node& node) const {
     452      node.id -= 2;
     453    }
     454
     455    void first(Node& node) const {
     456      if (aNodes.size() > 0) {
     457        node.id = 2 * aNodes.size() - 2;
     458      } else {
     459        node.id = 2 * bNodes.size() - 1;
     460      }
     461    }
     462    void next(Node& node) const {
     463      node.id -= 2;
     464      if (node.id == -2) {
     465        node.id = 2 * bNodes.size() - 1;
     466      }
     467    }
     468 
     469    void first(UEdge& edge) const {
     470      edge.id = edges.size() - 1;
     471    }
     472    void next(UEdge& edge) const {
     473      --edge.id;
     474    }
     475
     476    void firstFromANode(UEdge& edge, const Node& node) const {
     477      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
     478      edge.id = aNodes[node.id >> 1].first;
     479    }
     480    void nextFromANode(UEdge& edge) const {
     481      edge.id = edges[edge.id].next_out;
     482    }
     483
     484    void firstFromBNode(UEdge& edge, const Node& node) const {
     485      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
     486      edge.id = bNodes[node.id >> 1].first;
     487    }
     488    void nextFromBNode(UEdge& edge) const {
     489      edge.id = edges[edge.id].next_in;
     490    }
     491
     492    static int id(const Node& node) {
     493      return node.id;
     494    }
     495    static Node nodeFromId(int id) {
     496      return Node(id);
     497    }
     498    int maxNodeId() const {
     499      return aNodes.size() > bNodes.size() ?
     500        aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
     501    }
     502 
     503    static int id(const UEdge& edge) {
     504      return edge.id;
     505    }
     506    static UEdge uEdgeFromId(int id) {
     507      return UEdge(id);
     508    }
     509    int maxUEdgeId() const {
     510      return edges.size();
     511    }
     512 
     513    static int aNodeId(const Node& node) {
     514      return node.id >> 1;
     515    }
     516    static Node fromANodeId(int id) {
     517      return Node(id << 1);
     518    }
     519    int maxANodeId() const {
     520      return aNodes.size();
     521    }
     522
     523    static int bNodeId(const Node& node) {
     524      return node.id >> 1;
     525    }
     526    static Node fromBNodeId(int id) {
     527      return Node((id << 1) + 1);
     528    }
     529    int maxBNodeId() const {
     530      return bNodes.size();
     531    }
     532
     533    Node aNode(const UEdge& edge) const {
     534      return Node(edges[edge.id].aNode);
     535    }
     536    Node bNode(const UEdge& edge) const {
     537      return Node(edges[edge.id].bNode);
     538    }
     539
     540    static bool aNode(const Node& node) {
     541      return (node.id & 1) == 0;
     542    }
     543
     544    static bool bNode(const Node& node) {
     545      return (node.id & 1) == 1;
     546    }
     547
     548    Node addANode() {
     549      NodeT nodeT;
     550      nodeT.first = -1;
     551      aNodes.push_back(nodeT);
     552      return Node(aNodes.size() * 2 - 2);
     553    }
     554
     555    Node addBNode() {
     556      NodeT nodeT;
     557      nodeT.first = -1;
     558      bNodes.push_back(nodeT);
     559      return Node(bNodes.size() * 2 - 1);
     560    }
     561
     562    UEdge addEdge(const Node& source, const Node& target) {
     563      LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
     564      UEdgeT edgeT;
     565      if ((source.id & 1) == 0) {
     566        edgeT.aNode = source.id;
     567        edgeT.bNode = target.id;
     568      } else {
     569        edgeT.aNode = target.id;
     570        edgeT.bNode = source.id;
     571      }
     572      edgeT.next_out = aNodes[edgeT.aNode >> 1].first;
     573      aNodes[edgeT.aNode >> 1].first = edges.size();
     574      edgeT.next_in = bNodes[edgeT.bNode >> 1].first;
     575      bNodes[edgeT.bNode >> 1].first = edges.size();
     576      edges.push_back(edgeT);
     577      return UEdge(edges.size() - 1);
     578    }
     579
     580    void clear() {
     581      aNodes.clear();
     582      bNodes.clear();
     583      edges.clear();
     584    }
     585
     586    typedef True NodeNumTag;
     587    int nodeNum() const { return aNodes.size() + bNodes.size(); }
     588    int aNodeNum() const { return aNodes.size(); }
     589    int bNodeNum() const { return bNodes.size(); }
     590
     591    typedef True EdgeNumTag;
     592    int uEdgeNum() const { return edges.size(); }
     593
     594  };
     595
     596
     597  typedef BpUGraphExtender<SmartBpUGraphBase> ExtendedSmartBpUGraphBase;
     598
     599  /// \ingroup graphs
     600  ///
     601  /// \brief A smart bipartite undirected graph class.
     602  ///
     603  /// This is a simple and fast bipartite undirected graph implementation.
     604  /// It is also quite memory efficient, but at the price
     605  /// that <b> it does not support node and edge deletions</b>.
     606  /// Except from this it conforms to
     607  /// the \ref concept::BpUGraph "BpUGraph" concept.
     608  /// \sa concept::BpUGraph.
     609  ///
     610  class SmartBpUGraph : public ExtendedSmartBpUGraphBase {};
     611
     612 
     613  /// @} 
    357614} //namespace lemon
    358615
Note: See TracChangeset for help on using the changeset viewer.