366 1 |
366 1 |
367 \endcode |
367 \endcode |
368 Note that \c n is of type \c SubGW::NodeIt, but it can be converted to |
368 Note that \c n is of type \c SubGW::NodeIt, but it can be converted to |
369 \c Graph::Node that is why \c g.id(n) can be applied. |
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 |
371 For other examples see also the documentation of NodeSubGraphWrapper and |
372 of SubGraphWrapper is reasonable sure enough. If a shortest path is to be |
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 searched between two nodes \c s and \c t, then this can be done easily by |
613 searched between two nodes \c s and \c t, then this can be done easily by |
374 applying the Dijkstra algorithm class. What happens, if a maximum number of |
614 applying the Dijkstra algorithm class. What happens, if a maximum number of |
375 edge-disjoint shortest paths is to be computed. It can be proved that an |
615 edge-disjoint shortest paths is to be computed. It can be proved that an |
376 edge can be in a shortest path if and only if it is tight with respect to |
616 edge can be in a shortest path if and only if it is tight with respect to |
377 the potential function computed by Dijkstra. Moreover, any path containing |
617 the potential function computed by Dijkstra. Moreover, any path containing |
378 only such edges is a shortest one. Thus we have to compute a maximum number |
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-set |
619 of edge-disjoint paths between \c s and \c t in the graph which has edge-set |
380 all the tight edges. The computation will be demonstrated on the following |
620 all the tight edges. The computation will be demonstrated on the following |
381 graph, which is read from a dimacs file. |
621 graph, which is read from a dimacs file. |
382 |
622 |
383 \dot |
623 \dot |
384 digraph lemon_dot_example { |
624 digraph lemon_dot_example { |
475 7, 3--1->5 |
715 7, 3--1->5 |
476 4, 2--2->4 |
716 4, 2--2->4 |
477 2, 0--1->3 |
717 2, 0--1->3 |
478 1, 0--2->2 |
718 1, 0--2->2 |
479 \endcode |
719 \endcode |
480 \author Marton Makai |
720 |
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. |
|
681 \author Marton Makai |
721 \author Marton Makai |
682 */ |
722 */ |
683 template<typename Graph, typename EdgeFilterMap> |
723 template<typename Graph, typename EdgeFilterMap> |
684 class EdgeSubGraphWrapper : |
724 class EdgeSubGraphWrapper : |
685 public SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>, |
725 public SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>, |