Changeset 933:1b7c88fbb950 in lemon-0.x for src/lemon
- Timestamp:
- 10/01/04 13:31:03 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1258
- File:
-
- 1 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 node-map. 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 edge-map. 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 node-map 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 edge-map 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 node-set 574 can be filtered. Note that this does not mean of considering induced 575 subgraph, the edge-iterators consider the original edge-set. 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 edge-set 604 can be filtered. The usefulness of this wrapper is demonstrated in the 605 problem of searching a maximum number of edge-disjoint shortest paths 606 between 607 two nodes \c s and \c t. Shortest here means being shortest w.r.t. 608 non-negative edge-lengths. 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 edge-disjoint path between \c s and \c t in the graph which has edge-set619 of edge-disjoint paths between \c s and \c t in the graph which has edge-set 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, 0--2->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 node-map. 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 edge-map. 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 node-map 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 edge-map 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 edge-set 680 can be filtered. 720 681 721 \author Marton Makai 682 722 */
Note: See TracChangeset
for help on using the changeset viewer.