COIN-OR::LEMON - Graph Library

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


Ignore:
Timestamp:
01/26/06 17:24:40 (14 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:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/full_graph.h

    r1909 r1910  
    404404
    405405
    406   class FullUBipartiteGraphBase {
     406  class FullBpUGraphBase {
    407407  protected:
    408408
    409     int _upperNodeNum;
    410     int _lowerNodeNum;
     409    int _aNodeNum;
     410    int _bNodeNum;
    411411
    412412    int _edgeNum;
     
    416416    class NodeSetError : public LogicError {
    417417      virtual const char* exceptionName() const {
    418         return "lemon::FullUBipartiteGraph::NodeSetError";
     418        return "lemon::FullBpUGraph::NodeSetError";
    419419      }
    420420    };
    421421 
    422422    class Node {
    423       friend class FullUBipartiteGraphBase;
     423      friend class FullBpUGraphBase;
    424424    protected:
    425425      int id;
     
    435435
    436436    class Edge {
    437       friend class FullUBipartiteGraphBase;
     437      friend class FullBpUGraphBase;
    438438    protected:
    439439      int id;
     
    448448    };
    449449
    450     void construct(int upperNodeNum, int lowerNodeNum) {
    451       _upperNodeNum = upperNodeNum;
    452       _lowerNodeNum = lowerNodeNum;
    453       _edgeNum = upperNodeNum * lowerNodeNum;
    454     }
    455 
    456     void firstUpper(Node& node) const {
    457       node.id = 2 * _upperNodeNum - 2;
     450    void construct(int aNodeNum, int bNodeNum) {
     451      _aNodeNum = aNodeNum;
     452      _bNodeNum = bNodeNum;
     453      _edgeNum = aNodeNum * bNodeNum;
     454    }
     455
     456    void firstANode(Node& node) const {
     457      node.id = 2 * _aNodeNum - 2;
    458458      if (node.id < 0) node.id = -1;
    459459    }
    460     void nextUpper(Node& node) const {
     460    void nextANode(Node& node) const {
    461461      node.id -= 2;
    462462      if (node.id < 0) node.id = -1;
    463463    }
    464464
    465     void firstLower(Node& node) const {
    466       node.id = 2 * _lowerNodeNum - 1;
    467     }
    468     void nextLower(Node& node) const {
     465    void firstBNode(Node& node) const {
     466      node.id = 2 * _bNodeNum - 1;
     467    }
     468    void nextBNode(Node& node) const {
    469469      node.id -= 2;
    470470    }
    471471
    472472    void first(Node& node) const {
    473       if (_upperNodeNum > 0) {
    474         node.id = 2 * _upperNodeNum - 2;
     473      if (_aNodeNum > 0) {
     474        node.id = 2 * _aNodeNum - 2;
    475475      } else {
    476         node.id = 2 * _lowerNodeNum - 1;
     476        node.id = 2 * _bNodeNum - 1;
    477477      }
    478478    }
     
    480480      node.id -= 2;
    481481      if (node.id == -2) {
    482         node.id = 2 * _lowerNodeNum - 1;
     482        node.id = 2 * _bNodeNum - 1;
    483483      }
    484484    }
     
    491491    }
    492492
    493     void firstDown(Edge& edge, const Node& node) const {
     493    void firstOut(Edge& edge, const Node& node) const {
    494494      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
    495       edge.id = (node.id >> 1) * _lowerNodeNum;
    496     }
    497     void nextDown(Edge& edge) const {
     495      edge.id = (node.id >> 1) * _bNodeNum;
     496    }
     497    void nextOut(Edge& edge) const {
    498498      ++(edge.id);
    499       if (edge.id % _lowerNodeNum == 0) edge.id = -1;
    500     }
    501 
    502     void firstUp(Edge& edge, const Node& node) const {
     499      if (edge.id % _bNodeNum == 0) edge.id = -1;
     500    }
     501
     502    void firstIn(Edge& edge, const Node& node) const {
    503503      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
    504504      edge.id = (node.id >> 1);
    505505    }
    506     void nextUp(Edge& edge) const {
    507       edge.id += _lowerNodeNum;
     506    void nextIn(Edge& edge) const {
     507      edge.id += _bNodeNum;
    508508      if (edge.id >= _edgeNum) edge.id = -1;
    509509    }
     
    516516    }
    517517    int maxNodeId() const {
    518       return _upperNodeNum > _lowerNodeNum ?
    519         _upperNodeNum * 2 - 2 : _lowerNodeNum * 2 - 1;
     518      return _aNodeNum > _bNodeNum ?
     519        _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1;
    520520    }
    521521 
     
    530530    }
    531531 
    532     static int upperId(const Node& node) {
     532    static int aNodeId(const Node& node) {
    533533      return node.id >> 1;
    534534    }
    535     static Node fromUpperId(int id, Node) {
     535    static Node fromANodeId(int id, Node) {
    536536      return Node(id << 1);
    537537    }
    538     int maxUpperId() const {
    539       return _upperNodeNum;
    540     }
    541 
    542     static int lowerId(const Node& node) {
     538    int maxANodeId() const {
     539      return _aNodeNum;
     540    }
     541
     542    static int bNodeId(const Node& node) {
    543543      return node.id >> 1;
    544544    }
    545     static Node fromLowerId(int id) {
     545    static Node fromBNodeId(int id) {
    546546      return Node((id << 1) + 1);
    547547    }
    548     int maxLowerId() const {
    549       return _lowerNodeNum;
    550     }
    551 
    552     Node upperNode(const Edge& edge) const {
    553       return Node((edge.id / _lowerNodeNum) << 1);
    554     }
    555     Node lowerNode(const Edge& edge) const {
    556       return Node(((edge.id % _lowerNodeNum) << 1) + 1);
    557     }
    558 
    559     static bool upper(const Node& node) {
     548    int maxBNodeId() const {
     549      return _bNodeNum;
     550    }
     551
     552    Node aNode(const Edge& edge) const {
     553      return Node((edge.id / _bNodeNum) << 1);
     554    }
     555    Node bNode(const Edge& edge) const {
     556      return Node(((edge.id % _bNodeNum) << 1) + 1);
     557    }
     558
     559    static bool aNode(const Node& node) {
    560560      return (node.id & 1) == 0;
    561561    }
    562562
    563     static bool lower(const Node& node) {
     563    static bool bNode(const Node& node) {
    564564      return (node.id & 1) == 1;
    565565    }
    566566
    567     static Node upperNode(int index) {
     567    static Node aNode(int index) {
    568568      return Node(index << 1);
    569569    }
    570570
    571     static Node lowerNode(int index) {
     571    static Node bNode(int index) {
    572572      return Node((index << 1) + 1);
    573573    }
     
    576576
    577577
    578   typedef StaticMappableUBipartiteGraphExtender<
    579     IterableUBipartiteGraphExtender<
    580     AlterableUBipartiteGraphExtender<
    581     UBipartiteGraphExtender <
    582     FullUBipartiteGraphBase> > > >
    583   ExtendedFullUBipartiteGraphBase;
    584 
    585 
    586   class FullUBipartiteGraph :
    587     public ExtendedFullUBipartiteGraphBase {
    588   public:
    589     typedef ExtendedFullUBipartiteGraphBase Parent;
    590     FullUBipartiteGraph(int upperNodeNum, int lowerNodeNum) {
    591       Parent::construct(upperNodeNum, lowerNodeNum);
     578  typedef StaticMappableBpUGraphExtender<
     579    IterableBpUGraphExtender<
     580    AlterableBpUGraphExtender<
     581    BpUGraphExtender <
     582    FullBpUGraphBase> > > >
     583  ExtendedFullBpUGraphBase;
     584
     585
     586  /// \ingroup graphs
     587  ///
     588  /// \brief An undirected full bipartite graph class.
     589  ///
     590  /// This is a simple and fast bipartite undirected full graph implementation.
     591  /// It is completely static, so you can neither add nor delete either
     592  /// edges or nodes.
     593  ///
     594  /// \sa FullGraph
     595  ///
     596  /// \author Balazs Dezso
     597  class FullBpUGraph :
     598    public ExtendedFullBpUGraphBase {
     599  public:
     600    typedef ExtendedFullBpUGraphBase Parent;
     601    FullBpUGraph(int aNodeNum, int bNodeNum) {
     602      Parent::construct(aNodeNum, bNodeNum);
    592603    }
    593604  };
Note: See TracChangeset for help on using the changeset viewer.