Changeset 933:1b7c88fbb950 in lemon0.x
 Timestamp:
 10/01/04 13:31:03 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1258
 Location:
 src
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

src/lemon/graph_wrapper.h
r932 r933 369 369 \c Graph::Node that is why \c g.id(n) can be applied. 370 370 371 Consider now a mathematically more invloved problem, where the application 372 of SubGraphWrapper is reasonable sure enough. If a shortest path is to be 371 For other examples see also the documentation of NodeSubGraphWrapper and 372 EdgeSubGraphWrapper. 373 374 \author Marton Makai 375 */ 376 template<typename Graph, typename NodeFilterMap, 377 typename EdgeFilterMap> 378 class SubGraphWrapper : public GraphWrapper<Graph> { 379 public: 380 typedef GraphWrapper<Graph> Parent; 381 protected: 382 NodeFilterMap* node_filter_map; 383 EdgeFilterMap* edge_filter_map; 384 385 SubGraphWrapper() : GraphWrapper<Graph>(), 386 node_filter_map(0), edge_filter_map(0) { } 387 void setNodeFilterMap(NodeFilterMap& _node_filter_map) { 388 node_filter_map=&_node_filter_map; 389 } 390 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) { 391 edge_filter_map=&_edge_filter_map; 392 } 393 394 public: 395 SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map, 396 EdgeFilterMap& _edge_filter_map) : 397 GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map), 398 edge_filter_map(&_edge_filter_map) { } 399 400 typedef typename GraphWrapper<Graph>::Node Node; 401 class NodeIt : public Node { 402 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw; 403 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; 404 public: 405 NodeIt() { } 406 NodeIt(Invalid i) : Node(i) { } 407 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) : 408 Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { 409 while (*static_cast<Node*>(this)!=INVALID && 410 !(*(gw>node_filter_map))[*this]) 411 *(static_cast<Node*>(this))= 412 ++(typename Graph::NodeIt(*(gw>graph), *this)); 413 } 414 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 415 const Node& n) : 416 Node(n), gw(&_gw) { } 417 NodeIt& operator++() { 418 *(static_cast<Node*>(this))= 419 ++(typename Graph::NodeIt(*(gw>graph), *this)); 420 while (*static_cast<Node*>(this)!=INVALID && 421 !(*(gw>node_filter_map))[*this]) 422 *(static_cast<Node*>(this))= 423 ++(typename Graph::NodeIt(*(gw>graph), *this)); 424 return *this; 425 } 426 }; 427 typedef typename GraphWrapper<Graph>::Edge Edge; 428 class OutEdgeIt : public Edge { 429 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw; 430 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; 431 public: 432 OutEdgeIt() { } 433 OutEdgeIt(Invalid i) : Edge(i) { } 434 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) : 435 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { 436 while (*static_cast<Edge*>(this)!=INVALID && 437 !(*(gw>edge_filter_map))[*this]) 438 *(static_cast<Edge*>(this))= 439 ++(typename Graph::OutEdgeIt(*(gw>graph), *this)); 440 } 441 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 442 const Edge& e) : 443 Edge(e), gw(&_gw) { } 444 OutEdgeIt& operator++() { 445 *(static_cast<Edge*>(this))= 446 ++(typename Graph::OutEdgeIt(*(gw>graph), *this)); 447 while (*static_cast<Edge*>(this)!=INVALID && 448 !(*(gw>edge_filter_map))[*this]) 449 *(static_cast<Edge*>(this))= 450 ++(typename Graph::OutEdgeIt(*(gw>graph), *this)); 451 return *this; 452 } 453 }; 454 class InEdgeIt : public Edge { 455 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw; 456 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; 457 public: 458 InEdgeIt() { } 459 // InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { } 460 InEdgeIt(Invalid i) : Edge(i) { } 461 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) : 462 Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { 463 while (*static_cast<Edge*>(this)!=INVALID && 464 !(*(gw>edge_filter_map))[*this]) 465 *(static_cast<Edge*>(this))= 466 ++(typename Graph::InEdgeIt(*(gw>graph), *this)); 467 } 468 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 469 const Edge& e) : 470 Edge(e), gw(&_gw) { } 471 InEdgeIt& operator++() { 472 *(static_cast<Edge*>(this))= 473 ++(typename Graph::InEdgeIt(*(gw>graph), *this)); 474 while (*static_cast<Edge*>(this)!=INVALID && 475 !(*(gw>edge_filter_map))[*this]) 476 *(static_cast<Edge*>(this))= 477 ++(typename Graph::InEdgeIt(*(gw>graph), *this)); 478 return *this; 479 } 480 }; 481 class EdgeIt : public Edge { 482 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw; 483 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; 484 public: 485 EdgeIt() { } 486 EdgeIt(Invalid i) : Edge(i) { } 487 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) : 488 Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { 489 while (*static_cast<Edge*>(this)!=INVALID && 490 !(*(gw>edge_filter_map))[*this]) 491 *(static_cast<Edge*>(this))= 492 ++(typename Graph::EdgeIt(*(gw>graph), *this)); 493 } 494 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 495 const Edge& e) : 496 Edge(e), gw(&_gw) { } 497 EdgeIt& operator++() { 498 *(static_cast<Edge*>(this))= 499 ++(typename Graph::EdgeIt(*(gw>graph), *this)); 500 while (*static_cast<Edge*>(this)!=INVALID && 501 !(*(gw>edge_filter_map))[*this]) 502 *(static_cast<Edge*>(this))= 503 ++(typename Graph::EdgeIt(*(gw>graph), *this)); 504 return *this; 505 } 506 }; 507 508 NodeIt& first(NodeIt& i) const { 509 i=NodeIt(*this); return i; 510 } 511 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 512 i=OutEdgeIt(*this, p); return i; 513 } 514 InEdgeIt& first(InEdgeIt& i, const Node& p) const { 515 i=InEdgeIt(*this, p); return i; 516 } 517 EdgeIt& first(EdgeIt& i) const { 518 i=EdgeIt(*this); return i; 519 } 520 521 /// This function hides \c n in the graph, i.e. the iteration 522 /// jumps over it. This is done by simply setting the value of \c n 523 /// to be false in the corresponding nodemap. 524 void hide(const Node& n) const { node_filter_map>set(n, false); } 525 526 /// This function hides \c e in the graph, i.e. the iteration 527 /// jumps over it. This is done by simply setting the value of \c e 528 /// to be false in the corresponding edgemap. 529 void hide(const Edge& e) const { edge_filter_map>set(e, false); } 530 531 /// The value of \c n is set to be true in the nodemap which stores 532 /// hide information. If \c n was hidden previuosly, then it is shown 533 /// again 534 void unHide(const Node& n) const { node_filter_map>set(n, true); } 535 536 /// The value of \c e is set to be true in the edgemap which stores 537 /// hide information. If \c e was hidden previuosly, then it is shown 538 /// again 539 void unHide(const Edge& e) const { edge_filter_map>set(e, true); } 540 541 /// Returns true if \c n is hidden. 542 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; } 543 544 /// Returns true if \c n is hidden. 545 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; } 546 547 /// \warning This is a linear time operation and works only if 548 /// \c Graph::NodeIt is defined. 549 int nodeNum() const { 550 int i=0; 551 for (NodeIt n(*this); n!=INVALID; ++n) ++i; 552 return i; 553 } 554 555 /// \warning This is a linear time operation and works only if 556 /// \c Graph::EdgeIt is defined. 557 int edgeNum() const { 558 int i=0; 559 for (EdgeIt e(*this); e!=INVALID; ++e) ++i; 560 return i; 561 } 562 563 // KEEP_MAPS(Parent, SubGraphWrapper); 564 }; 565 566 567 /*! \brief A wrapper for hiding nodes from a graph. 568 569 \warning Graph wrappers are in even more experimental state than the other 570 parts of the lib. Use them at you own risk. 571 572 A wrapper for hiding nodes from a graph. 573 This wrapper specializes SubGraphWrapper in the way that only the nodeset 574 can be filtered. Note that this does not mean of considering induced 575 subgraph, the edgeiterators consider the original edgeset. 576 \author Marton Makai 577 */ 578 template<typename Graph, typename NodeFilterMap> 579 class NodeSubGraphWrapper : 580 public SubGraphWrapper<Graph, NodeFilterMap, 581 ConstMap<typename Graph::Edge,bool> > { 582 public: 583 typedef SubGraphWrapper<Graph, NodeFilterMap, 584 ConstMap<typename Graph::Edge,bool> > Parent; 585 protected: 586 ConstMap<typename Graph::Edge, bool> const_true_map; 587 public: 588 NodeSubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map) : 589 Parent(), const_true_map(true) { 590 Parent::setGraph(_graph); 591 Parent::setNodeFilterMap(_node_filter_map); 592 Parent::setEdgeFilterMap(const_true_map); 593 } 594 }; 595 596 597 /*! \brief A wrapper for hiding edges from a graph. 598 599 \warning Graph wrappers are in even more experimental state than the other 600 parts of the lib. Use them at you own risk. 601 602 A wrapper for hiding edges from a graph. 603 This wrapper specializes SubGraphWrapper in the way that only the edgeset 604 can be filtered. The usefulness of this wrapper is demonstrated in the 605 problem of searching a maximum number of edgedisjoint shortest paths 606 between 607 two nodes \c s and \c t. Shortest here means being shortest w.r.t. 608 nonnegative edgelengths. Note that 609 the comprehension of the presented solution 610 need's some knowledge from elementary combinatorial optimization. 611 612 If a single shortest path is to be 373 613 searched between two nodes \c s and \c t, then this can be done easily by 374 614 applying the Dijkstra algorithm class. What happens, if a maximum number of … … 377 617 the potential function computed by Dijkstra. Moreover, any path containing 378 618 only such edges is a shortest one. Thus we have to compute a maximum number 379 of edgedisjoint path between \c s and \c t in the graph which has edgeset619 of edgedisjoint paths between \c s and \c t in the graph which has edgeset 380 620 all the tight edges. The computation will be demonstrated on the following 381 621 graph, which is read from a dimacs file. … … 478 718 1, 02>2 479 719 \endcode 480 \author Marton Makai 481 */ 482 template<typename Graph, typename NodeFilterMap, 483 typename EdgeFilterMap> 484 class SubGraphWrapper : public GraphWrapper<Graph> { 485 public: 486 typedef GraphWrapper<Graph> Parent; 487 protected: 488 NodeFilterMap* node_filter_map; 489 EdgeFilterMap* edge_filter_map; 490 491 SubGraphWrapper() : GraphWrapper<Graph>(), 492 node_filter_map(0), edge_filter_map(0) { } 493 void setNodeFilterMap(NodeFilterMap& _node_filter_map) { 494 node_filter_map=&_node_filter_map; 495 } 496 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) { 497 edge_filter_map=&_edge_filter_map; 498 } 499 500 public: 501 SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map, 502 EdgeFilterMap& _edge_filter_map) : 503 GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map), 504 edge_filter_map(&_edge_filter_map) { } 505 506 typedef typename GraphWrapper<Graph>::Node Node; 507 class NodeIt : public Node { 508 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw; 509 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; 510 public: 511 NodeIt() { } 512 NodeIt(Invalid i) : Node(i) { } 513 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) : 514 Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { 515 while (*static_cast<Node*>(this)!=INVALID && 516 !(*(gw>node_filter_map))[*this]) 517 *(static_cast<Node*>(this))= 518 ++(typename Graph::NodeIt(*(gw>graph), *this)); 519 } 520 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 521 const Node& n) : 522 Node(n), gw(&_gw) { } 523 NodeIt& operator++() { 524 *(static_cast<Node*>(this))= 525 ++(typename Graph::NodeIt(*(gw>graph), *this)); 526 while (*static_cast<Node*>(this)!=INVALID && 527 !(*(gw>node_filter_map))[*this]) 528 *(static_cast<Node*>(this))= 529 ++(typename Graph::NodeIt(*(gw>graph), *this)); 530 return *this; 531 } 532 }; 533 typedef typename GraphWrapper<Graph>::Edge Edge; 534 class OutEdgeIt : public Edge { 535 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw; 536 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; 537 public: 538 OutEdgeIt() { } 539 OutEdgeIt(Invalid i) : Edge(i) { } 540 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) : 541 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { 542 while (*static_cast<Edge*>(this)!=INVALID && 543 !(*(gw>edge_filter_map))[*this]) 544 *(static_cast<Edge*>(this))= 545 ++(typename Graph::OutEdgeIt(*(gw>graph), *this)); 546 } 547 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 548 const Edge& e) : 549 Edge(e), gw(&_gw) { } 550 OutEdgeIt& operator++() { 551 *(static_cast<Edge*>(this))= 552 ++(typename Graph::OutEdgeIt(*(gw>graph), *this)); 553 while (*static_cast<Edge*>(this)!=INVALID && 554 !(*(gw>edge_filter_map))[*this]) 555 *(static_cast<Edge*>(this))= 556 ++(typename Graph::OutEdgeIt(*(gw>graph), *this)); 557 return *this; 558 } 559 }; 560 class InEdgeIt : public Edge { 561 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw; 562 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; 563 public: 564 InEdgeIt() { } 565 // InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { } 566 InEdgeIt(Invalid i) : Edge(i) { } 567 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) : 568 Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { 569 while (*static_cast<Edge*>(this)!=INVALID && 570 !(*(gw>edge_filter_map))[*this]) 571 *(static_cast<Edge*>(this))= 572 ++(typename Graph::InEdgeIt(*(gw>graph), *this)); 573 } 574 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 575 const Edge& e) : 576 Edge(e), gw(&_gw) { } 577 InEdgeIt& operator++() { 578 *(static_cast<Edge*>(this))= 579 ++(typename Graph::InEdgeIt(*(gw>graph), *this)); 580 while (*static_cast<Edge*>(this)!=INVALID && 581 !(*(gw>edge_filter_map))[*this]) 582 *(static_cast<Edge*>(this))= 583 ++(typename Graph::InEdgeIt(*(gw>graph), *this)); 584 return *this; 585 } 586 }; 587 class EdgeIt : public Edge { 588 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw; 589 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; 590 public: 591 EdgeIt() { } 592 EdgeIt(Invalid i) : Edge(i) { } 593 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) : 594 Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { 595 while (*static_cast<Edge*>(this)!=INVALID && 596 !(*(gw>edge_filter_map))[*this]) 597 *(static_cast<Edge*>(this))= 598 ++(typename Graph::EdgeIt(*(gw>graph), *this)); 599 } 600 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, 601 const Edge& e) : 602 Edge(e), gw(&_gw) { } 603 EdgeIt& operator++() { 604 *(static_cast<Edge*>(this))= 605 ++(typename Graph::EdgeIt(*(gw>graph), *this)); 606 while (*static_cast<Edge*>(this)!=INVALID && 607 !(*(gw>edge_filter_map))[*this]) 608 *(static_cast<Edge*>(this))= 609 ++(typename Graph::EdgeIt(*(gw>graph), *this)); 610 return *this; 611 } 612 }; 613 614 NodeIt& first(NodeIt& i) const { 615 i=NodeIt(*this); return i; 616 } 617 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 618 i=OutEdgeIt(*this, p); return i; 619 } 620 InEdgeIt& first(InEdgeIt& i, const Node& p) const { 621 i=InEdgeIt(*this, p); return i; 622 } 623 EdgeIt& first(EdgeIt& i) const { 624 i=EdgeIt(*this); return i; 625 } 626 627 /// This function hides \c n in the graph, i.e. the iteration 628 /// jumps over it. This is done by simply setting the value of \c n 629 /// to be false in the corresponding nodemap. 630 void hide(const Node& n) const { node_filter_map>set(n, false); } 631 632 /// This function hides \c e in the graph, i.e. the iteration 633 /// jumps over it. This is done by simply setting the value of \c e 634 /// to be false in the corresponding edgemap. 635 void hide(const Edge& e) const { edge_filter_map>set(e, false); } 636 637 /// The value of \c n is set to be true in the nodemap which stores 638 /// hide information. If \c n was hidden previuosly, then it is shown 639 /// again 640 void unHide(const Node& n) const { node_filter_map>set(n, true); } 641 642 /// The value of \c e is set to be true in the edgemap which stores 643 /// hide information. If \c e was hidden previuosly, then it is shown 644 /// again 645 void unHide(const Edge& e) const { edge_filter_map>set(e, true); } 646 647 /// Returns true if \c n is hidden. 648 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; } 649 650 /// Returns true if \c n is hidden. 651 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; } 652 653 /// \warning This is a linear time operation and works only if 654 /// \c Graph::NodeIt is defined. 655 int nodeNum() const { 656 int i=0; 657 for (NodeIt n(*this); n!=INVALID; ++n) ++i; 658 return i; 659 } 660 661 /// \warning This is a linear time operation and works only if 662 /// \c Graph::EdgeIt is defined. 663 int edgeNum() const { 664 int i=0; 665 for (EdgeIt e(*this); e!=INVALID; ++e) ++i; 666 return i; 667 } 668 669 // KEEP_MAPS(Parent, SubGraphWrapper); 670 }; 671 672 673 /*! \brief A wrapper for hiding edges from a graph. 674 675 \warning Graph wrappers are in even more experimental state than the other 676 parts of the lib. Use them at you own risk. 677 678 A wrapper for hiding edges from a graph. 679 This wrapper specializes SubGraphWrapper in the way that only the edgeset 680 can be filtered. 720 681 721 \author Marton Makai 682 722 */ 
src/test/graph_wrapper_test.cc
r921 r933 50 50 template void checkCompileStaticGraph<SubGW>(SubGW &); 51 51 52 //Compile NodeSubGraphWrapper 53 typedef NodeSubGraphWrapper<Graph, Graph::NodeMap<bool> > NodeSubGW; 54 template void checkCompileStaticGraph<NodeSubGW>(NodeSubGW &); 55 56 //Compile EdgeSubGraphWrapper 57 typedef EdgeSubGraphWrapper<Graph, Graph::EdgeMap<bool> > EdgeSubGW; 58 template void checkCompileStaticGraph<EdgeSubGW>(EdgeSubGW &); 59 52 60 //Compile UndirGraphWrapper 53 61 /// \bug UndirGraphWrapper cannot pass the StaticGraph test
Note: See TracChangeset
for help on using the changeset viewer.