COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/full_graph.h

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