931 this->next(f); |
931 this->next(f); |
932 first_out_edges->set(this->tail(e), f.e); |
932 first_out_edges->set(this->tail(e), f.e); |
933 } |
933 } |
934 }; |
934 }; |
935 |
935 |
936 /// A wrapper for composing a bipartite graph. |
|
937 /// \c _graph have to be a reference to a graph of type \c Graph |
|
938 /// and \c _s_false_t_true_map is an \c IterableBoolMap |
|
939 /// reference containing the elements for the |
|
940 /// color classes S and T. \c _graph is to be referred to an undirected |
|
941 /// graph or a directed graph with edges oriented from S to T. |
|
942 /// |
|
943 ///\author Marton Makai |
|
944 template<typename Graph> |
|
945 class BipartiteGraphWrapper : public GraphWrapper<Graph> { |
|
946 typedef IterableBoolMap< typename Graph::template NodeMap<int> > |
|
947 SFalseTTrueMap; |
|
948 SFalseTTrueMap* s_false_t_true_map; |
|
949 |
|
950 public: |
|
951 //marci |
|
952 //FIXME vhogy igy kellene, csak az en forditom nem eszi meg |
|
953 //static const bool S_CLASS=false; |
|
954 //static const bool T_CLASS=true; |
|
955 |
|
956 bool S_CLASS; |
|
957 bool T_CLASS; |
|
958 |
|
959 BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map) |
|
960 : GraphWrapper<Graph>(_graph), s_false_t_true_map(&_s_false_t_true_map), |
|
961 S_CLASS(false), T_CLASS(true) { } |
|
962 typedef typename GraphWrapper<Graph>::Node Node; |
|
963 //using GraphWrapper<Graph>::NodeIt; |
|
964 typedef typename GraphWrapper<Graph>::Edge Edge; |
|
965 //using GraphWrapper<Graph>::EdgeIt; |
|
966 class ClassNodeIt; |
|
967 friend class ClassNodeIt; |
|
968 class OutEdgeIt; |
|
969 friend class OutEdgeIt; |
|
970 class InEdgeIt; |
|
971 friend class InEdgeIt; |
|
972 class ClassNodeIt { |
|
973 friend class BipartiteGraphWrapper<Graph>; |
|
974 protected: |
|
975 Node n; |
|
976 public: |
|
977 ClassNodeIt() { } |
|
978 ClassNodeIt(const Invalid& i) : n(i) { } |
|
979 ClassNodeIt(const BipartiteGraphWrapper<Graph>& _G, bool _class) { |
|
980 _G.s_false_t_true_map->first(n, _class); |
|
981 } |
|
982 //FIXME needed in new concept, important here |
|
983 ClassNodeIt(const Node& _n) : n(_n) { } |
|
984 operator Node() const { return n; } |
|
985 }; |
|
986 // class SNodeIt { |
|
987 // Node n; |
|
988 // public: |
|
989 // SNodeIt() { } |
|
990 // SNodeIt(const Invalid& i) : n(i) { } |
|
991 // SNodeIt(const BipartiteGraphWrapper<Graph>& _G) { |
|
992 // _G.s_false_t_true_map->first(n, false); |
|
993 // } |
|
994 // operator Node() const { return n; } |
|
995 // }; |
|
996 // class TNodeIt { |
|
997 // Node n; |
|
998 // public: |
|
999 // TNodeIt() { } |
|
1000 // TNodeIt(const Invalid& i) : n(i) { } |
|
1001 // TNodeIt(const BipartiteGraphWrapper<Graph>& _G) { |
|
1002 // _G.s_false_t_true_map->first(n, true); |
|
1003 // } |
|
1004 // operator Node() const { return n; } |
|
1005 // }; |
|
1006 class OutEdgeIt { |
|
1007 friend class BipartiteGraphWrapper<Graph>; |
|
1008 protected: |
|
1009 typename Graph::OutEdgeIt e; |
|
1010 public: |
|
1011 OutEdgeIt() { } |
|
1012 OutEdgeIt(const Invalid& i) : e(i) { } |
|
1013 OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) { |
|
1014 if (!(*(_G.s_false_t_true_map))[_n]) |
|
1015 e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n)); |
|
1016 else |
|
1017 e=INVALID; |
|
1018 } |
|
1019 operator Edge() const { return Edge(typename Graph::Edge(e)); } |
|
1020 }; |
|
1021 class InEdgeIt { |
|
1022 friend class BipartiteGraphWrapper<Graph>; |
|
1023 protected: |
|
1024 typename Graph::InEdgeIt e; |
|
1025 public: |
|
1026 InEdgeIt() { } |
|
1027 InEdgeIt(const Invalid& i) : e(i) { } |
|
1028 InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) { |
|
1029 if ((*(_G.s_false_t_true_map))[_n]) |
|
1030 e=typename Graph::InEdgeIt(*(_G.graph), typename Graph::Node(_n)); |
|
1031 else |
|
1032 e=INVALID; |
|
1033 } |
|
1034 operator Edge() const { return Edge(typename Graph::Edge(e)); } |
|
1035 }; |
|
1036 |
|
1037 using GraphWrapper<Graph>::first; |
|
1038 ClassNodeIt& first(ClassNodeIt& n, bool _class) const { |
|
1039 n=ClassNodeIt(*this, _class) ; return n; } |
|
1040 // SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; } |
|
1041 // TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; } |
|
1042 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
|
1043 i=OutEdgeIt(*this, p); return i; |
|
1044 } |
|
1045 InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
|
1046 i=InEdgeIt(*this, p); return i; |
|
1047 } |
|
1048 |
|
1049 using GraphWrapper<Graph>::next; |
|
1050 ClassNodeIt& next(ClassNodeIt& n) const { |
|
1051 this->s_false_t_true_map->next(n.n); return n; |
|
1052 } |
|
1053 // SNodeIt& next(SNodeIt& n) const { |
|
1054 // this->s_false_t_true_map->next(n); return n; |
|
1055 // } |
|
1056 // TNodeIt& next(TNodeIt& n) const { |
|
1057 // this->s_false_t_true_map->next(n); return n; |
|
1058 // } |
|
1059 OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; } |
|
1060 InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; } |
|
1061 |
|
1062 Node tail(const Edge& e) { |
|
1063 if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) |
|
1064 return Node(this->graph->tail(e)); |
|
1065 else |
|
1066 return Node(this->graph->head(e)); |
|
1067 } |
|
1068 Node head(const Edge& e) { |
|
1069 if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) |
|
1070 return Node(this->graph->head(e)); |
|
1071 else |
|
1072 return Node(this->graph->tail(e)); |
|
1073 } |
|
1074 |
|
1075 Node aNode(const OutEdgeIt& e) const { |
|
1076 return Node(this->graph->aNode(e.e)); |
|
1077 } |
|
1078 Node aNode(const InEdgeIt& e) const { |
|
1079 return Node(this->graph->aNode(e.e)); |
|
1080 } |
|
1081 Node bNode(const OutEdgeIt& e) const { |
|
1082 return Node(this->graph->bNode(e.e)); |
|
1083 } |
|
1084 Node bNode(const InEdgeIt& e) const { |
|
1085 return Node(this->graph->bNode(e.e)); |
|
1086 } |
|
1087 |
|
1088 bool inSClass(const Node& n) const { |
|
1089 return !(*(this->s_false_t_true_map))[n]; |
|
1090 } |
|
1091 bool inTClass(const Node& n) const { |
|
1092 return (*(this->s_false_t_true_map))[n]; |
|
1093 } |
|
1094 }; |
|
1095 |
|
1096 template<typename Graph> |
|
1097 class stGraphWrapper; |
|
1098 |
|
1099 // template<typename Graph> |
|
1100 // std::ostream& |
|
1101 // operator<<(std::ostream& os, const typename stGraphWrapper<Graph>::Node& i) { |
|
1102 // os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")"; |
|
1103 // return os; |
|
1104 // } |
|
1105 // template<typename Graph> |
|
1106 // std::ostream& |
|
1107 // operator<<(std::ostream& os, const typename stGraphWrapper<Graph>::Edge& i) { |
|
1108 // os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec << |
|
1109 // " node: " << i.n << ")"; |
|
1110 // return os; |
|
1111 // } |
|
1112 |
|
1113 /// experimentral, do not try it. |
|
1114 /// It eats a bipartite graph, oriented from S to T. |
|
1115 /// Such one can be made e.g. by the above wrapper. |
|
1116 /// |
|
1117 ///\author Marton Makai |
|
1118 template<typename Graph> |
|
1119 class stGraphWrapper : public GraphWrapper<Graph> { |
|
1120 public: |
|
1121 class Node; |
|
1122 friend class Node; |
|
1123 //GN, int |
|
1124 //0 normalis, 1 s, 2, true, ez az iteralasi sorrend, |
|
1125 //es a vege a false azaz (invalid, 3) |
|
1126 class NodeIt; |
|
1127 friend class NodeIt; |
|
1128 //GNI, int |
|
1129 class Edge; |
|
1130 friend class Edge; |
|
1131 //GE, int, GN |
|
1132 //0 normalis, 1 s->vmi, 2 vmi->t, ez a sorrend, |
|
1133 //invalid: (invalid, 3, invalid) |
|
1134 class OutEdgeIt; |
|
1135 friend class OutEdgeIt; |
|
1136 //GO, int, GNI |
|
1137 //normalis pontbol (first, 0, invalid), ..., (invalid, 2, vmi), ... (invalid, 3, invalid) |
|
1138 //s-bol (invalid, 1, first), ... (invalid, 3, invalid) |
|
1139 //t-bol (invalid, 3, invalid) |
|
1140 class InEdgeIt; |
|
1141 friend class InEdgeIt; |
|
1142 //GI, int, GNI |
|
1143 //normalis pontbol (first, 0, invalid), ..., (invalid, 1, vmi), ... (invalid, 3, invalid) |
|
1144 //s-be (invalid, 3, invalid) |
|
1145 //t-be (invalid, 2, first), ... (invalid, 3, invalid) |
|
1146 class EdgeIt; |
|
1147 friend class EdgeIt; |
|
1148 //(first, 0, invalid) ... |
|
1149 //(invalid, 1, vmi) |
|
1150 //(invalid, 2, vmi) |
|
1151 //invalid, 3, invalid) |
|
1152 template <typename T> class NodeMap; |
|
1153 template <typename T, typename Parent> class EdgeMap; |
|
1154 |
|
1155 // template <typename T> friend class NodeMap; |
|
1156 // template <typename T> friend class EdgeMap; |
|
1157 |
|
1158 const Node S_NODE; |
|
1159 const Node T_NODE; |
|
1160 |
|
1161 static const bool S_CLASS=false; |
|
1162 static const bool T_CLASS=true; |
|
1163 |
|
1164 stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) , |
|
1165 S_NODE(INVALID, 1), |
|
1166 T_NODE(INVALID, 2) { } |
|
1167 |
|
1168 |
|
1169 // std::ostream& |
|
1170 // operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i); |
|
1171 // friend std::ostream& |
|
1172 // operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i); |
|
1173 // friend std::ostream& |
|
1174 // operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Edge& i); |
|
1175 |
|
1176 class Node : public Graph::Node { |
|
1177 protected: |
|
1178 friend class GraphWrapper<Graph>; |
|
1179 friend class stGraphWrapper<Graph>; |
|
1180 template <typename T> friend class NodeMap; |
|
1181 friend class Edge; |
|
1182 friend class OutEdgeIt; |
|
1183 friend class InEdgeIt; |
|
1184 friend class EdgeIt; |
|
1185 int spec; |
|
1186 public: |
|
1187 Node() { } |
|
1188 Node(const typename Graph::Node& _n, int _spec=0) : |
|
1189 Graph::Node(_n), spec(_spec) { } |
|
1190 Node(const Invalid& i) : Graph::Node(i), spec(3) { } |
|
1191 friend bool operator==(const Node& u, const Node& v) { |
|
1192 return (u.spec==v.spec && |
|
1193 static_cast<typename Graph::Node>(u)== |
|
1194 static_cast<typename Graph::Node>(v)); |
|
1195 } |
|
1196 friend bool operator!=(const Node& u, const Node& v) { |
|
1197 return (v.spec!=u.spec || |
|
1198 static_cast<typename Graph::Node>(u)!= |
|
1199 static_cast<typename Graph::Node>(v)); |
|
1200 } |
|
1201 // template<typename G> |
|
1202 // friend std::ostream& |
|
1203 // operator<<(std::ostream& os, const typename stGraphWrapper<G>::Node& i); |
|
1204 friend std::ostream& operator<< (std::ostream& os, const Node& i); |
|
1205 int getSpec() const { return spec; } |
|
1206 }; |
|
1207 |
|
1208 class NodeIt { |
|
1209 friend class GraphWrapper<Graph>; |
|
1210 friend class stGraphWrapper<Graph>; |
|
1211 typename Graph::NodeIt n; |
|
1212 int spec; |
|
1213 public: |
|
1214 NodeIt() { } |
|
1215 NodeIt(const typename Graph::NodeIt& _n, int _spec) : |
|
1216 n(_n), spec(_spec) { } |
|
1217 NodeIt(const Invalid& i) : n(i), spec(3) { } |
|
1218 NodeIt(const stGraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) { |
|
1219 if (!_G.graph->valid(n)) spec=1; |
|
1220 } |
|
1221 operator Node() const { return Node(n, spec); } |
|
1222 }; |
|
1223 |
|
1224 class Edge : public Graph::Edge { |
|
1225 friend class GraphWrapper<Graph>; |
|
1226 friend class stGraphWrapper<Graph>; |
|
1227 template <typename T, typename Parent> friend class EdgeMap; |
|
1228 int spec; |
|
1229 typename Graph::Node n; |
|
1230 public: |
|
1231 Edge() { } |
|
1232 Edge(const typename Graph::Edge& _e, int _spec, |
|
1233 const typename Graph::Node& _n) : |
|
1234 Graph::Edge(_e), spec(_spec), n(_n) { |
|
1235 } |
|
1236 Edge(const Invalid& i) : Graph::Edge(i), spec(3), n(i) { } |
|
1237 friend bool operator==(const Edge& u, const Edge& v) { |
|
1238 return (u.spec==v.spec && |
|
1239 static_cast<typename Graph::Edge>(u)== |
|
1240 static_cast<typename Graph::Edge>(v) && |
|
1241 u.n==v.n); |
|
1242 } |
|
1243 friend bool operator!=(const Edge& u, const Edge& v) { |
|
1244 return (v.spec!=u.spec || |
|
1245 static_cast<typename Graph::Edge>(u)!= |
|
1246 static_cast<typename Graph::Edge>(v) || |
|
1247 u.n!=v.n); |
|
1248 } |
|
1249 // template<typename G> |
|
1250 // friend std::ostream& |
|
1251 // operator<<(std::ostream& os, const typename stGraphWrapper<G>::Edge& i); |
|
1252 friend std::ostream& operator<< (std::ostream& os, const Edge& i); |
|
1253 int getSpec() const { return spec; } |
|
1254 }; |
|
1255 |
|
1256 class OutEdgeIt { |
|
1257 friend class GraphWrapper<Graph>; |
|
1258 friend class stGraphWrapper<Graph>; |
|
1259 typename Graph::OutEdgeIt e; |
|
1260 int spec; |
|
1261 typename Graph::ClassNodeIt n; |
|
1262 public: |
|
1263 OutEdgeIt() { } |
|
1264 OutEdgeIt(const typename Graph::OutEdgeIt& _e, int _spec, |
|
1265 const typename Graph::ClassNodeIt& _n) : |
|
1266 e(_e), spec(_spec), n(_n) { |
|
1267 } |
|
1268 OutEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { } |
|
1269 OutEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) { |
|
1270 switch (_n.spec) { |
|
1271 case 0 : |
|
1272 if (_G.graph->inSClass(_n)) { //S, van normalis kiel |
|
1273 e=typename Graph::OutEdgeIt(*(_G.graph), |
|
1274 typename Graph::Node(_n)); |
|
1275 spec=0; |
|
1276 n=INVALID; |
|
1277 if (!_G.graph->valid(e)) spec=3; |
|
1278 } else { //T, specko kiel van |
|
1279 e=INVALID; |
|
1280 spec=2; |
|
1281 n=_n; |
|
1282 } |
|
1283 break; |
|
1284 case 1: |
|
1285 e=INVALID; |
|
1286 spec=1; |
|
1287 _G.graph->first(n, S_CLASS); //s->vmi; |
|
1288 if (!_G.graph->valid(n)) spec=3; //Ha S ures |
|
1289 break; |
|
1290 case 2: |
|
1291 e=INVALID; |
|
1292 spec=3; |
|
1293 n=INVALID; |
|
1294 break; |
|
1295 } |
|
1296 } |
|
1297 operator Edge() const { return Edge(e, spec, n); } |
|
1298 }; |
|
1299 |
|
1300 class InEdgeIt { |
|
1301 friend class GraphWrapper<Graph>; |
|
1302 friend class stGraphWrapper<Graph>; |
|
1303 typename Graph::InEdgeIt e; |
|
1304 int spec; |
|
1305 typename Graph::ClassNodeIt n; |
|
1306 public: |
|
1307 InEdgeIt() { } |
|
1308 InEdgeIt(const typename Graph::InEdgeIt& _e, int _spec, |
|
1309 const typename Graph::ClassNodeIt& _n) : |
|
1310 e(_e), spec(_spec), n(_n) { |
|
1311 } |
|
1312 InEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { } |
|
1313 InEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) { |
|
1314 switch (_n.spec) { |
|
1315 case 0 : |
|
1316 if (_G.graph->inTClass(_n)) { //T, van normalis beel |
|
1317 e=typename Graph::InEdgeIt(*(_G.graph), |
|
1318 typename Graph::Node(_n)); |
|
1319 spec=0; |
|
1320 n=INVALID; |
|
1321 if (!_G.graph->valid(e)) spec=3; |
|
1322 } else { //S, specko beel van |
|
1323 e=INVALID; |
|
1324 spec=1; |
|
1325 n=_n; |
|
1326 } |
|
1327 break; |
|
1328 case 1: |
|
1329 e=INVALID; |
|
1330 spec=3; |
|
1331 n=INVALID; |
|
1332 break; |
|
1333 case 2: |
|
1334 e=INVALID; |
|
1335 spec=2; |
|
1336 _G.graph->first(n, T_CLASS); //vmi->t; |
|
1337 if (!_G.graph->valid(n)) spec=3; //Ha T ures |
|
1338 break; |
|
1339 } |
|
1340 } |
|
1341 operator Edge() const { return Edge(e, spec, n); } |
|
1342 }; |
|
1343 |
|
1344 class EdgeIt { |
|
1345 friend class GraphWrapper<Graph>; |
|
1346 friend class stGraphWrapper<Graph>; |
|
1347 typename Graph::EdgeIt e; |
|
1348 int spec; |
|
1349 typename Graph::ClassNodeIt n; |
|
1350 public: |
|
1351 EdgeIt() { } |
|
1352 EdgeIt(const typename Graph::EdgeIt& _e, int _spec, |
|
1353 const typename Graph::ClassNodeIt& _n) : |
|
1354 e(_e), spec(_spec), n(_n) { } |
|
1355 EdgeIt(const Invalid& i) : e(i), spec(3), n(i) { } |
|
1356 EdgeIt(const stGraphWrapper<Graph>& _G) : |
|
1357 e(*(_G.graph)), spec(0), n(INVALID) { |
|
1358 if (!_G.graph->valid(e)) { |
|
1359 spec=1; |
|
1360 _G.graph->first(n, S_CLASS); |
|
1361 if (!_G.graph->valid(n)) { //Ha S ures |
|
1362 spec=2; |
|
1363 _G.graph->first(n, T_CLASS); |
|
1364 if (!_G.graph->valid(n)) { //Ha T ures |
|
1365 spec=3; |
|
1366 } |
|
1367 } |
|
1368 } |
|
1369 } |
|
1370 operator Edge() const { return Edge(e, spec, n); } |
|
1371 }; |
|
1372 |
|
1373 NodeIt& first(NodeIt& i) const { |
|
1374 i=NodeIt(*this); return i; |
|
1375 } |
|
1376 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
|
1377 i=OutEdgeIt(*this, p); return i; |
|
1378 } |
|
1379 InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
|
1380 i=InEdgeIt(*this, p); return i; |
|
1381 } |
|
1382 EdgeIt& first(EdgeIt& i) const { |
|
1383 i=EdgeIt(*this); return i; |
|
1384 } |
|
1385 |
|
1386 NodeIt& next(NodeIt& i) const { |
|
1387 switch (i.spec) { |
|
1388 case 0: |
|
1389 this->graph->next(i.n); |
|
1390 if (!this->graph->valid(i.n)) { |
|
1391 i.spec=1; |
|
1392 } |
|
1393 break; |
|
1394 case 1: |
|
1395 i.spec=2; |
|
1396 break; |
|
1397 case 2: |
|
1398 i.spec=3; |
|
1399 break; |
|
1400 } |
|
1401 return i; |
|
1402 } |
|
1403 OutEdgeIt& next(OutEdgeIt& i) const { |
|
1404 typename Graph::Node v; |
|
1405 switch (i.spec) { |
|
1406 case 0: //normal edge |
|
1407 v=this->graph->aNode(i.e); |
|
1408 this->graph->next(i.e); |
|
1409 if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk |
|
1410 if (this->graph->inSClass(v)) { //S, nincs kiel |
|
1411 i.spec=3; |
|
1412 i.n=INVALID; |
|
1413 } else { //T, van kiel |
|
1414 i.spec=2; |
|
1415 i.n=v; |
|
1416 } |
|
1417 } |
|
1418 break; |
|
1419 case 1: //s->vmi |
|
1420 this->graph->next(i.n); |
|
1421 if (!this->graph->valid(i.n)) i.spec=3; |
|
1422 break; |
|
1423 case 2: //vmi->t |
|
1424 i.spec=3; |
|
1425 i.n=INVALID; |
|
1426 break; |
|
1427 } |
|
1428 return i; |
|
1429 } |
|
1430 InEdgeIt& next(InEdgeIt& i) const { |
|
1431 typename Graph::Node v; |
|
1432 switch (i.spec) { |
|
1433 case 0: //normal edge |
|
1434 v=this->graph->aNode(i.e); |
|
1435 this->graph->next(i.e); |
|
1436 if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk |
|
1437 if (this->graph->inTClass(v)) { //S, nincs beel |
|
1438 i.spec=3; |
|
1439 i.n=INVALID; |
|
1440 } else { //S, van beel |
|
1441 i.spec=1; |
|
1442 i.n=v; |
|
1443 } |
|
1444 } |
|
1445 break; |
|
1446 case 1: //s->vmi |
|
1447 i.spec=3; |
|
1448 i.n=INVALID; |
|
1449 break; |
|
1450 case 2: //vmi->t |
|
1451 this->graph->next(i.n); |
|
1452 if (!this->graph->valid(i.n)) i.spec=3; |
|
1453 break; |
|
1454 } |
|
1455 return i; |
|
1456 } |
|
1457 |
|
1458 EdgeIt& next(EdgeIt& i) const { |
|
1459 switch (i.spec) { |
|
1460 case 0: |
|
1461 this->graph->next(i.e); |
|
1462 if (!this->graph->valid(i.e)) { |
|
1463 i.spec=1; |
|
1464 this->graph->first(i.n, S_CLASS); |
|
1465 if (!this->graph->valid(i.n)) { |
|
1466 i.spec=2; |
|
1467 this->graph->first(i.n, T_CLASS); |
|
1468 if (!this->graph->valid(i.n)) i.spec=3; |
|
1469 } |
|
1470 } |
|
1471 break; |
|
1472 case 1: |
|
1473 this->graph->next(i.n); |
|
1474 if (!this->graph->valid(i.n)) { |
|
1475 i.spec=2; |
|
1476 this->graph->first(i.n, T_CLASS); |
|
1477 if (!this->graph->valid(i.n)) i.spec=3; |
|
1478 } |
|
1479 break; |
|
1480 case 2: |
|
1481 this->graph->next(i.n); |
|
1482 if (!this->graph->valid(i.n)) i.spec=3; |
|
1483 break; |
|
1484 } |
|
1485 return i; |
|
1486 } |
|
1487 |
|
1488 Node tail(const Edge& e) const { |
|
1489 switch (e.spec) { |
|
1490 case 0: |
|
1491 return Node(this->graph->tail(e)); |
|
1492 break; |
|
1493 case 1: |
|
1494 return S_NODE; |
|
1495 break; |
|
1496 case 2: |
|
1497 default: |
|
1498 return Node(e.n); |
|
1499 break; |
|
1500 } |
|
1501 } |
|
1502 Node head(const Edge& e) const { |
|
1503 switch (e.spec) { |
|
1504 case 0: |
|
1505 return Node(this->graph->head(e)); |
|
1506 break; |
|
1507 case 1: |
|
1508 return Node(e.n); |
|
1509 break; |
|
1510 case 2: |
|
1511 default: |
|
1512 return T_NODE; |
|
1513 break; |
|
1514 } |
|
1515 } |
|
1516 |
|
1517 bool valid(const Node& n) const { return (n.spec<3); } |
|
1518 bool valid(const Edge& e) const { return (e.spec<3); } |
|
1519 |
|
1520 int nodeNum() const { return this->graph->nodeNum()+2; } |
|
1521 int edgeNum() const { |
|
1522 return this->graph->edgeNum()+this->graph->nodeNum(); |
|
1523 } |
|
1524 |
|
1525 Node aNode(const OutEdgeIt& e) const { return tail(e); } |
|
1526 Node aNode(const InEdgeIt& e) const { return head(e); } |
|
1527 Node bNode(const OutEdgeIt& e) const { return head(e); } |
|
1528 Node bNode(const InEdgeIt& e) const { return tail(e); } |
|
1529 |
|
1530 void addNode() const { } |
|
1531 void addEdge() const { } |
|
1532 |
|
1533 // Node addNode() const { return Node(this->graph->addNode()); } |
|
1534 // Edge addEdge(const Node& tail, const Node& head) const { |
|
1535 // return Edge(this->graph->addEdge(tail, head)); } |
|
1536 |
|
1537 // void erase(const Node& i) const { this->graph->erase(i); } |
|
1538 // void erase(const Edge& i) const { this->graph->erase(i); } |
|
1539 |
|
1540 // void clear() const { this->graph->clear(); } |
|
1541 |
|
1542 template<typename T> class NodeMap : public GraphWrapper<Graph>::template NodeMap<T> { |
|
1543 typedef typename GraphWrapper<Graph>::template NodeMap<T> Parent; |
|
1544 T s_value, t_value; |
|
1545 public: |
|
1546 NodeMap(const stGraphWrapper<Graph>& _G) : Parent(_G), |
|
1547 s_value(), |
|
1548 t_value() { } |
|
1549 NodeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a), |
|
1550 s_value(a), |
|
1551 t_value(a) { } |
|
1552 T operator[](const Node& n) const { |
|
1553 switch (n.spec) { |
|
1554 case 0: |
|
1555 return Parent::operator[](n); |
|
1556 break; |
|
1557 case 1: |
|
1558 return s_value; |
|
1559 break; |
|
1560 case 2: |
|
1561 default: |
|
1562 return t_value; |
|
1563 break; |
|
1564 } |
|
1565 } |
|
1566 void set(const Node& n, T t) { |
|
1567 switch (n.spec) { |
|
1568 case 0: |
|
1569 GraphWrapper<Graph>::template NodeMap<T>::set(n, t); |
|
1570 break; |
|
1571 case 1: |
|
1572 s_value=t; |
|
1573 break; |
|
1574 case 2: |
|
1575 default: |
|
1576 t_value=t; |
|
1577 break; |
|
1578 } |
|
1579 } |
|
1580 }; |
|
1581 |
|
1582 template<typename T, |
|
1583 typename Parent= |
|
1584 typename GraphWrapper<Graph>::template EdgeMap<T> > |
|
1585 class EdgeMap : public Parent { |
|
1586 //typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent; |
|
1587 typename GraphWrapper<Graph>::template NodeMap<T> node_value; |
|
1588 public: |
|
1589 EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G), |
|
1590 node_value(_G) { } |
|
1591 EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a), |
|
1592 node_value(_G, a) { } |
|
1593 T operator[](const Edge& e) const { |
|
1594 switch (e.spec) { |
|
1595 case 0: |
|
1596 return Parent::operator[](e); |
|
1597 break; |
|
1598 case 1: |
|
1599 return node_value[e.n]; |
|
1600 break; |
|
1601 case 2: |
|
1602 default: |
|
1603 return node_value[e.n]; |
|
1604 break; |
|
1605 } |
|
1606 } |
|
1607 void set(const Edge& e, T t) { |
|
1608 switch (e.spec) { |
|
1609 case 0: |
|
1610 Parent::set(e, t); |
|
1611 break; |
|
1612 case 1: |
|
1613 node_value.set(e.n, t); |
|
1614 break; |
|
1615 case 2: |
|
1616 default: |
|
1617 node_value.set(e.n, t); |
|
1618 break; |
|
1619 } |
|
1620 } |
|
1621 }; |
|
1622 |
|
1623 // template<typename T> class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> { |
|
1624 // typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent; |
|
1625 // typename GraphWrapper<Graph>::template NodeMap<T> node_value; |
|
1626 // public: |
|
1627 // EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G), |
|
1628 // node_value(_G) { } |
|
1629 // EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a), |
|
1630 // node_value(_G, a) { } |
|
1631 // T operator[](const Edge& e) const { |
|
1632 // switch (e.spec) { |
|
1633 // case 0: |
|
1634 // return Parent::operator[](e); |
|
1635 // break; |
|
1636 // case 1: |
|
1637 // return node_value[e.n]; |
|
1638 // break; |
|
1639 // case 2: |
|
1640 // default: |
|
1641 // return node_value[e.n]; |
|
1642 // break; |
|
1643 // } |
|
1644 // } |
|
1645 // void set(const Edge& e, T t) { |
|
1646 // switch (e.spec) { |
|
1647 // case 0: |
|
1648 // GraphWrapper<Graph>::template EdgeMap<T>::set(e, t); |
|
1649 // break; |
|
1650 // case 1: |
|
1651 // node_value.set(e.n, t); |
|
1652 // break; |
|
1653 // case 2: |
|
1654 // default: |
|
1655 // node_value.set(e.n, t); |
|
1656 // break; |
|
1657 // } |
|
1658 // } |
|
1659 // }; |
|
1660 |
|
1661 // template<typename G> |
|
1662 friend std::ostream& |
|
1663 operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i) { |
|
1664 os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")"; |
|
1665 return os; |
|
1666 } |
|
1667 // template<typename G> |
|
1668 friend std::ostream& |
|
1669 operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Edge& i) { |
|
1670 os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec << |
|
1671 " node: " << i.n << ")"; |
|
1672 return os; |
|
1673 } |
|
1674 |
|
1675 }; |
|
1676 |
|
1677 ///@} |
936 ///@} |
1678 |
937 |
1679 } //namespace hugo |
938 } //namespace hugo |
1680 |
939 |
1681 |
940 |