COIN-OR::LEMON - Graph Library

Changeset 1820:22099ef840d7 in lemon-0.x for lemon/full_graph.h


Ignore:
Timestamp:
11/21/05 18:48:00 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2370
Message:

Undir Bipartite Graph/Full? and Smart/ without concept, doc and concept
checking

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/full_graph.h

    r1791 r1820  
    403403  };
    404404
     405
     406  class FullUndirBipartiteGraphBase {
     407  protected:
     408
     409    int _upperNodeNum;
     410    int _lowerNodeNum;
     411
     412    int _edgeNum;
     413
     414  public:
     415
     416    class NodeSetError : public LogicError {
     417      virtual const char* exceptionName() const {
     418        return "lemon::FullUndirBipartiteGraph::NodeSetError";
     419      }
     420    };
     421 
     422    class Node {
     423      friend class FullUndirBipartiteGraphBase;
     424    protected:
     425      int id;
     426
     427      Node(int _id) : id(_id) {}
     428    public:
     429      Node() {}
     430      Node(Invalid) { id = -1; }
     431      bool operator==(const Node i) const {return id==i.id;}
     432      bool operator!=(const Node i) const {return id!=i.id;}
     433      bool operator<(const Node i) const {return id<i.id;}
     434    };
     435
     436    class Edge {
     437      friend class FullUndirBipartiteGraphBase;
     438    protected:
     439      int id;
     440
     441      Edge(int _id) { id = _id;}
     442    public:
     443      Edge() {}
     444      Edge (Invalid) { id = -1; }
     445      bool operator==(const Edge i) const {return id==i.id;}
     446      bool operator!=(const Edge i) const {return id!=i.id;}
     447      bool operator<(const Edge i) const {return id<i.id;}
     448    };
     449
     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;
     458      if (node.id < 0) node.id = -1;
     459    }
     460    void nextUpper(Node& node) const {
     461      node.id -= 2;
     462      if (node.id < 0) node.id = -1;
     463    }
     464
     465    void firstLower(Node& node) const {
     466      node.id = 2 * _lowerNodeNum - 1;
     467    }
     468    void nextLower(Node& node) const {
     469      node.id -= 2;
     470    }
     471
     472    void first(Node& node) const {
     473      if (_upperNodeNum > 0) {
     474        node.id = 2 * _upperNodeNum - 2;
     475      } else {
     476        node.id = 2 * _lowerNodeNum - 1;
     477      }
     478    }
     479    void next(Node& node) const {
     480      node.id -= 2;
     481      if (node.id == -2) {
     482        node.id = 2 * _lowerNodeNum - 1;
     483      }
     484    }
     485 
     486    void first(Edge& edge) const {
     487      edge.id = _edgeNum - 1;
     488    }
     489    void next(Edge& edge) const {
     490      --edge.id;
     491    }
     492
     493    void firstDown(Edge& edge, const Node& node) const {
     494      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
     495      edge.id = (node.id >> 1) * _lowerNodeNum;
     496    }
     497    void nextDown(Edge& edge) const {
     498      ++(edge.id);
     499      if (edge.id % _lowerNodeNum == 0) edge.id = -1;
     500    }
     501
     502    void firstUp(Edge& edge, const Node& node) const {
     503      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
     504      edge.id = (node.id >> 1);
     505    }
     506    void nextUp(Edge& edge) const {
     507      edge.id += _lowerNodeNum;
     508      if (edge.id >= _edgeNum) edge.id = -1;
     509    }
     510
     511    static int id(const Node& node) {
     512      return node.id;
     513    }
     514    static Node nodeFromId(int id) {
     515      return Node(id);
     516    }
     517    int maxNodeId() const {
     518      return _upperNodeNum > _lowerNodeNum ?
     519        _upperNodeNum * 2 - 2 : _lowerNodeNum * 2 - 1;
     520    }
     521 
     522    static int id(const Edge& edge) {
     523      return edge.id;
     524    }
     525    static Edge edgeFromId(int id) {
     526      return Edge(id);
     527    }
     528    int maxEdgeId() const {
     529      return _edgeNum - 1;
     530    }
     531 
     532    static int upperId(const Node& node) {
     533      return node.id >> 1;
     534    }
     535    static Node fromUpperId(int id, Node) {
     536      return Node(id << 1);
     537    }
     538    int maxUpperId() const {
     539      return _upperNodeNum;
     540    }
     541
     542    static int lowerId(const Node& node) {
     543      return node.id >> 1;
     544    }
     545    static Node fromLowerId(int id) {
     546      return Node((id << 1) + 1);
     547    }
     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) {
     560      return (node.id & 1) == 0;
     561    }
     562
     563    static bool lower(const Node& node) {
     564      return (node.id & 1) == 1;
     565    }
     566
     567    static Node upperNode(int index) {
     568      return Node(index << 1);
     569    }
     570
     571    static Node lowerNode(int index) {
     572      return Node((index << 1) + 1);
     573    }
     574
     575  };
     576
     577
     578  typedef MappableUndirBipartiteGraphExtender<
     579    IterableUndirBipartiteGraphExtender<
     580    AlterableUndirBipartiteGraphExtender<
     581    UndirBipartiteGraphExtender <
     582    FullUndirBipartiteGraphBase> > > >
     583  ExtendedFullUndirBipartiteGraphBase;
     584
     585
     586  class FullUndirBipartiteGraph :
     587    public ExtendedFullUndirBipartiteGraphBase {
     588  public:
     589    typedef ExtendedFullUndirBipartiteGraphBase Parent;
     590    FullUndirBipartiteGraph(int upperNodeNum, int lowerNodeNum) {
     591      Parent::construct(upperNodeNum, lowerNodeNum);
     592    }
     593  };
     594
    405595} //namespace lemon
    406596
Note: See TracChangeset for help on using the changeset viewer.