COIN-OR::LEMON - Graph Library

Changeset 1188:5ef0ab7b61cd in lemon for lemon/full_graph.h


Ignore:
Timestamp:
11/14/10 22:48:32 (9 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Phase:
public
Message:

FullBpGraph? implementation (#69)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/full_graph.h

    r956 r1188  
    622622  };
    623623
     624  class FullBpGraphBase {
     625
     626  protected:
     627
     628    int _red_num, _blue_num;
     629    int _node_num, _edge_num;
     630
     631  public:
     632
     633    typedef FullBpGraphBase Graph;
     634
     635    class Node;
     636    class Arc;
     637    class Edge;
     638
     639    class Node {
     640      friend class FullBpGraphBase;
     641    protected:
     642
     643      int _id;
     644      explicit Node(int id) { _id = id;}
     645
     646    public:
     647      Node() {}
     648      Node (Invalid) { _id = -1; }
     649      bool operator==(const Node& node) const {return _id == node._id;}
     650      bool operator!=(const Node& node) const {return _id != node._id;}
     651      bool operator<(const Node& node) const {return _id < node._id;}
     652    };
     653
     654    class Edge {
     655      friend class FullBpGraphBase;
     656    protected:
     657
     658      int _id;
     659      explicit Edge(int id) { _id = id;}
     660
     661    public:
     662      Edge() {}
     663      Edge (Invalid) { _id = -1; }
     664      bool operator==(const Edge& arc) const {return _id == arc._id;}
     665      bool operator!=(const Edge& arc) const {return _id != arc._id;}
     666      bool operator<(const Edge& arc) const {return _id < arc._id;}
     667    };
     668
     669    class Arc {
     670      friend class FullBpGraphBase;
     671    protected:
     672
     673      int _id;
     674      explicit Arc(int id) { _id = id;}
     675
     676    public:
     677      operator Edge() const {
     678        return _id != -1 ? edgeFromId(_id / 2) : INVALID;
     679      }
     680
     681      Arc() {}
     682      Arc (Invalid) { _id = -1; }
     683      bool operator==(const Arc& arc) const {return _id == arc._id;}
     684      bool operator!=(const Arc& arc) const {return _id != arc._id;}
     685      bool operator<(const Arc& arc) const {return _id < arc._id;}
     686    };
     687
     688
     689  protected:
     690
     691    FullBpGraphBase()
     692      : _red_num(0), _blue_num(0), _node_num(0), _edge_num(0) {}
     693
     694    void construct(int redNum, int blueNum) {
     695      _red_num = redNum; _blue_num = blueNum;
     696      _node_num = redNum + blueNum; _edge_num = redNum * blueNum;
     697    }
     698
     699  public:
     700
     701    typedef True NodeNumTag;
     702    typedef True EdgeNumTag;
     703    typedef True ArcNumTag;
     704
     705    int nodeNum() const { return _node_num; }
     706    int redNum() const { return _red_num; }
     707    int blueNum() const { return _blue_num; }
     708    int edgeNum() const { return _edge_num; }
     709    int arcNum() const { return 2 * _edge_num; }
     710
     711    int maxNodeId() const { return _node_num - 1; }
     712    int maxRedId() const { return _red_num - 1; }
     713    int maxBlueId() const { return _blue_num - 1; }
     714    int maxEdgeId() const { return _edge_num - 1; }
     715    int maxArcId() const { return 2 * _edge_num - 1; }
     716
     717    bool red(Node n) const { return n._id < _red_num; }
     718    bool blue(Node n) const { return n._id >= _red_num; }
     719
     720    Node source(Arc a) const {
     721      if (a._id & 1) {
     722        return Node((a._id >> 1) % _red_num);
     723      } else {
     724        return Node((a._id >> 1) / _red_num + _red_num);
     725      }
     726    }
     727    Node target(Arc a) const {
     728      if (a._id & 1) {
     729        return Node((a._id >> 1) / _red_num + _red_num);
     730      } else {
     731        return Node((a._id >> 1) % _red_num);
     732      }
     733    }
     734
     735    Node redNode(Edge e) const {
     736      return Node(e._id % _red_num);
     737    }
     738    Node blueNode(Edge e) const {
     739      return Node(e._id / _red_num + _red_num);
     740    }
     741
     742    static bool direction(Arc a) {
     743      return (a._id & 1) == 1;
     744    }
     745
     746    static Arc direct(Edge e, bool d) {
     747      return Arc(e._id * 2 + (d ? 1 : 0));
     748    }
     749
     750    void first(Node& node) const {
     751      node._id = _node_num - 1;
     752    }
     753
     754    static void next(Node& node) {
     755      --node._id;
     756    }
     757
     758    void firstRed(Node& node) const {
     759      node._id = _red_num - 1;
     760    }
     761
     762    static void nextRed(Node& node) {
     763      --node._id;
     764    }
     765
     766    void firstBlue(Node& node) const {
     767      if (_red_num == _node_num) node._id = -1;
     768      else node._id = _node_num - 1;
     769    }
     770
     771    void nextBlue(Node& node) const {
     772      if (node._id == _red_num) node._id = -1;
     773      else --node._id;
     774    }
     775
     776    void first(Arc& arc) const {
     777      arc._id = 2 * _edge_num - 1;
     778    }
     779
     780    static void next(Arc& arc) {
     781      --arc._id;
     782    }
     783
     784    void first(Edge& arc) const {
     785      arc._id = _edge_num - 1;
     786    }
     787
     788    static void next(Edge& arc) {
     789      --arc._id;
     790    }
     791
     792    void firstOut(Arc &a, const Node& v) const {
     793      if (v._id < _red_num) {
     794        a._id = 2 * (v._id + _red_num * (_blue_num - 1)) + 1;
     795      } else {
     796        a._id = 2 * (_red_num - 1 + _red_num * (v._id - _red_num));
     797      }
     798    }
     799    void nextOut(Arc &a) const {
     800      if (a._id & 1) {
     801        a._id -= 2 * _red_num;
     802        if (a._id < 0) a._id = -1;
     803      } else {
     804        if (a._id % (2 * _red_num) == 0) a._id = -1;
     805        else a._id -= 2;
     806      }
     807    }
     808
     809    void firstIn(Arc &a, const Node& v) const {
     810      if (v._id < _red_num) {
     811        a._id = 2 * (v._id + _red_num * (_blue_num - 1));
     812      } else {
     813        a._id = 2 * (_red_num - 1 + _red_num * (v._id - _red_num)) + 1;
     814      }
     815    }
     816    void nextIn(Arc &a) const {
     817      if (a._id & 1) {
     818        if (a._id % (2 * _red_num) == 1) a._id = -1;
     819        else a._id -= 2;
     820      } else {
     821        a._id -= 2 * _red_num;
     822        if (a._id < 0) a._id = -1;
     823      }
     824    }
     825
     826    void firstInc(Edge &e, bool& d, const Node& v) const {
     827      if (v._id < _red_num) {
     828        d = true;
     829        e._id = v._id + _red_num * (_blue_num - 1);
     830      } else {
     831        d = false;
     832        e._id = _red_num - 1 + _red_num * (v._id - _red_num);
     833      }
     834    }
     835    void nextInc(Edge &e, bool& d) const {
     836      if (d) {
     837        e._id -= _red_num;
     838        if (e._id < 0) e._id = -1;
     839      } else {
     840        if (e._id % _red_num == 0) e._id = -1;
     841        else --e._id;
     842      }
     843    }
     844
     845    static int id(Node v) { return v._id; }
     846    int redId(Node v) const {
     847      LEMON_DEBUG(v._id < _red_num, "Node has to be red");
     848      return v._id;
     849    }
     850    int blueId(Node v) const {
     851      LEMON_DEBUG(v._id >= _red_num, "Node has to be blue");
     852      return v._id - _red_num;
     853    }
     854    static int id(Arc e) { return e._id; }
     855    static int id(Edge e) { return e._id; }
     856   
     857    static Node nodeFromId(int id) { return Node(id);}
     858    static Arc arcFromId(int id) { return Arc(id);}
     859    static Edge edgeFromId(int id) { return Edge(id);}
     860
     861    bool valid(Node n) const {
     862      return n._id >= 0 && n._id < _node_num;
     863    }
     864    bool valid(Arc a) const {
     865      return a._id >= 0 && a._id < 2 * _edge_num;
     866    }
     867    bool valid(Edge e) const {
     868      return e._id >= 0 && e._id < _edge_num;
     869    }
     870
     871    Node redNode(int index) const {
     872      return Node(index);
     873    }
     874
     875    int redIndex(Node n) const {
     876      return n._id;
     877    }
     878
     879    Node blueNode(int index) const {
     880      return Node(index + _red_num);
     881    }
     882
     883    int blueIndex(Node n) const {
     884      return n._id - _red_num;
     885    }
     886       
     887    void clear() {
     888      _red_num = 0; _blue_num = 0;
     889      _node_num = 0; _edge_num = 0;
     890    }
     891
     892    Edge edge(const Node& u, const Node& v) const {
     893      if (u._id < _red_num) {
     894        if (v._id < _red_num) {
     895          return Edge(-1);
     896        } else {
     897          return Edge(u._id + _red_num * (v._id - _red_num));
     898        }
     899      } else {
     900        if (v._id < _red_num) {
     901          return Edge(v._id + _red_num * (u._id - _red_num));
     902        } else {
     903          return Edge(-1);
     904        }
     905      }
     906    }
     907
     908    Arc arc(const Node& u, const Node& v) const {
     909      if (u._id < _red_num) {
     910        if (v._id < _red_num) {
     911          return Arc(-1);
     912        } else {
     913          return Arc(2 * (u._id + _red_num * (v._id - _red_num)) + 1);
     914        }
     915      } else {
     916        if (v._id < _red_num) {
     917          return Arc(2 * (v._id + _red_num * (u._id - _red_num)));
     918        } else {
     919          return Arc(-1);
     920        }
     921      }
     922    }
     923
     924    typedef True FindEdgeTag;
     925    typedef True FindArcTag;
     926
     927    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
     928      return prev != INVALID ? INVALID : edge(u, v);
     929    }
     930
     931    Arc findArc(Node s, Node t, Arc prev = INVALID) const {
     932      return prev != INVALID ? INVALID : arc(s, t);
     933    }
     934
     935  };
     936
     937  typedef BpGraphExtender<FullBpGraphBase> ExtendedFullBpGraphBase;
     938
     939  /// \ingroup graphs
     940  ///
     941  /// \brief An undirected full bipartite graph class.
     942  ///
     943  /// FullBpGraph is a simple and fast implmenetation of undirected
     944  /// full bipartite graphs. It contains an edge between every
     945  /// red-blue pairs of nodes, therefore the number of edges is
     946  /// <tt>nr*nb</tt>.  This class is completely static and it needs
     947  /// constant memory space.  Thus you can neither add nor delete
     948  /// nodes or edges, however the structure can be resized using
     949  /// resize().
     950  ///
     951  /// This type fully conforms to the \ref concepts::BpGraph "BpGraph concept".
     952  /// Most of its member functions and nested classes are documented
     953  /// only in the concept class.
     954  ///
     955  /// This class provides constant time counting for nodes, edges and arcs.
     956  ///
     957  /// \sa FullGraph
     958  class FullBpGraph : public ExtendedFullBpGraphBase {
     959  public:
     960
     961    typedef ExtendedFullBpGraphBase Parent;
     962
     963    /// \brief Default constructor.
     964    ///
     965    /// Default constructor. The number of nodes and edges will be zero.
     966    FullBpGraph() { construct(0, 0); }
     967
     968    /// \brief Constructor
     969    ///
     970    /// Constructor.
     971    /// \param redNum The number of the red nodes.
     972    /// \param blueNum The number of the blue nodes.
     973    FullBpGraph(int redNum, int blueNum) { construct(redNum, blueNum); }
     974
     975    /// \brief Resizes the graph
     976    ///
     977    /// This function resizes the graph. It fully destroys and
     978    /// rebuilds the structure, therefore the maps of the graph will be
     979    /// reallocated automatically and the previous values will be lost.
     980    void resize(int redNum, int blueNum) {
     981      Parent::notifier(Arc()).clear();
     982      Parent::notifier(Edge()).clear();
     983      Parent::notifier(Node()).clear();
     984      Parent::notifier(BlueNode()).clear();
     985      Parent::notifier(RedNode()).clear();
     986      construct(redNum, blueNum);
     987      Parent::notifier(RedNode()).build();
     988      Parent::notifier(BlueNode()).build();
     989      Parent::notifier(Node()).build();
     990      Parent::notifier(Edge()).build();
     991      Parent::notifier(Arc()).build();
     992    }
     993
     994    /// \brief Returns the red node with the given index.
     995    ///
     996    /// Returns the red node with the given index. Since this
     997    /// structure is completely static, the red nodes can be indexed
     998    /// with integers from the range <tt>[0..redNum()-1]</tt>.
     999    /// \sa redIndex()
     1000    Node redNode(int index) const { return Parent::redNode(index); }
     1001
     1002    /// \brief Returns the index of the given red node.
     1003    ///
     1004    /// Returns the index of the given red node. Since this structure
     1005    /// is completely static, the red nodes can be indexed with
     1006    /// integers from the range <tt>[0..redNum()-1]</tt>.
     1007    ///
     1008    /// \sa operator()()
     1009    int redIndex(Node node) const { return Parent::redIndex(node); }
     1010
     1011    /// \brief Returns the blue node with the given index.
     1012    ///
     1013    /// Returns the blue node with the given index. Since this
     1014    /// structure is completely static, the blue nodes can be indexed
     1015    /// with integers from the range <tt>[0..blueNum()-1]</tt>.
     1016    /// \sa blueIndex()
     1017    Node blueNode(int index) const { return Parent::blueNode(index); }
     1018
     1019    /// \brief Returns the index of the given blue node.
     1020    ///
     1021    /// Returns the index of the given blue node. Since this structure
     1022    /// is completely static, the blue nodes can be indexed with
     1023    /// integers from the range <tt>[0..blueNum()-1]</tt>.
     1024    ///
     1025    /// \sa operator()()
     1026    int blueIndex(Node node) const { return Parent::blueIndex(node); }
     1027
     1028    /// \brief Returns the edge which connects the given nodes.
     1029    ///
     1030    /// Returns the edge which connects the given nodes.
     1031    Edge edge(const Node& u, const Node& v) const {
     1032      return Parent::edge(u, v);
     1033    }
     1034
     1035    /// \brief Returns the arc which connects the given nodes.
     1036    ///
     1037    /// Returns the arc which connects the given nodes.
     1038    Arc arc(const Node& u, const Node& v) const {
     1039      return Parent::arc(u, v);
     1040    }
     1041
     1042    /// \brief Number of nodes.
     1043    int nodeNum() const { return Parent::nodeNum(); }
     1044    /// \brief Number of red nodes.
     1045    int redNum() const { return Parent::redNum(); }
     1046    /// \brief Number of blue nodes.
     1047    int blueNum() const { return Parent::blueNum(); }
     1048    /// \brief Number of arcs.
     1049    int arcNum() const { return Parent::arcNum(); }
     1050    /// \brief Number of edges.
     1051    int edgeNum() const { return Parent::edgeNum(); }
     1052  };
     1053
    6241054
    6251055} //namespace lemon
Note: See TracChangeset for help on using the changeset viewer.