lemon/full_graph.h
changeset 1027 8b2b9e61d8ce
parent 1024 b84e68af8248
child 1092 dceba191c00d
equal deleted inserted replaced
13:9b273825458c 14:3342a5233573
   649       bool operator==(const Node& node) const {return _id == node._id;}
   649       bool operator==(const Node& node) const {return _id == node._id;}
   650       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;}
   651       bool operator<(const Node& node) const {return _id < node._id;}
   652     };
   652     };
   653 
   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 
   654     class Edge {
   678     class Edge {
   655       friend class FullBpGraphBase;
   679       friend class FullBpGraphBase;
   656     protected:
   680     protected:
   657 
   681 
   658       int _id;
   682       int _id;
   715     int maxArcId() const { return 2 * _edge_num - 1; }
   739     int maxArcId() const { return 2 * _edge_num - 1; }
   716 
   740 
   717     bool red(Node n) const { return n._id < _red_num; }
   741     bool red(Node n) const { return n._id < _red_num; }
   718     bool blue(Node n) const { return n._id >= _red_num; }
   742     bool blue(Node n) const { return n._id >= _red_num; }
   719 
   743 
       
   744     static RedNode asRedNodeUnsafe(Node n) { return RedNode(n._id); }
       
   745     static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n._id); }
       
   746 
   720     Node source(Arc a) const {
   747     Node source(Arc a) const {
   721       if (a._id & 1) {
   748       if (a._id & 1) {
   722         return Node((a._id >> 1) % _red_num);
   749         return Node((a._id >> 1) % _red_num);
   723       } else {
   750       } else {
   724         return Node((a._id >> 1) / _red_num + _red_num);
   751         return Node((a._id >> 1) / _red_num + _red_num);
   730       } else {
   757       } else {
   731         return Node((a._id >> 1) % _red_num);
   758         return Node((a._id >> 1) % _red_num);
   732       }
   759       }
   733     }
   760     }
   734 
   761 
   735     Node redNode(Edge e) const {
   762     RedNode redNode(Edge e) const {
   736       return Node(e._id % _red_num);
   763       return RedNode(e._id % _red_num);
   737     }
   764     }
   738     Node blueNode(Edge e) const {
   765     BlueNode blueNode(Edge e) const {
   739       return Node(e._id / _red_num + _red_num);
   766       return BlueNode(e._id / _red_num + _red_num);
   740     }
   767     }
   741 
   768 
   742     static bool direction(Arc a) {
   769     static bool direction(Arc a) {
   743       return (a._id & 1) == 1;
   770       return (a._id & 1) == 1;
   744     }
   771     }
   753 
   780 
   754     static void next(Node& node) {
   781     static void next(Node& node) {
   755       --node._id;
   782       --node._id;
   756     }
   783     }
   757 
   784 
   758     void firstRed(Node& node) const {
   785     void first(RedNode& node) const {
   759       node._id = _red_num - 1;
   786       node._id = _red_num - 1;
   760     }
   787     }
   761 
   788 
   762     static void nextRed(Node& node) {
   789     static void next(RedNode& node) {
   763       --node._id;
   790       --node._id;
   764     }
   791     }
   765 
   792 
   766     void firstBlue(Node& node) const {
   793     void first(BlueNode& node) const {
   767       if (_red_num == _node_num) node._id = -1;
   794       if (_red_num == _node_num) node._id = -1;
   768       else node._id = _node_num - 1;
   795       else node._id = _node_num - 1;
   769     }
   796     }
   770 
   797 
   771     void nextBlue(Node& node) const {
   798     void next(BlueNode& node) const {
   772       if (node._id == _red_num) node._id = -1;
   799       if (node._id == _red_num) node._id = -1;
   773       else --node._id;
   800       else --node._id;
   774     }
   801     }
   775 
   802 
   776     void first(Arc& arc) const {
   803     void first(Arc& arc) const {
   840         if (e._id % _red_num == 0) e._id = -1;
   867         if (e._id % _red_num == 0) e._id = -1;
   841         else --e._id;
   868         else --e._id;
   842       }
   869       }
   843     }
   870     }
   844 
   871 
   845     static int id(Node v) { return v._id; }
   872     static int id(const Node& v) { return v._id; }
   846     int redId(Node v) const {
   873     int id(const RedNode& v) const { return v._id; }
   847       LEMON_DEBUG(v._id < _red_num, "Node has to be red");
   874     int id(const BlueNode& v) const { return v._id - _red_num; }
   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; }
   875     static int id(Arc e) { return e._id; }
   855     static int id(Edge e) { return e._id; }
   876     static int id(Edge e) { return e._id; }
   856     
   877     
   857     static Node nodeFromId(int id) { return Node(id);}
   878     static Node nodeFromId(int id) { return Node(id);}
   858     static Arc arcFromId(int id) { return Arc(id);}
   879     static Arc arcFromId(int id) { return Arc(id);}
   866     }
   887     }
   867     bool valid(Edge e) const {
   888     bool valid(Edge e) const {
   868       return e._id >= 0 && e._id < _edge_num;
   889       return e._id >= 0 && e._id < _edge_num;
   869     }
   890     }
   870 
   891 
   871     Node redNode(int index) const {
   892     RedNode redNode(int index) const {
   872       return Node(index);
   893       return RedNode(index);
   873     }
   894     }
   874 
   895 
   875     int redIndex(Node n) const {
   896     int index(RedNode n) const {
   876       return n._id;
   897       return n._id;
   877     }
   898     }
   878 
   899 
   879     Node blueNode(int index) const {
   900     BlueNode blueNode(int index) const {
   880       return Node(index + _red_num);
   901       return BlueNode(index + _red_num);
   881     }
   902     }
   882 
   903 
   883     int blueIndex(Node n) const {
   904     int index(BlueNode n) const {
   884       return n._id - _red_num;
   905       return n._id - _red_num;
   885     }
   906     }
   886         
   907         
   887     void clear() {
   908     void clear() {
   888       _red_num = 0; _blue_num = 0;
   909       _red_num = 0; _blue_num = 0;
   998     ///
  1019     ///
   999     /// Returns the red node with the given index. Since this
  1020     /// Returns the red node with the given index. Since this
  1000     /// structure is completely static, the red nodes can be indexed
  1021     /// structure is completely static, the red nodes can be indexed
  1001     /// with integers from the range <tt>[0..redNum()-1]</tt>.
  1022     /// with integers from the range <tt>[0..redNum()-1]</tt>.
  1002     /// \sa redIndex()
  1023     /// \sa redIndex()
  1003     Node redNode(int index) const { return Parent::redNode(index); }
  1024     RedNode redNode(int index) const { return Parent::redNode(index); }
  1004 
  1025 
  1005     /// \brief Returns the index of the given red node.
  1026     /// \brief Returns the index of the given red node.
  1006     ///
  1027     ///
  1007     /// Returns the index of the given red node. Since this structure
  1028     /// Returns the index of the given red node. Since this structure
  1008     /// is completely static, the red nodes can be indexed with
  1029     /// is completely static, the red nodes can be indexed with
  1009     /// integers from the range <tt>[0..redNum()-1]</tt>.
  1030     /// integers from the range <tt>[0..redNum()-1]</tt>.
  1010     ///
  1031     ///
  1011     /// \sa operator()()
  1032     /// \sa operator()()
  1012     int redIndex(Node node) const { return Parent::redIndex(node); }
  1033     int index(RedNode node) const { return Parent::index(node); }
  1013 
  1034 
  1014     /// \brief Returns the blue node with the given index.
  1035     /// \brief Returns the blue node with the given index.
  1015     ///
  1036     ///
  1016     /// Returns the blue node with the given index. Since this
  1037     /// Returns the blue node with the given index. Since this
  1017     /// structure is completely static, the blue nodes can be indexed
  1038     /// structure is completely static, the blue nodes can be indexed
  1018     /// with integers from the range <tt>[0..blueNum()-1]</tt>.
  1039     /// with integers from the range <tt>[0..blueNum()-1]</tt>.
  1019     /// \sa blueIndex()
  1040     /// \sa blueIndex()
  1020     Node blueNode(int index) const { return Parent::blueNode(index); }
  1041     BlueNode blueNode(int index) const { return Parent::blueNode(index); }
  1021 
  1042 
  1022     /// \brief Returns the index of the given blue node.
  1043     /// \brief Returns the index of the given blue node.
  1023     ///
  1044     ///
  1024     /// Returns the index of the given blue node. Since this structure
  1045     /// Returns the index of the given blue node. Since this structure
  1025     /// is completely static, the blue nodes can be indexed with
  1046     /// is completely static, the blue nodes can be indexed with
  1026     /// integers from the range <tt>[0..blueNum()-1]</tt>.
  1047     /// integers from the range <tt>[0..blueNum()-1]</tt>.
  1027     ///
  1048     ///
  1028     /// \sa operator()()
  1049     /// \sa operator()()
  1029     int blueIndex(Node node) const { return Parent::blueIndex(node); }
  1050     int index(BlueNode node) const { return Parent::index(node); }
  1030 
  1051 
  1031     /// \brief Returns the edge which connects the given nodes.
  1052     /// \brief Returns the edge which connects the given nodes.
  1032     ///
  1053     ///
  1033     /// Returns the edge which connects the given nodes.
  1054     /// Returns the edge which connects the given nodes.
  1034     Edge edge(const Node& u, const Node& v) const {
  1055     Edge edge(const Node& u, const Node& v) const {