Changeset 389:770cc1f4861f in lemon-0.x for src/work/marci/graph_wrapper.h
- Timestamp:
- 04/24/04 14:44:41 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@520
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/marci/graph_wrapper.h
r381 r389 184 184 void clear() const { graph->clear(); } 185 185 186 template<typename T> class NodeMap : public Graph::NodeMap<T> { 187 public: 188 NodeMap(const GraphWrapper<Graph>& _G) : 189 Graph::NodeMap<T>(*(_G.graph)) { } 190 NodeMap(const GraphWrapper<Graph>& _G, T a) : 191 Graph::NodeMap<T>(*(_G.graph), a) { } 192 }; 193 194 template<typename T> class EdgeMap : public Graph::EdgeMap<T> { 195 public: 196 EdgeMap(const GraphWrapper<Graph>& _G) : 197 Graph::EdgeMap<T>(*(_G.graph)) { } 198 EdgeMap(const GraphWrapper<Graph>& _G, T a) : 199 Graph::EdgeMap<T>(*(_G.graph), a) { } 186 template<typename T> class NodeMap : public Graph::template NodeMap<T> { 187 typedef typename Graph::template NodeMap<T> Parent; 188 public: 189 NodeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { } 190 NodeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { } 191 }; 192 193 template<typename T> class EdgeMap : public Graph::template EdgeMap<T> { 194 typedef typename Graph::template EdgeMap<T> Parent; 195 public: 196 EdgeMap(const GraphWrapper<Graph>& _G) : Parent(*(_G.graph)) { } 197 EdgeMap(const GraphWrapper<Graph>& _G, T a) : Parent(*(_G.graph), a) { } 200 198 }; 201 199 }; … … 253 251 254 252 using GraphWrapper<Graph>::next; 255 OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; } 256 InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; } 257 258 Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); } 259 Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } 260 Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } 261 Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } 253 OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; } 254 InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; } 255 256 Node aNode(const OutEdgeIt& e) const { 257 return Node(this->graph->aNode(e.e)); } 258 Node aNode(const InEdgeIt& e) const { 259 return Node(this->graph->aNode(e.e)); } 260 Node bNode(const OutEdgeIt& e) const { 261 return Node(this->graph->bNode(e.e)); } 262 Node bNode(const InEdgeIt& e) const { 263 return Node(this->graph->bNode(e.e)); } 262 264 263 265 Node tail(const Edge& e) const { … … 367 369 368 370 NodeIt& next(NodeIt& i) const { 369 graph->next(i.n); 370 while (graph->valid(i) && !(*node_filter_map)[i.n]) { graph->next(i.n); } 371 this->graph->next(i.n); 372 while (this->graph->valid(i) && !(*node_filter_map)[i.n]) { 373 this->graph->next(i.n); } 371 374 return i; 372 375 } 373 376 OutEdgeIt& next(OutEdgeIt& i) const { 374 graph->next(i.e); 375 while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); } 377 this->graph->next(i.e); 378 while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 379 this->graph->next(i.e); } 376 380 return i; 377 381 } 378 382 InEdgeIt& next(InEdgeIt& i) const { 379 graph->next(i.e); 380 while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); } 383 this->graph->next(i.e); 384 while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 385 this->graph->next(i.e); } 381 386 return i; 382 387 } 383 388 EdgeIt& next(EdgeIt& i) const { 384 graph->next(i.e); 385 while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); } 389 this->graph->next(i.e); 390 while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) { 391 this->graph->next(i.e); } 386 392 return i; 387 393 } 388 394 389 Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); } 390 Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } 391 Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } 392 Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } 395 Node aNode(const OutEdgeIt& e) const { 396 return Node(this->graph->aNode(e.e)); } 397 Node aNode(const InEdgeIt& e) const { 398 return Node(this->graph->aNode(e.e)); } 399 Node bNode(const OutEdgeIt& e) const { 400 return Node(this->graph->bNode(e.e)); } 401 Node bNode(const InEdgeIt& e) const { 402 return Node(this->graph->bNode(e.e)); } 393 403 394 404 ///\todo … … 470 480 OutEdgeIt& next(OutEdgeIt& e) const { 471 481 if (e.out_or_in) { 472 typename Graph::Node n=graph->tail(e.out); 473 graph->next(e.out); 474 if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); } 482 typename Graph::Node n=this->graph->tail(e.out); 483 this->graph->next(e.out); 484 if (!this->graph->valid(e.out)) { 485 e.out_or_in=false; this->graph->first(e.in, n); } 475 486 } else { 476 graph->next(e.in);487 this->graph->next(e.in); 477 488 } 478 489 return e; … … 486 497 487 498 Node aNode(const OutEdgeIt& e) const { 488 if (e.out_or_in) return graph->tail(e); else return graph->head(e); } 499 if (e.out_or_in) return this->graph->tail(e); else 500 return this->graph->head(e); } 489 501 Node bNode(const OutEdgeIt& e) const { 490 if (e.out_or_in) return graph->head(e); else return graph->tail(e); } 502 if (e.out_or_in) return this->graph->head(e); else 503 return this->graph->tail(e); } 491 504 }; 492 505 … … 646 659 OutEdgeIt& next(OutEdgeIt& e) const { 647 660 if (e.forward) { 648 Node v=graph->aNode(e.out); 649 graph->next(e.out); 650 while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); } 651 if (!graph->valid(e.out)) { 661 Node v=this->graph->aNode(e.out); 662 this->graph->next(e.out); 663 while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 664 this->graph->next(e.out); } 665 if (!this->graph->valid(e.out)) { 652 666 e.forward=false; 653 graph->first(e.in, v); 654 while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); } 667 this->graph->first(e.in, v); 668 while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 669 this->graph->next(e.in); } 655 670 } 656 671 } else { 657 graph->next(e.in); 658 while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); } 672 this->graph->next(e.in); 673 while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 674 this->graph->next(e.in); } 659 675 } 660 676 return e; … … 663 679 InEdgeIt& next(InEdgeIt& e) const { 664 680 if (e.forward) { 665 Node v=graph->aNode(e.in); 666 graph->next(e.in); 667 while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); } 668 if (!graph->valid(e.in)) { 681 Node v=this->graph->aNode(e.in); 682 this->graph->next(e.in); 683 while( this->graph->valid(e.in) && !(resCap(e)>0) ) { 684 this->graph->next(e.in); } 685 if (!this->graph->valid(e.in)) { 669 686 e.forward=false; 670 graph->first(e.out, v); 671 while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); } 687 this->graph->first(e.out, v); 688 while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 689 this->graph->next(e.out); } 672 690 } 673 691 } else { 674 graph->next(e.out); 675 while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); } 692 this->graph->next(e.out); 693 while( this->graph->valid(e.out) && !(resCap(e)>0) ) { 694 this->graph->next(e.out); } 676 695 } 677 696 return e; … … 679 698 EdgeIt& next(EdgeIt& e) const { 680 699 if (e.forward) { 681 graph->next(e.e); 682 while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); } 683 if (!graph->valid(e.e)) { 700 this->graph->next(e.e); 701 while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 702 this->graph->next(e.e); } 703 if (!this->graph->valid(e.e)) { 684 704 e.forward=false; 685 graph->first(e.e); 686 while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); } 705 this->graph->first(e.e); 706 while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 707 this->graph->next(e.e); } 687 708 } 688 709 } else { 689 graph->next(e.e); 690 while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); } 710 this->graph->next(e.e); 711 while( this->graph->valid(e.e) && !(resCap(e)>0) ) { 712 this->graph->next(e.e); } 691 713 } 692 714 return e; … … 694 716 695 717 Node tail(Edge e) const { 696 return ((e.forward) ? graph->tail(e) :graph->head(e)); }718 return ((e.forward) ? this->graph->tail(e) : this->graph->head(e)); } 697 719 Node head(Edge e) const { 698 return ((e.forward) ? graph->head(e) :graph->tail(e)); }720 return ((e.forward) ? this->graph->head(e) : this->graph->tail(e)); } 699 721 700 722 Node aNode(OutEdgeIt e) const { 701 return ((e.forward) ? graph->aNode(e.out) : graph->aNode(e.in)); } 723 return ((e.forward) ? this->graph->aNode(e.out) : 724 this->graph->aNode(e.in)); } 702 725 Node bNode(OutEdgeIt e) const { 703 return ((e.forward) ? graph->bNode(e.out) : graph->bNode(e.in)); } 726 return ((e.forward) ? this->graph->bNode(e.out) : 727 this->graph->bNode(e.in)); } 704 728 705 729 Node aNode(InEdgeIt e) const { 706 return ((e.forward) ? graph->aNode(e.in) : graph->aNode(e.out)); } 730 return ((e.forward) ? this->graph->aNode(e.in) : 731 this->graph->aNode(e.out)); } 707 732 Node bNode(InEdgeIt e) const { 708 return ((e.forward) ? graph->bNode(e.in) : graph->bNode(e.out)); } 733 return ((e.forward) ? this->graph->bNode(e.in) : 734 this->graph->bNode(e.out)); } 709 735 710 736 // int nodeNum() const { return graph->nodeNum(); } … … 718 744 bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); } 719 745 bool valid(Edge e) const { 720 return graph->valid(e);746 return this->graph->valid(e); 721 747 //return e.forward ? graph->valid(e.out) : graph->valid(e.in); 722 748 } … … 752 778 template <typename T> 753 779 class EdgeMap { 754 typename Graph:: EdgeMap<T> forward_map, backward_map;780 typename Graph::template EdgeMap<T> forward_map, backward_map; 755 781 public: 756 782 EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { } … … 862 888 using GraphWrapper<Graph>::next; 863 889 // NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; } 864 OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }865 InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }866 EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }890 OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; } 891 InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; } 892 EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; } 867 893 868 Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); } 869 Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } 870 Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } 871 Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } 894 Node aNode(const OutEdgeIt& e) const { 895 return Node(this->graph->aNode(e.e)); } 896 Node aNode(const InEdgeIt& e) const { 897 return Node(this->graph->aNode(e.e)); } 898 Node bNode(const OutEdgeIt& e) const { 899 return Node(this->graph->bNode(e.e)); } 900 Node bNode(const InEdgeIt& e) const { 901 return Node(this->graph->bNode(e.e)); } 872 902 873 903 void erase(const OutEdgeIt& e) const { … … 886 916 template<typename Graph> 887 917 class BipartiteGraphWrapper : public GraphWrapper<Graph> { 888 typedef IterableBoolMap< typename Graph::NodeMap<int> > SFalseTTrueMap; 918 typedef IterableBoolMap< typename Graph::template NodeMap<int> > 919 SFalseTTrueMap; 889 920 SFalseTTrueMap* s_false_t_true_map; 890 921 … … 984 1015 // this->s_false_t_true_map->next(n); return n; 985 1016 // } 986 OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }987 InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }1017 OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; } 1018 InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; } 988 1019 989 1020 Node tail(const Edge& e) { … … 1079 1110 friend class GraphWrapper<Graph>; 1080 1111 friend class stGraphWrapper<Graph>; 1081 template <typename T> friend class stGraphWrapper<Graph>::NodeMap;1112 template <typename T> friend class NodeMap; 1082 1113 friend class Edge; 1083 1114 friend class OutEdgeIt; … … 1120 1151 friend class GraphWrapper<Graph>; 1121 1152 friend class stGraphWrapper<Graph>; 1122 template <typename T> friend class stGraphWrapper<Graph>::EdgeMap;1153 template <typename T> friend class EdgeMap; 1123 1154 int spec; 1124 1155 typename Graph::Node n; … … 1274 1305 switch (i.spec) { 1275 1306 case 0: 1276 graph->next(i.n);1277 if (! graph->valid(i.n)) {1307 this->graph->next(i.n); 1308 if (!this->graph->valid(i.n)) { 1278 1309 i.spec=1; 1279 1310 } … … 1291 1322 switch (i.spec) { 1292 1323 case 0: //normal edge 1293 typename Graph::Node v= graph->aNode(i.e);1294 graph->next(i.e);1295 if (! graph->valid(i.e)) { //Az igazi elek vegere ertunk1296 if ( graph->inSClass(v)) { //S, nincs kiel1324 typename Graph::Node v=this->graph->aNode(i.e); 1325 this->graph->next(i.e); 1326 if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk 1327 if (this->graph->inSClass(v)) { //S, nincs kiel 1297 1328 i.spec=3; 1298 1329 i.n=INVALID; … … 1304 1335 break; 1305 1336 case 1: //s->vmi 1306 graph->next(i.n);1307 if (! graph->valid(i.n)) i.spec=3;1337 this->graph->next(i.n); 1338 if (!this->graph->valid(i.n)) i.spec=3; 1308 1339 break; 1309 1340 case 2: //vmi->t … … 1317 1348 switch (i.spec) { 1318 1349 case 0: //normal edge 1319 typename Graph::Node v= graph->aNode(i.e);1320 graph->next(i.e);1321 if (! graph->valid(i.e)) { //Az igazi elek vegere ertunk1322 if ( graph->inTClass(v)) { //S, nincs beel1350 typename Graph::Node v=this->graph->aNode(i.e); 1351 this->graph->next(i.e); 1352 if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk 1353 if (this->graph->inTClass(v)) { //S, nincs beel 1323 1354 i.spec=3; 1324 1355 i.n=INVALID; … … 1334 1365 break; 1335 1366 case 2: //vmi->t 1336 graph->next(i.n);1337 if (! graph->valid(i.n)) i.spec=3;1367 this->graph->next(i.n); 1368 if (!this->graph->valid(i.n)) i.spec=3; 1338 1369 break; 1339 1370 } … … 1344 1375 switch (i.spec) { 1345 1376 case 0: 1346 graph->next(i.e);1347 if (! graph->valid(i.e)) {1377 this->graph->next(i.e); 1378 if (!this->graph->valid(i.e)) { 1348 1379 i.spec=1; 1349 graph->first(n, S_CLASS);1350 if (! graph->valid(i.n)) {1380 this->graph->first(i.n, S_CLASS); 1381 if (!this->graph->valid(i.n)) { 1351 1382 i.spec=2; 1352 graph->first(n, T_CLASS);1353 if (! graph->valid(i.n))spec=3;1383 this->graph->first(i.n, T_CLASS); 1384 if (!this->graph->valid(i.n)) i.spec=3; 1354 1385 } 1355 1386 } 1356 1387 break; 1357 1388 case 1: 1358 graph->next(i.n);1359 if (! graph->valid(i.n)) {1389 this->graph->next(i.n); 1390 if (!this->graph->valid(i.n)) { 1360 1391 i.spec=2; 1361 graph->first(n, T_CLASS);1362 if (! graph->valid(i.n))spec=3;1392 this->graph->first(i.n, T_CLASS); 1393 if (!this->graph->valid(i.n)) i.spec=3; 1363 1394 } 1364 1395 break; 1365 1396 case 2: 1366 graph->next(i.n);1367 if (! graph->valid(i.n)) i.spec=3;1397 this->graph->next(i.n); 1398 if (!this->graph->valid(i.n)) i.spec=3; 1368 1399 break; 1369 1400 } … … 1374 1405 switch (e.spec) { 1375 1406 case 0: 1376 return Node( graph->tail(e));1407 return Node(this->graph->tail(e)); 1377 1408 break; 1378 1409 case 1: … … 1387 1418 switch (e.spec) { 1388 1419 case 0: 1389 return Node( graph->head(e));1420 return Node(this->graph->head(e)); 1390 1421 break; 1391 1422 case 1: … … 1401 1432 bool valid(const Edge& e) const { return (e.spec<3); } 1402 1433 1403 // int nodeNum() const { return graph->nodeNum(); }1404 // int edgeNum() const { return graph->edgeNum(); }1434 // int nodeNum() const { return this->graph->nodeNum(); } 1435 // int edgeNum() const { return this->graph->edgeNum(); } 1405 1436 1406 1437 Node aNode(const OutEdgeIt& e) const { return tail(e); } … … 1409 1440 Node bNode(const InEdgeIt& e) const { return tail(e); } 1410 1441 1411 // Node addNode() const { return Node( graph->addNode()); }1442 // Node addNode() const { return Node(this->graph->addNode()); } 1412 1443 // Edge addEdge(const Node& tail, const Node& head) const { 1413 // return Edge( graph->addEdge(tail, head)); }1414 1415 // void erase(const Node& i) const { graph->erase(i); }1416 // void erase(const Edge& i) const { graph->erase(i); }1444 // return Edge(this->graph->addEdge(tail, head)); } 1445 1446 // void erase(const Node& i) const { this->graph->erase(i); } 1447 // void erase(const Edge& i) const { this->graph->erase(i); } 1417 1448 1418 // void clear() const { graph->clear(); }1449 // void clear() const { this->graph->clear(); } 1419 1450 1420 template<typename T> class NodeMap : public GraphWrapper<Graph>::NodeMap<T> { 1451 template<typename T> class NodeMap : public GraphWrapper<Graph>::template NodeMap<T> { 1452 typedef typename GraphWrapper<Graph>::template NodeMap<T> Parent; 1421 1453 T s_value, t_value; 1422 1454 public: 1423 NodeMap(const stGraphWrapper<Graph>& _G) : 1424 GraphWrapper<Graph>::NodeMap<T>(_G) { } 1425 NodeMap(const stGraphWrapper<Graph>& _G, T a) :1426 GraphWrapper<Graph>::NodeMap<T>(_G, a), s_value(a),t_value(a) { }1455 NodeMap(const stGraphWrapper<Graph>& _G) : Parent(_G) { } 1456 NodeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a), 1457 s_value(a), 1458 t_value(a) { } 1427 1459 T operator[](const Node& n) const { 1428 1460 switch (n.spec) { … … 1441 1473 switch (n.spec) { 1442 1474 case 0: 1443 GraphWrapper<Graph>:: NodeMap<T>::set(n, t);1475 GraphWrapper<Graph>::template NodeMap<T>::set(n, t); 1444 1476 break; 1445 1477 case 1: … … 1453 1485 }; 1454 1486 1455 template<typename T> class EdgeMap : public GraphWrapper<Graph>::EdgeMap<T> { 1456 typename GraphWrapper<Graph>::NodeMap<T> node_value; 1457 public: 1458 EdgeMap(const stGraphWrapper<Graph>& _G) : 1459 GraphWrapper<Graph>::EdgeMap<T>(_G), node_value(_G) { } 1460 EdgeMap(const stGraphWrapper<Graph>& _G, T a) : 1461 GraphWrapper<Graph>::EdgeMap<T>(_G, a), node_value(_G, a) { } 1487 template<typename T> class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> { 1488 typedef typename Graph::template NodeMap<T> Parent; 1489 typename GraphWrapper<Graph>::template NodeMap<T> node_value; 1490 public: 1491 EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G), 1492 node_value(_G) { } 1493 EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a), 1494 node_value(_G, a) { } 1462 1495 T operator[](const Edge& e) const { 1463 1496 switch (e.spec) {
Note: See TracChangeset
for help on using the changeset viewer.