lemon/smart_graph.h
changeset 1057 6a8a688eacf6
parent 1023 939ee6d1e525
child 1092 dceba191c00d
equal deleted inserted replaced
31:b0ea68f9a6e1 32:3b6db54947d4
   852       bool operator==(const Node& node) const {return _id == node._id;}
   852       bool operator==(const Node& node) const {return _id == node._id;}
   853       bool operator!=(const Node& node) const {return _id != node._id;}
   853       bool operator!=(const Node& node) const {return _id != node._id;}
   854       bool operator<(const Node& node) const {return _id < node._id;}
   854       bool operator<(const Node& node) const {return _id < node._id;}
   855     };
   855     };
   856 
   856 
       
   857     class RedNode : public Node {
       
   858       friend class SmartBpGraphBase;
       
   859     protected:
       
   860 
       
   861       explicit RedNode(int pid) : Node(pid) {}
       
   862 
       
   863     public:
       
   864       RedNode() {}
       
   865       RedNode(const RedNode& node) : Node(node) {}
       
   866       RedNode(Invalid) : Node(INVALID){}
       
   867     };
       
   868 
       
   869     class BlueNode : public Node {
       
   870       friend class SmartBpGraphBase;
       
   871     protected:
       
   872 
       
   873       explicit BlueNode(int pid) : Node(pid) {}
       
   874 
       
   875     public:
       
   876       BlueNode() {}
       
   877       BlueNode(const BlueNode& node) : Node(node) {}
       
   878       BlueNode(Invalid) : Node(INVALID){}
       
   879     };
       
   880 
   857     class Edge {
   881     class Edge {
   858       friend class SmartBpGraphBase;
   882       friend class SmartBpGraphBase;
   859     protected:
   883     protected:
   860 
   884 
   861       int _id;
   885       int _id;
   911     int maxArcId() const { return arcs.size()-1; }
   935     int maxArcId() const { return arcs.size()-1; }
   912 
   936 
   913     bool red(Node n) const { return nodes[n._id].red; }
   937     bool red(Node n) const { return nodes[n._id].red; }
   914     bool blue(Node n) const { return !nodes[n._id].red; }
   938     bool blue(Node n) const { return !nodes[n._id].red; }
   915 
   939 
       
   940     static RedNode asRedNodeUnsafe(Node n) { return RedNode(n._id); }
       
   941     static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n._id); }
       
   942 
   916     Node source(Arc a) const { return Node(arcs[a._id ^ 1].target); }
   943     Node source(Arc a) const { return Node(arcs[a._id ^ 1].target); }
   917     Node target(Arc a) const { return Node(arcs[a._id].target); }
   944     Node target(Arc a) const { return Node(arcs[a._id].target); }
   918 
   945 
   919     Node redNode(Edge e) const { return Node(arcs[2 * e._id].target); }
   946     RedNode redNode(Edge e) const {
   920     Node blueNode(Edge e) const { return Node(arcs[2 * e._id + 1].target); }
   947       return RedNode(arcs[2 * e._id].target);
       
   948     }
       
   949     BlueNode blueNode(Edge e) const {
       
   950       return BlueNode(arcs[2 * e._id + 1].target);
       
   951     }
   921 
   952 
   922     static bool direction(Arc a) {
   953     static bool direction(Arc a) {
   923       return (a._id & 1) == 1;
   954       return (a._id & 1) == 1;
   924     }
   955     }
   925 
   956 
   933 
   964 
   934     static void next(Node& node) {
   965     static void next(Node& node) {
   935       --node._id;
   966       --node._id;
   936     }
   967     }
   937 
   968 
   938     void firstRed(Node& node) const {
   969     void first(RedNode& node) const {
   939       node._id = first_red;
   970       node._id = first_red;
   940     }
   971     }
   941 
   972 
   942     void nextRed(Node& node) const {
   973     void next(RedNode& node) const {
   943       node._id = nodes[node._id].partition_next;
   974       node._id = nodes[node._id].partition_next;
   944     }
   975     }
   945 
   976 
   946     void firstBlue(Node& node) const {
   977     void first(BlueNode& node) const {
   947       node._id = first_blue;
   978       node._id = first_blue;
   948     }
   979     }
   949 
   980 
   950     void nextBlue(Node& node) const {
   981     void next(BlueNode& node) const {
   951       node._id = nodes[node._id].partition_next;
   982       node._id = nodes[node._id].partition_next;
   952     }
   983     }
   953 
   984 
   954     void first(Arc& arc) const {
   985     void first(Arc& arc) const {
   955       arc._id = arcs.size() - 1;
   986       arc._id = arcs.size() - 1;
  1003         d = true;
  1034         d = true;
  1004       }
  1035       }
  1005     }
  1036     }
  1006 
  1037 
  1007     static int id(Node v) { return v._id; }
  1038     static int id(Node v) { return v._id; }
  1008     int redId(Node v) const {
  1039     int id(RedNode v) const { return nodes[v._id].partition_index; }
  1009       LEMON_DEBUG(nodes[v._id].red, "Node has to be red");
  1040     int id(BlueNode v) const { return nodes[v._id].partition_index; }
  1010       return nodes[v._id].partition_index;
       
  1011     }
       
  1012     int blueId(Node v) const {
       
  1013       LEMON_DEBUG(!nodes[v._id].red, "Node has to be blue");
       
  1014       return nodes[v._id].partition_index;
       
  1015     }
       
  1016     static int id(Arc e) { return e._id; }
  1041     static int id(Arc e) { return e._id; }
  1017     static int id(Edge e) { return e._id; }
  1042     static int id(Edge e) { return e._id; }
  1018 
  1043 
  1019     static Node nodeFromId(int id) { return Node(id);}
  1044     static Node nodeFromId(int id) { return Node(id);}
  1020     static Arc arcFromId(int id) { return Arc(id);}
  1045     static Arc arcFromId(int id) { return Arc(id);}
  1028     }
  1053     }
  1029     bool valid(Edge e) const {
  1054     bool valid(Edge e) const {
  1030       return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
  1055       return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
  1031     }
  1056     }
  1032 
  1057 
  1033     Node addRedNode() {
  1058     RedNode addRedNode() {
  1034       int n = nodes.size();
  1059       int n = nodes.size();
  1035       nodes.push_back(NodeT());
  1060       nodes.push_back(NodeT());
  1036       nodes[n].first_out = -1;
  1061       nodes[n].first_out = -1;
  1037       nodes[n].red = true;
  1062       nodes[n].red = true;
  1038       nodes[n].partition_index = ++max_red;
  1063       nodes[n].partition_index = ++max_red;
  1039       nodes[n].partition_next = first_red;
  1064       nodes[n].partition_next = first_red;
  1040       first_red = n;
  1065       first_red = n;
  1041 
  1066 
  1042       return Node(n);
  1067       return RedNode(n);
  1043     }
  1068     }
  1044 
  1069 
  1045     Node addBlueNode() {
  1070     BlueNode addBlueNode() {
  1046       int n = nodes.size();
  1071       int n = nodes.size();
  1047       nodes.push_back(NodeT());
  1072       nodes.push_back(NodeT());
  1048       nodes[n].first_out = -1;
  1073       nodes[n].first_out = -1;
  1049       nodes[n].red = false;
  1074       nodes[n].red = false;
  1050       nodes[n].partition_index = ++max_blue;
  1075       nodes[n].partition_index = ++max_blue;
  1051       nodes[n].partition_next = first_blue;
  1076       nodes[n].partition_next = first_blue;
  1052       first_blue = n;
  1077       first_blue = n;
  1053 
  1078 
  1054       return Node(n);
  1079       return BlueNode(n);
  1055     }
  1080     }
  1056 
  1081 
  1057     Edge addEdge(Node u, Node v) {
  1082     Edge addEdge(RedNode u, BlueNode v) {
  1058       int n = arcs.size();
  1083       int n = arcs.size();
  1059       arcs.push_back(ArcT());
  1084       arcs.push_back(ArcT());
  1060       arcs.push_back(ArcT());
  1085       arcs.push_back(ArcT());
  1061 
  1086 
  1062       arcs[n].target = u._id;
  1087       arcs[n].target = u._id;
  1122 
  1147 
  1123     /// \brief Add a new red node to the graph.
  1148     /// \brief Add a new red node to the graph.
  1124     ///
  1149     ///
  1125     /// This function adds a red new node to the graph.
  1150     /// This function adds a red new node to the graph.
  1126     /// \return The new node.
  1151     /// \return The new node.
  1127     Node addRedNode() { return Parent::addRedNode(); }
  1152     RedNode addRedNode() { return Parent::addRedNode(); }
  1128 
  1153 
  1129     /// \brief Add a new blue node to the graph.
  1154     /// \brief Add a new blue node to the graph.
  1130     ///
  1155     ///
  1131     /// This function adds a blue new node to the graph.
  1156     /// This function adds a blue new node to the graph.
  1132     /// \return The new node.
  1157     /// \return The new node.
  1133     Node addBlueNode() { return Parent::addBlueNode(); }
  1158     BlueNode addBlueNode() { return Parent::addBlueNode(); }
  1134 
  1159 
  1135     /// \brief Add a new edge to the graph.
  1160     /// \brief Add a new edge to the graph.
  1136     ///
  1161     ///
  1137     /// This function adds a new edge to the graph between nodes
  1162     /// This function adds a new edge to the graph between nodes
  1138     /// \c u and \c v with inherent orientation from node \c u to
  1163     /// \c u and \c v with inherent orientation from node \c u to
  1139     /// node \c v.
  1164     /// node \c v.
  1140     /// \return The new edge.
  1165     /// \return The new edge.
  1141     Edge addEdge(Node red, Node blue) {
  1166     Edge addEdge(RedNode u, BlueNode v) {
  1142       LEMON_DEBUG(Parent::red(red) && Parent::blue(blue),
  1167       return Parent::addEdge(u, v);
  1143                   "Edge has to be formed by a red and a blue nodes");
  1168     }
  1144       return Parent::addEdge(red, blue);
  1169     Edge addEdge(BlueNode v, RedNode u) {
       
  1170       return Parent::addEdge(u, v);
  1145     }
  1171     }
  1146 
  1172 
  1147     /// \brief Node validity check
  1173     /// \brief Node validity check
  1148     ///
  1174     ///
  1149     /// This function gives back \c true if the given node is valid,
  1175     /// This function gives back \c true if the given node is valid,
  1235           if (first_red != -1) {
  1261           if (first_red != -1) {
  1236             max_red = nodes[first_red].partition_index;
  1262             max_red = nodes[first_red].partition_index;
  1237           } else {
  1263           } else {
  1238             max_red = -1;
  1264             max_red = -1;
  1239           }
  1265           }
  1240           Parent::notifier(RedNode()).erase(node);          
  1266           Parent::notifier(RedNode()).erase(asRedNodeUnsafe(node));          
  1241         } else {
  1267         } else {
  1242           first_blue = nodes[n].partition_next;
  1268           first_blue = nodes[n].partition_next;
  1243           if (first_blue != -1) {
  1269           if (first_blue != -1) {
  1244             max_blue = nodes[first_blue].partition_index;
  1270             max_blue = nodes[first_blue].partition_index;
  1245           } else {
  1271           } else {
  1246             max_blue = -1;
  1272             max_blue = -1;
  1247           }
  1273           }
  1248           Parent::notifier(BlueNode()).erase(node);
  1274           Parent::notifier(BlueNode()).erase(asBlueNodeUnsafe(node));
  1249         }
  1275         }
  1250         Parent::notifier(Node()).erase(node);
  1276         Parent::notifier(Node()).erase(node);
  1251         nodes.pop_back();
  1277         nodes.pop_back();
  1252       }
  1278       }
  1253     }
  1279     }