916 template<typename Graph> |
916 template<typename Graph> |
917 class BipartiteGraphWrapper : public GraphWrapper<Graph> { |
917 class BipartiteGraphWrapper : public GraphWrapper<Graph> { |
918 typedef IterableBoolMap< typename Graph::template NodeMap<int> > |
918 typedef IterableBoolMap< typename Graph::template NodeMap<int> > |
919 SFalseTTrueMap; |
919 SFalseTTrueMap; |
920 SFalseTTrueMap* s_false_t_true_map; |
920 SFalseTTrueMap* s_false_t_true_map; |
921 |
921 |
922 public: |
922 public: |
923 static const bool S_CLASS=false; |
923 static const bool S_CLASS=false; |
924 static const bool T_CLASS=true; |
924 static const bool T_CLASS=true; |
925 |
925 |
926 BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map) |
926 BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map) |
928 } |
928 } |
929 typedef typename GraphWrapper<Graph>::Node Node; |
929 typedef typename GraphWrapper<Graph>::Node Node; |
930 //using GraphWrapper<Graph>::NodeIt; |
930 //using GraphWrapper<Graph>::NodeIt; |
931 typedef typename GraphWrapper<Graph>::Edge Edge; |
931 typedef typename GraphWrapper<Graph>::Edge Edge; |
932 //using GraphWrapper<Graph>::EdgeIt; |
932 //using GraphWrapper<Graph>::EdgeIt; |
|
933 class ClassNodeIt; |
|
934 friend class ClassNodeIt; |
|
935 class OutEdgeIt; |
|
936 friend class OutEdgeIt; |
|
937 class InEdgeIt; |
|
938 friend class InEdgeIt; |
933 class ClassNodeIt { |
939 class ClassNodeIt { |
|
940 friend class BipartiteGraphWrapper<Graph>; |
|
941 protected: |
934 Node n; |
942 Node n; |
935 public: |
943 public: |
936 ClassNodeIt() { } |
944 ClassNodeIt() { } |
937 ClassNodeIt(const Invalid& i) : n(i) { } |
945 ClassNodeIt(const Invalid& i) : n(i) { } |
938 ClassNodeIt(const BipartiteGraphWrapper<Graph>& _G, bool _class) { |
946 ClassNodeIt(const BipartiteGraphWrapper<Graph>& _G, bool _class) { |
961 // _G.s_false_t_true_map->first(n, true); |
969 // _G.s_false_t_true_map->first(n, true); |
962 // } |
970 // } |
963 // operator Node() const { return n; } |
971 // operator Node() const { return n; } |
964 // }; |
972 // }; |
965 class OutEdgeIt { |
973 class OutEdgeIt { |
966 public: |
974 friend class BipartiteGraphWrapper<Graph>; |
967 |
975 protected: |
968 typename Graph::OutEdgeIt e; |
976 typename Graph::OutEdgeIt e; |
969 public: |
977 public: |
970 OutEdgeIt() { } |
978 OutEdgeIt() { } |
971 OutEdgeIt(const Invalid& i) : e(i) { } |
979 OutEdgeIt(const Invalid& i) : e(i) { } |
972 OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) { |
980 OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) { |
976 e=INVALID; |
984 e=INVALID; |
977 } |
985 } |
978 operator Edge() const { return Edge(typename Graph::Edge(e)); } |
986 operator Edge() const { return Edge(typename Graph::Edge(e)); } |
979 }; |
987 }; |
980 class InEdgeIt { |
988 class InEdgeIt { |
981 public: |
989 friend class BipartiteGraphWrapper<Graph>; |
|
990 protected: |
982 typename Graph::InEdgeIt e; |
991 typename Graph::InEdgeIt e; |
983 public: |
992 public: |
984 InEdgeIt() { } |
993 InEdgeIt() { } |
985 InEdgeIt(const Invalid& i) : e(i) { } |
994 InEdgeIt(const Invalid& i) : e(i) { } |
986 InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) { |
995 InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) { |
992 operator Edge() const { return Edge(typename Graph::Edge(e)); } |
1001 operator Edge() const { return Edge(typename Graph::Edge(e)); } |
993 }; |
1002 }; |
994 |
1003 |
995 using GraphWrapper<Graph>::first; |
1004 using GraphWrapper<Graph>::first; |
996 ClassNodeIt& first(ClassNodeIt& n, bool _class) const { |
1005 ClassNodeIt& first(ClassNodeIt& n, bool _class) const { |
997 n=SNodeIt(*this, _class) ; return n; } |
1006 n=ClassNodeIt(*this, _class) ; return n; } |
998 // SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; } |
1007 // SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; } |
999 // TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; } |
1008 // TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; } |
1000 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
1009 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
1001 i=OutEdgeIt(*this, p); return i; |
1010 i=OutEdgeIt(*this, p); return i; |
1002 } |
1011 } |
1004 i=InEdgeIt(*this, p); return i; |
1013 i=InEdgeIt(*this, p); return i; |
1005 } |
1014 } |
1006 |
1015 |
1007 using GraphWrapper<Graph>::next; |
1016 using GraphWrapper<Graph>::next; |
1008 ClassNodeIt& next(ClassNodeIt& n) const { |
1017 ClassNodeIt& next(ClassNodeIt& n) const { |
1009 this->s_false_t_true_map->next(n); return n; |
1018 this->s_false_t_true_map->next(n.n); return n; |
1010 } |
1019 } |
1011 // SNodeIt& next(SNodeIt& n) const { |
1020 // SNodeIt& next(SNodeIt& n) const { |
1012 // this->s_false_t_true_map->next(n); return n; |
1021 // this->s_false_t_true_map->next(n); return n; |
1013 // } |
1022 // } |
1014 // TNodeIt& next(TNodeIt& n) const { |
1023 // TNodeIt& next(TNodeIt& n) const { |
1317 break; |
1326 break; |
1318 } |
1327 } |
1319 return i; |
1328 return i; |
1320 } |
1329 } |
1321 OutEdgeIt& next(OutEdgeIt& i) const { |
1330 OutEdgeIt& next(OutEdgeIt& i) const { |
|
1331 typename Graph::Node v; |
1322 switch (i.spec) { |
1332 switch (i.spec) { |
1323 case 0: //normal edge |
1333 case 0: //normal edge |
1324 typename Graph::Node v=this->graph->aNode(i.e); |
1334 this->graph->aNode(i.e); |
1325 this->graph->next(i.e); |
1335 this->graph->next(i.e); |
1326 if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk |
1336 if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk |
1327 if (this->graph->inSClass(v)) { //S, nincs kiel |
1337 if (this->graph->inSClass(v)) { //S, nincs kiel |
1328 i.spec=3; |
1338 i.spec=3; |
1329 i.n=INVALID; |
1339 i.n=INVALID; |
1343 break; |
1353 break; |
1344 } |
1354 } |
1345 return i; |
1355 return i; |
1346 } |
1356 } |
1347 InEdgeIt& next(InEdgeIt& i) const { |
1357 InEdgeIt& next(InEdgeIt& i) const { |
|
1358 typename Graph::Node v; |
1348 switch (i.spec) { |
1359 switch (i.spec) { |
1349 case 0: //normal edge |
1360 case 0: //normal edge |
1350 typename Graph::Node v=this->graph->aNode(i.e); |
1361 v=this->graph->aNode(i.e); |
1351 this->graph->next(i.e); |
1362 this->graph->next(i.e); |
1352 if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk |
1363 if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk |
1353 if (this->graph->inTClass(v)) { //S, nincs beel |
1364 if (this->graph->inTClass(v)) { //S, nincs beel |
1354 i.spec=3; |
1365 i.spec=3; |
1355 i.n=INVALID; |
1366 i.n=INVALID; |
1401 return i; |
1412 return i; |
1402 } |
1413 } |
1403 |
1414 |
1404 Node tail(const Edge& e) const { |
1415 Node tail(const Edge& e) const { |
1405 switch (e.spec) { |
1416 switch (e.spec) { |
1406 case 0: |
1417 case 0: |
1407 return Node(this->graph->tail(e)); |
1418 return Node(this->graph->tail(e)); |
1408 break; |
1419 break; |
1409 case 1: |
1420 case 1: |
1410 return S_NODE; |
1421 return S_NODE; |
1411 break; |
1422 break; |
1412 case 2: |
1423 case 2: |
1413 return Node(e.n); |
1424 default: |
1414 break; |
1425 return Node(e.n); |
|
1426 break; |
1415 } |
1427 } |
1416 } |
1428 } |
1417 Node head(const Edge& e) const { |
1429 Node head(const Edge& e) const { |
1418 switch (e.spec) { |
1430 switch (e.spec) { |
1419 case 0: |
1431 case 0: |
1420 return Node(this->graph->head(e)); |
1432 return Node(this->graph->head(e)); |
1421 break; |
1433 break; |
1422 case 1: |
1434 case 1: |
1423 return Node(e.n); |
1435 return Node(e.n); |
1424 break; |
1436 break; |
1425 case 2: |
1437 case 2: |
1426 return T_NODE; |
1438 default: |
1427 break; |
1439 return T_NODE; |
|
1440 break; |
1428 } |
1441 } |
1429 } |
1442 } |
1430 |
1443 |
1431 bool valid(const Node& n) const { return (n.spec<3); } |
1444 bool valid(const Node& n) const { return (n.spec<3); } |
1432 bool valid(const Edge& e) const { return (e.spec<3); } |
1445 bool valid(const Edge& e) const { return (e.spec<3); } |
1456 NodeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a), |
1469 NodeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a), |
1457 s_value(a), |
1470 s_value(a), |
1458 t_value(a) { } |
1471 t_value(a) { } |
1459 T operator[](const Node& n) const { |
1472 T operator[](const Node& n) const { |
1460 switch (n.spec) { |
1473 switch (n.spec) { |
1461 case 0: |
1474 case 0: |
1462 return (*this)[n]; |
1475 return Parent::operator[](n); |
1463 break; |
1476 break; |
1464 case 1: |
1477 case 1: |
1465 return s_value; |
1478 return s_value; |
1466 break; |
1479 break; |
1467 case 2: |
1480 case 2: |
1468 return t_value; |
1481 default: |
1469 break; |
1482 return t_value; |
|
1483 break; |
1470 } |
1484 } |
1471 } |
1485 } |
1472 void set(const Node& n, T t) { |
1486 void set(const Node& n, T t) { |
1473 switch (n.spec) { |
1487 switch (n.spec) { |
1474 case 0: |
1488 case 0: |
1475 GraphWrapper<Graph>::template NodeMap<T>::set(n, t); |
1489 GraphWrapper<Graph>::template NodeMap<T>::set(n, t); |
1476 break; |
1490 break; |
1477 case 1: |
1491 case 1: |
1478 s_value=t; |
1492 s_value=t; |
1479 break; |
1493 break; |
1480 case 2: |
1494 case 2: |
1481 t_value=t; |
1495 default: |
1482 break; |
1496 t_value=t; |
|
1497 break; |
1483 } |
1498 } |
1484 } |
1499 } |
1485 }; |
1500 }; |
1486 |
1501 |
1487 template<typename T> class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> { |
1502 template<typename T> class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> { |
1488 typedef typename Graph::template NodeMap<T> Parent; |
1503 typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent; |
1489 typename GraphWrapper<Graph>::template NodeMap<T> node_value; |
1504 typename GraphWrapper<Graph>::template NodeMap<T> node_value; |
1490 public: |
1505 public: |
1491 EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G), |
1506 EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G), |
1492 node_value(_G) { } |
1507 node_value(_G) { } |
1493 EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a), |
1508 EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a), |
1494 node_value(_G, a) { } |
1509 node_value(_G, a) { } |
1495 T operator[](const Edge& e) const { |
1510 T operator[](const Edge& e) const { |
1496 switch (e.spec) { |
1511 switch (e.spec) { |
1497 case 0: |
1512 case 0: |
1498 return (*this)[e]; |
1513 return Parent::operator[](e); |
1499 break; |
1514 break; |
1500 case 1: |
1515 case 1: |
1501 return node_value[e.n]; |
1516 return node_value[e.n]; |
1502 break; |
1517 break; |
1503 case 2: |
1518 case 2: |
1504 return node_value[e.n]; |
1519 default: |
1505 break; |
1520 return node_value[e.n]; |
|
1521 break; |
1506 } |
1522 } |
1507 } |
1523 } |
1508 void set(const Edge& e, T t) { |
1524 void set(const Edge& e, T t) { |
1509 switch (e.spec) { |
1525 switch (e.spec) { |
1510 case 0: |
1526 case 0: |
1511 GraphWrapper<Graph>::set(e, t); |
1527 GraphWrapper<Graph>::template EdgeMap<T>::set(e, t); |
1512 break; |
1528 break; |
1513 case 1: |
1529 case 1: |
1514 node_value.set(e, t); |
1530 node_value.set(e.n, t); |
1515 break; |
1531 break; |
1516 case 2: |
1532 case 2: |
1517 node_value.set(e, t); |
1533 default: |
1518 break; |
1534 node_value.set(e.n, t); |
|
1535 break; |
1519 } |
1536 } |
1520 } |
1537 } |
1521 }; |
1538 }; |
1522 }; |
1539 }; |
1523 |
1540 |