345 For other examples see also the documentation of NodeSubGraphWrapper and |
457 For other examples see also the documentation of NodeSubGraphWrapper and |
346 EdgeSubGraphWrapper. |
458 EdgeSubGraphWrapper. |
347 |
459 |
348 \author Marton Makai |
460 \author Marton Makai |
349 */ |
461 */ |
350 template<typename Graph, typename NodeFilterMap, |
462 template<typename _Graph, typename NodeFilterMap, |
351 typename EdgeFilterMap> |
463 typename EdgeFilterMap> |
352 class SubGraphWrapper : public GraphWrapper<Graph> { |
464 class SubGraphWrapper : |
353 public: |
465 public IterableGraphExtender< |
354 typedef GraphWrapper<Graph> Parent; |
466 SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > { |
|
467 public: |
|
468 typedef _Graph Graph; |
|
469 typedef IterableGraphExtender< |
|
470 SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent; |
355 protected: |
471 protected: |
356 NodeFilterMap* node_filter_map; |
472 SubGraphWrapper() { } |
357 EdgeFilterMap* edge_filter_map; |
473 public: |
358 |
474 SubGraphWrapper(_Graph& _graph, NodeFilterMap& _node_filter_map, |
359 SubGraphWrapper() : GraphWrapper<Graph>(), |
475 EdgeFilterMap& _edge_filter_map) { |
360 node_filter_map(0), edge_filter_map(0) { } |
476 setGraph(_graph); |
361 void setNodeFilterMap(NodeFilterMap& _node_filter_map) { |
477 setNodeFilterMap(_node_filter_map); |
362 node_filter_map=&_node_filter_map; |
478 setEdgeFilterMap(_edge_filter_map); |
363 } |
479 } |
364 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) { |
480 }; |
365 edge_filter_map=&_edge_filter_map; |
481 |
366 } |
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 // } |
367 |
499 |
368 public: |
500 // public: |
369 SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map, |
501 // SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map, |
370 EdgeFilterMap& _edge_filter_map) : |
502 // EdgeFilterMap& _edge_filter_map) : |
371 GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map), |
503 // GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map), |
372 edge_filter_map(&_edge_filter_map) { } |
504 // edge_filter_map(&_edge_filter_map) { } |
373 |
505 |
374 typedef typename GraphWrapper<Graph>::Node Node; |
506 // typedef typename GraphWrapper<Graph>::Node Node; |
375 class NodeIt : public Node { |
507 // class NodeIt : public Node { |
376 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw; |
508 // const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw; |
377 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; |
509 // friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; |
378 public: |
510 // public: |
379 NodeIt() { } |
511 // NodeIt() { } |
380 NodeIt(Invalid i) : Node(i) { } |
512 // NodeIt(Invalid i) : Node(i) { } |
381 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) : |
513 // NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) : |
382 Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { |
514 // Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) { |
383 while (*static_cast<Node*>(this)!=INVALID && |
515 // while (*static_cast<Node*>(this)!=INVALID && |
384 !(*(gw->node_filter_map))[*this]) |
516 // !(*(gw->node_filter_map))[*this]) |
385 *(static_cast<Node*>(this))= |
517 // *(static_cast<Node*>(this))= |
386 ++(typename Graph::NodeIt(*(gw->graph), *this)); |
518 // ++(typename Graph::NodeIt(*(gw->graph), *this)); |
387 } |
519 // } |
388 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, |
520 // NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, |
389 const Node& n) : |
521 // const Node& n) : |
390 Node(n), gw(&_gw) { } |
522 // Node(n), gw(&_gw) { } |
391 NodeIt& operator++() { |
523 // NodeIt& operator++() { |
392 *(static_cast<Node*>(this))= |
524 // *(static_cast<Node*>(this))= |
393 ++(typename Graph::NodeIt(*(gw->graph), *this)); |
525 // ++(typename Graph::NodeIt(*(gw->graph), *this)); |
394 while (*static_cast<Node*>(this)!=INVALID && |
526 // while (*static_cast<Node*>(this)!=INVALID && |
395 !(*(gw->node_filter_map))[*this]) |
527 // !(*(gw->node_filter_map))[*this]) |
396 *(static_cast<Node*>(this))= |
528 // *(static_cast<Node*>(this))= |
397 ++(typename Graph::NodeIt(*(gw->graph), *this)); |
529 // ++(typename Graph::NodeIt(*(gw->graph), *this)); |
398 return *this; |
530 // return *this; |
399 } |
531 // } |
400 }; |
532 // }; |
401 typedef typename GraphWrapper<Graph>::Edge Edge; |
533 // typedef typename GraphWrapper<Graph>::Edge Edge; |
402 class OutEdgeIt : public Edge { |
534 // class OutEdgeIt : public Edge { |
403 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw; |
535 // const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw; |
404 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; |
536 // friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; |
405 public: |
537 // public: |
406 OutEdgeIt() { } |
538 // OutEdgeIt() { } |
407 OutEdgeIt(Invalid i) : Edge(i) { } |
539 // OutEdgeIt(Invalid i) : Edge(i) { } |
408 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) : |
540 // OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) : |
409 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { |
541 // Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { |
410 while (*static_cast<Edge*>(this)!=INVALID && |
542 // while (*static_cast<Edge*>(this)!=INVALID && |
411 !(*(gw->edge_filter_map))[*this]) |
543 // !(*(gw->edge_filter_map))[*this]) |
412 *(static_cast<Edge*>(this))= |
544 // *(static_cast<Edge*>(this))= |
413 ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); |
545 // ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); |
414 } |
546 // } |
415 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, |
547 // OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, |
416 const Edge& e) : |
548 // const Edge& e) : |
417 Edge(e), gw(&_gw) { } |
549 // Edge(e), gw(&_gw) { } |
418 OutEdgeIt& operator++() { |
550 // OutEdgeIt& operator++() { |
419 *(static_cast<Edge*>(this))= |
551 // *(static_cast<Edge*>(this))= |
420 ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); |
552 // ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); |
421 while (*static_cast<Edge*>(this)!=INVALID && |
553 // while (*static_cast<Edge*>(this)!=INVALID && |
422 !(*(gw->edge_filter_map))[*this]) |
554 // !(*(gw->edge_filter_map))[*this]) |
423 *(static_cast<Edge*>(this))= |
555 // *(static_cast<Edge*>(this))= |
424 ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); |
556 // ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); |
425 return *this; |
557 // return *this; |
426 } |
558 // } |
427 }; |
559 // }; |
428 class InEdgeIt : public Edge { |
560 // class InEdgeIt : public Edge { |
429 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw; |
561 // const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw; |
430 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; |
562 // friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; |
431 public: |
563 // public: |
432 InEdgeIt() { } |
564 // InEdgeIt() { } |
433 // InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { } |
565 // // InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { } |
434 InEdgeIt(Invalid i) : Edge(i) { } |
566 // InEdgeIt(Invalid i) : Edge(i) { } |
435 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) : |
567 // InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) : |
436 Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { |
568 // Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { |
437 while (*static_cast<Edge*>(this)!=INVALID && |
569 // while (*static_cast<Edge*>(this)!=INVALID && |
438 !(*(gw->edge_filter_map))[*this]) |
570 // !(*(gw->edge_filter_map))[*this]) |
439 *(static_cast<Edge*>(this))= |
571 // *(static_cast<Edge*>(this))= |
440 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); |
572 // ++(typename Graph::InEdgeIt(*(gw->graph), *this)); |
441 } |
573 // } |
442 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, |
574 // InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, |
443 const Edge& e) : |
575 // const Edge& e) : |
444 Edge(e), gw(&_gw) { } |
576 // Edge(e), gw(&_gw) { } |
445 InEdgeIt& operator++() { |
577 // InEdgeIt& operator++() { |
446 *(static_cast<Edge*>(this))= |
578 // *(static_cast<Edge*>(this))= |
447 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); |
579 // ++(typename Graph::InEdgeIt(*(gw->graph), *this)); |
448 while (*static_cast<Edge*>(this)!=INVALID && |
580 // while (*static_cast<Edge*>(this)!=INVALID && |
449 !(*(gw->edge_filter_map))[*this]) |
581 // !(*(gw->edge_filter_map))[*this]) |
450 *(static_cast<Edge*>(this))= |
582 // *(static_cast<Edge*>(this))= |
451 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); |
583 // ++(typename Graph::InEdgeIt(*(gw->graph), *this)); |
452 return *this; |
584 // return *this; |
453 } |
585 // } |
454 }; |
586 // }; |
455 class EdgeIt : public Edge { |
587 // class EdgeIt : public Edge { |
456 const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw; |
588 // const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw; |
457 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; |
589 // friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; |
458 public: |
590 // public: |
459 EdgeIt() { } |
591 // EdgeIt() { } |
460 EdgeIt(Invalid i) : Edge(i) { } |
592 // EdgeIt(Invalid i) : Edge(i) { } |
461 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) : |
593 // EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) : |
462 Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { |
594 // Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) { |
463 while (*static_cast<Edge*>(this)!=INVALID && |
595 // while (*static_cast<Edge*>(this)!=INVALID && |
464 !(*(gw->edge_filter_map))[*this]) |
596 // !(*(gw->edge_filter_map))[*this]) |
465 *(static_cast<Edge*>(this))= |
597 // *(static_cast<Edge*>(this))= |
466 ++(typename Graph::EdgeIt(*(gw->graph), *this)); |
598 // ++(typename Graph::EdgeIt(*(gw->graph), *this)); |
467 } |
599 // } |
468 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, |
600 // EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, |
469 const Edge& e) : |
601 // const Edge& e) : |
470 Edge(e), gw(&_gw) { } |
602 // Edge(e), gw(&_gw) { } |
471 EdgeIt& operator++() { |
603 // EdgeIt& operator++() { |
472 *(static_cast<Edge*>(this))= |
604 // *(static_cast<Edge*>(this))= |
473 ++(typename Graph::EdgeIt(*(gw->graph), *this)); |
605 // ++(typename Graph::EdgeIt(*(gw->graph), *this)); |
474 while (*static_cast<Edge*>(this)!=INVALID && |
606 // while (*static_cast<Edge*>(this)!=INVALID && |
475 !(*(gw->edge_filter_map))[*this]) |
607 // !(*(gw->edge_filter_map))[*this]) |
476 *(static_cast<Edge*>(this))= |
608 // *(static_cast<Edge*>(this))= |
477 ++(typename Graph::EdgeIt(*(gw->graph), *this)); |
609 // ++(typename Graph::EdgeIt(*(gw->graph), *this)); |
478 return *this; |
610 // return *this; |
479 } |
611 // } |
480 }; |
612 // }; |
481 |
613 |
482 NodeIt& first(NodeIt& i) const { |
614 // NodeIt& first(NodeIt& i) const { |
483 i=NodeIt(*this); return i; |
615 // i=NodeIt(*this); return i; |
484 } |
616 // } |
485 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
617 // OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
486 i=OutEdgeIt(*this, p); return i; |
618 // i=OutEdgeIt(*this, p); return i; |
487 } |
619 // } |
488 InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
620 // InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
489 i=InEdgeIt(*this, p); return i; |
621 // i=InEdgeIt(*this, p); return i; |
490 } |
622 // } |
491 EdgeIt& first(EdgeIt& i) const { |
623 // EdgeIt& first(EdgeIt& i) const { |
492 i=EdgeIt(*this); return i; |
624 // i=EdgeIt(*this); return i; |
493 } |
625 // } |
494 |
626 |
495 /// This function hides \c n in the graph, i.e. the iteration |
627 // /// This function hides \c n in the graph, i.e. the iteration |
496 /// jumps over it. This is done by simply setting the value of \c n |
628 // /// jumps over it. This is done by simply setting the value of \c n |
497 /// to be false in the corresponding node-map. |
629 // /// to be false in the corresponding node-map. |
498 void hide(const Node& n) const { node_filter_map->set(n, false); } |
630 // void hide(const Node& n) const { node_filter_map->set(n, false); } |
499 |
631 |
500 /// This function hides \c e in the graph, i.e. the iteration |
632 // /// This function hides \c e in the graph, i.e. the iteration |
501 /// jumps over it. This is done by simply setting the value of \c e |
633 // /// jumps over it. This is done by simply setting the value of \c e |
502 /// to be false in the corresponding edge-map. |
634 // /// to be false in the corresponding edge-map. |
503 void hide(const Edge& e) const { edge_filter_map->set(e, false); } |
635 // void hide(const Edge& e) const { edge_filter_map->set(e, false); } |
504 |
636 |
505 /// The value of \c n is set to be true in the node-map which stores |
637 // /// The value of \c n is set to be true in the node-map which stores |
506 /// hide information. If \c n was hidden previuosly, then it is shown |
638 // /// hide information. If \c n was hidden previuosly, then it is shown |
507 /// again |
639 // /// again |
508 void unHide(const Node& n) const { node_filter_map->set(n, true); } |
640 // void unHide(const Node& n) const { node_filter_map->set(n, true); } |
509 |
641 |
510 /// The value of \c e is set to be true in the edge-map which stores |
642 // /// The value of \c e is set to be true in the edge-map which stores |
511 /// hide information. If \c e was hidden previuosly, then it is shown |
643 // /// hide information. If \c e was hidden previuosly, then it is shown |
512 /// again |
644 // /// again |
513 void unHide(const Edge& e) const { edge_filter_map->set(e, true); } |
645 // void unHide(const Edge& e) const { edge_filter_map->set(e, true); } |
514 |
646 |
515 /// Returns true if \c n is hidden. |
647 // /// Returns true if \c n is hidden. |
516 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; } |
648 // bool hidden(const Node& n) const { return !(*node_filter_map)[n]; } |
517 |
649 |
518 /// Returns true if \c n is hidden. |
650 // /// Returns true if \c n is hidden. |
519 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; } |
651 // bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; } |
520 |
652 |
521 /// \warning This is a linear time operation and works only if |
653 // /// \warning This is a linear time operation and works only if |
522 /// \c Graph::NodeIt is defined. |
654 // /// \c Graph::NodeIt is defined. |
523 int nodeNum() const { |
655 // int nodeNum() const { |
524 int i=0; |
656 // int i=0; |
525 for (NodeIt n(*this); n!=INVALID; ++n) ++i; |
657 // for (NodeIt n(*this); n!=INVALID; ++n) ++i; |
526 return i; |
658 // return i; |
527 } |
659 // } |
528 |
660 |
529 /// \warning This is a linear time operation and works only if |
661 // /// \warning This is a linear time operation and works only if |
530 /// \c Graph::EdgeIt is defined. |
662 // /// \c Graph::EdgeIt is defined. |
531 int edgeNum() const { |
663 // int edgeNum() const { |
532 int i=0; |
664 // int i=0; |
533 for (EdgeIt e(*this); e!=INVALID; ++e) ++i; |
665 // for (EdgeIt e(*this); e!=INVALID; ++e) ++i; |
534 return i; |
666 // return i; |
535 } |
667 // } |
536 |
668 |
537 // KEEP_MAPS(Parent, SubGraphWrapper); |
669 // // KEEP_MAPS(Parent, SubGraphWrapper); |
538 }; |
670 // }; |
539 |
671 |
540 |
672 |
541 /*! \brief A wrapper for hiding nodes from a graph. |
673 /*! \brief A wrapper for hiding nodes from a graph. |
542 |
674 |
543 \warning Graph wrappers are in even more experimental state than the other |
675 \warning Graph wrappers are in even more experimental state than the other |
797 } |
929 } |
798 |
930 |
799 // KEEP_MAPS(Parent, UndirGraph); |
931 // KEEP_MAPS(Parent, UndirGraph); |
800 }; |
932 }; |
801 |
933 |
|
934 |
|
935 template <typename _Graph, |
|
936 typename ForwardFilterMap, typename BackwardFilterMap> |
|
937 class SubBidirGraphWrapperBase : public GraphWrapperBase<_Graph> { |
|
938 public: |
|
939 typedef _Graph Graph; |
|
940 typedef GraphWrapperBase<_Graph> Parent; |
|
941 protected: |
|
942 ForwardFilterMap* forward_filter; |
|
943 BackwardFilterMap* backward_filter; |
|
944 SubBidirGraphWrapperBase() : Parent(), |
|
945 forward_filter(0), backward_filter(0) { } |
|
946 |
|
947 void setForwardFilterMap(ForwardFilterMap& _forward_filter) { |
|
948 forward_filter=&_forward_filter; |
|
949 } |
|
950 void setBackwardFilterMap(BackwardFilterMap& _backward_filter) { |
|
951 backward_filter=&_backward_filter; |
|
952 } |
|
953 |
|
954 public: |
|
955 // SubGraphWrapperBase(Graph& _graph, |
|
956 // NodeFilterMap& _node_filter_map, |
|
957 // EdgeFilterMap& _edge_filter_map) : |
|
958 // Parent(&_graph), |
|
959 // node_filter_map(&node_filter_map), |
|
960 // edge_filter_map(&edge_filter_map) { } |
|
961 |
|
962 typedef typename Parent::Node Node; |
|
963 typedef typename _Graph::Edge GraphEdge; |
|
964 template <typename T> class EdgeMap; |
|
965 /// SubBidirGraphWrapperBase<..., ..., ...>::Edge is inherited from |
|
966 /// _Graph::Edge. It contains an extra bool flag which is true |
|
967 /// if and only if the |
|
968 /// edge is the backward version of the original edge. |
|
969 class Edge : public _Graph::Edge { |
|
970 friend class SubBidirGraphWrapperBase< |
|
971 Graph, ForwardFilterMap, BackwardFilterMap>; |
|
972 template<typename T> friend class EdgeMap; |
|
973 protected: |
|
974 bool backward; //true, iff backward |
|
975 public: |
|
976 Edge() { } |
|
977 /// \todo =false is needed, or causes problems? |
|
978 /// If \c _backward is false, then we get an edge corresponding to the |
|
979 /// original one, otherwise its oppositely directed pair is obtained. |
|
980 Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) : |
|
981 _Graph::Edge(e), backward(_backward) { } |
|
982 Edge(Invalid i) : _Graph::Edge(i), backward(true) { } |
|
983 bool operator==(const Edge& v) const { |
|
984 return (this->backward==v.backward && |
|
985 static_cast<typename _Graph::Edge>(*this)== |
|
986 static_cast<typename _Graph::Edge>(v)); |
|
987 } |
|
988 bool operator!=(const Edge& v) const { |
|
989 return (this->backward!=v.backward || |
|
990 static_cast<typename _Graph::Edge>(*this)!= |
|
991 static_cast<typename _Graph::Edge>(v)); |
|
992 } |
|
993 }; |
|
994 |
|
995 void first(Node& i) const { |
|
996 Parent::first(i); |
|
997 } |
|
998 |
|
999 void first(Edge& i) const { |
|
1000 Parent::first(i); |
|
1001 i.backward=false; |
|
1002 while (*static_cast<GraphEdge*>(&i)!=INVALID && |
|
1003 !(*forward_filter)[i]) Parent::next(i); |
|
1004 if (*static_cast<GraphEdge*>(&i)==INVALID) { |
|
1005 Parent::first(i); |
|
1006 i.backward=true; |
|
1007 while (*static_cast<GraphEdge*>(&i)!=INVALID && |
|
1008 !(*backward_filter)[i]) Parent::next(i); |
|
1009 } |
|
1010 } |
|
1011 |
|
1012 void firstIn(Edge& i, const Node& n) const { |
|
1013 Parent::firstIn(i, n); |
|
1014 i.backward=false; |
|
1015 while (*static_cast<GraphEdge*>(&i)!=INVALID && |
|
1016 !(*forward_filter)[i]) Parent::nextOut(i); |
|
1017 if (*static_cast<GraphEdge*>(&i)==INVALID) { |
|
1018 Parent::firstOut(i, n); |
|
1019 i.backward=true; |
|
1020 while (*static_cast<GraphEdge*>(&i)!=INVALID && |
|
1021 !(*backward_filter)[i]) Parent::nextOut(i); |
|
1022 } |
|
1023 } |
|
1024 |
|
1025 void firstOut(Edge& i, const Node& n) const { |
|
1026 Parent::firstOut(i, n); |
|
1027 i.backward=false; |
|
1028 while (*static_cast<GraphEdge*>(&i)!=INVALID && |
|
1029 !(*forward_filter)[i]) Parent::nextOut(i); |
|
1030 if (*static_cast<GraphEdge*>(&i)==INVALID) { |
|
1031 Parent::firstIn(i, n); |
|
1032 i.backward=true; |
|
1033 while (*static_cast<GraphEdge*>(&i)!=INVALID && |
|
1034 !(*backward_filter)[i]) Parent::nextIn(i); |
|
1035 } |
|
1036 } |
|
1037 |
|
1038 void next(Node& i) const { |
|
1039 Parent::next(i); |
|
1040 } |
|
1041 |
|
1042 void next(Edge& i) const { |
|
1043 if (!(i.backward)) { |
|
1044 Parent::next(i); |
|
1045 while (*static_cast<GraphEdge*>(&i)!=INVALID && |
|
1046 !(*forward_filter)[i]) Parent::next(i); |
|
1047 if (*static_cast<GraphEdge*>(&i)==INVALID) { |
|
1048 Parent::first(i); |
|
1049 i.backward=true; |
|
1050 while (*static_cast<GraphEdge*>(&i)!=INVALID && |
|
1051 !(*backward_filter)[i]) Parent::next(i); |
|
1052 } |
|
1053 } else { |
|
1054 Parent::next(i); |
|
1055 while (*static_cast<GraphEdge*>(&i)!=INVALID && |
|
1056 !(*backward_filter)[i]) Parent::next(i); |
|
1057 } |
|
1058 } |
|
1059 |
|
1060 void nextIn(Edge& i) const { |
|
1061 if (!(i.backward)) { |
|
1062 Node n=Parent::target(i); |
|
1063 Parent::nextIn(i); |
|
1064 while (*static_cast<GraphEdge*>(&i)!=INVALID && |
|
1065 !(*forward_filter)[i]) Parent::nextIn(i); |
|
1066 if (*static_cast<GraphEdge*>(&i)==INVALID) { |
|
1067 Parent::firstOut(i, n); |
|
1068 i.backward=true; |
|
1069 while (*static_cast<GraphEdge*>(&i)!=INVALID && |
|
1070 !(*backward_filter)[i]) Parent::nextOut(i); |
|
1071 } |
|
1072 } else { |
|
1073 Parent::nextOut(i); |
|
1074 while (*static_cast<GraphEdge*>(&i)!=INVALID && |
|
1075 !(*backward_filter)[i]) Parent::nextOut(i); |
|
1076 } |
|
1077 } |
|
1078 |
|
1079 void nextOut(Edge& i) const { |
|
1080 if (!(i.backward)) { |
|
1081 Node n=Parent::source(i); |
|
1082 Parent::nextOut(i); |
|
1083 while (*static_cast<GraphEdge*>(&i)!=INVALID && |
|
1084 !(*forward_filter)[i]) Parent::nextOut(i); |
|
1085 if (*static_cast<GraphEdge*>(&i)==INVALID) { |
|
1086 Parent::firstIn(i, n); |
|
1087 i.backward=true; |
|
1088 while (*static_cast<GraphEdge*>(&i)!=INVALID && |
|
1089 !(*backward_filter)[i]) Parent::nextIn(i); |
|
1090 } |
|
1091 } else { |
|
1092 Parent::nextIn(i); |
|
1093 while (*static_cast<GraphEdge*>(&i)!=INVALID && |
|
1094 !(*backward_filter)[i]) Parent::nextIn(i); |
|
1095 } |
|
1096 } |
|
1097 |
|
1098 Node source(Edge e) const { |
|
1099 return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); } |
|
1100 Node target(Edge e) const { |
|
1101 return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); } |
|
1102 |
|
1103 /// Gives back the opposite edge. |
|
1104 Edge opposite(const Edge& e) const { |
|
1105 Edge f=e; |
|
1106 f.backward=!f.backward; |
|
1107 return f; |
|
1108 } |
|
1109 |
|
1110 /// \warning This is a linear time operation and works only if |
|
1111 /// \c Graph::EdgeIt is defined. |
|
1112 /// \todo hmm |
|
1113 int edgeNum() const { |
|
1114 int i=0; |
|
1115 Edge e; |
|
1116 for (first(e); e!=INVALID; next(e)) ++i; |
|
1117 return i; |
|
1118 } |
|
1119 |
|
1120 bool forward(const Edge& e) const { return !e.backward; } |
|
1121 bool backward(const Edge& e) const { return e.backward; } |
|
1122 |
|
1123 template <typename T> |
|
1124 /// \c SubBidirGraphWrapperBase<..., ..., ...>::EdgeMap contains two |
|
1125 /// _Graph::EdgeMap one for the forward edges and |
|
1126 /// one for the backward edges. |
|
1127 class EdgeMap { |
|
1128 template <typename TT> friend class EdgeMap; |
|
1129 typename _Graph::template EdgeMap<T> forward_map, backward_map; |
|
1130 public: |
|
1131 typedef T Value; |
|
1132 typedef Edge Key; |
|
1133 |
|
1134 EdgeMap(const SubBidirGraphWrapperBase<_Graph, |
|
1135 ForwardFilterMap, BackwardFilterMap>& g) : |
|
1136 forward_map(*(g.graph)), backward_map(*(g.graph)) { } |
|
1137 |
|
1138 EdgeMap(const SubBidirGraphWrapperBase<_Graph, |
|
1139 ForwardFilterMap, BackwardFilterMap>& g, T a) : |
|
1140 forward_map(*(g.graph), a), backward_map(*(g.graph), a) { } |
|
1141 |
|
1142 // template <typename TT> |
|
1143 // EdgeMap(const EdgeMap<TT>& copy) |
|
1144 // : forward_map(copy.forward_map), backward_map(copy.backward_map) {} |
|
1145 |
|
1146 // template <typename TT> |
|
1147 // EdgeMap& operator=(const EdgeMap<TT>& copy) { |
|
1148 // forward_map = copy.forward_map; |
|
1149 // backward_map = copy.backward_map; |
|
1150 // return *this; |
|
1151 // } |
|
1152 |
|
1153 void set(Edge e, T a) { |
|
1154 if (!e.backward) |
|
1155 forward_map.set(e, a); |
|
1156 else |
|
1157 backward_map.set(e, a); |
|
1158 } |
|
1159 |
|
1160 // typename _Graph::template EdgeMap<T>::ConstReference |
|
1161 // operator[](Edge e) const { |
|
1162 // if (!e.backward) |
|
1163 // return forward_map[e]; |
|
1164 // else |
|
1165 // return backward_map[e]; |
|
1166 // } |
|
1167 |
|
1168 // typename _Graph::template EdgeMap<T>::Reference |
|
1169 T operator[](Edge e) { |
|
1170 if (!e.backward) |
|
1171 return forward_map[e]; |
|
1172 else |
|
1173 return backward_map[e]; |
|
1174 } |
|
1175 |
|
1176 void update() { |
|
1177 forward_map.update(); |
|
1178 backward_map.update(); |
|
1179 } |
|
1180 }; |
|
1181 |
|
1182 }; |
802 |
1183 |
803 |
1184 |
804 ///\brief A wrapper for composing a subgraph of a |
1185 ///\brief A wrapper for composing a subgraph of a |
805 /// bidirected graph made from a directed one. |
1186 /// bidirected graph made from a directed one. |
806 /// |
1187 /// |
836 /// is ResGraphWrapper, which stands for the residual graph in directed |
1217 /// is ResGraphWrapper, which stands for the residual graph in directed |
837 /// flow and circulation problems. |
1218 /// flow and circulation problems. |
838 /// As wrappers usually, the SubBidirGraphWrapper implements the |
1219 /// As wrappers usually, the SubBidirGraphWrapper implements the |
839 /// above mentioned graph structure without its physical storage, |
1220 /// above mentioned graph structure without its physical storage, |
840 /// that is the whole stuff is stored in constant memory. |
1221 /// that is the whole stuff is stored in constant memory. |
841 template<typename Graph, |
1222 template<typename _Graph, |
842 typename ForwardFilterMap, typename BackwardFilterMap> |
1223 typename ForwardFilterMap, typename BackwardFilterMap> |
843 class SubBidirGraphWrapper : public GraphWrapper<Graph> { |
1224 class SubBidirGraphWrapper : |
844 public: |
1225 public IterableGraphExtender< |
845 typedef GraphWrapper<Graph> Parent; |
1226 SubBidirGraphWrapperBase<_Graph, ForwardFilterMap, BackwardFilterMap> > { |
|
1227 public: |
|
1228 typedef _Graph Graph; |
|
1229 typedef IterableGraphExtender< |
|
1230 SubBidirGraphWrapperBase< |
|
1231 _Graph, ForwardFilterMap, BackwardFilterMap> > Parent; |
846 protected: |
1232 protected: |
847 ForwardFilterMap* forward_filter; |
1233 SubBidirGraphWrapper() { } |
848 BackwardFilterMap* backward_filter; |
1234 public: |
849 |
1235 SubBidirGraphWrapper(_Graph& _graph, ForwardFilterMap& _forward_filter, |
850 SubBidirGraphWrapper() : GraphWrapper<Graph>() { } |
1236 BackwardFilterMap& _backward_filter) { |
851 void setForwardFilterMap(ForwardFilterMap& _forward_filter) { |
1237 setGraph(_graph); |
852 forward_filter=&_forward_filter; |
1238 setForwardFilterMap(_forward_filter); |
853 } |
1239 setBackwardFilterMap(_backward_filter); |
854 void setBackwardFilterMap(BackwardFilterMap& _backward_filter) { |
1240 } |
855 backward_filter=&_backward_filter; |
1241 }; |
856 } |
1242 |
857 |
1243 // template<typename Graph, |
858 public: |
1244 // typename ForwardFilterMap, typename BackwardFilterMap> |
859 |
1245 // class SubBidirGraphWrapper : public GraphWrapper<Graph> { |
860 SubBidirGraphWrapper(Graph& _graph, ForwardFilterMap& _forward_filter, |
1246 // public: |
861 BackwardFilterMap& _backward_filter) : |
1247 // typedef GraphWrapper<Graph> Parent; |
862 GraphWrapper<Graph>(_graph), |
1248 // protected: |
863 forward_filter(&_forward_filter), backward_filter(&_backward_filter) { } |
1249 // ForwardFilterMap* forward_filter; |
864 SubBidirGraphWrapper(const SubBidirGraphWrapper<Graph, |
1250 // BackwardFilterMap* backward_filter; |
865 ForwardFilterMap, BackwardFilterMap>& gw) : |
1251 |
866 Parent(gw), |
1252 // SubBidirGraphWrapper() : GraphWrapper<Graph>() { } |
867 forward_filter(gw.forward_filter), |
1253 // void setForwardFilterMap(ForwardFilterMap& _forward_filter) { |
868 backward_filter(gw.backward_filter) { } |
1254 // forward_filter=&_forward_filter; |
869 |
|
870 class Edge; |
|
871 class OutEdgeIt; |
|
872 friend class Edge; |
|
873 friend class OutEdgeIt; |
|
874 |
|
875 template<typename T> class EdgeMap; |
|
876 |
|
877 typedef typename GraphWrapper<Graph>::Node Node; |
|
878 |
|
879 typedef typename Graph::Edge GraphEdge; |
|
880 /// SubBidirGraphWrapper<..., ..., ...>::Edge is inherited from |
|
881 /// Graph::Edge. It contains an extra bool flag which is true |
|
882 /// if and only if the |
|
883 /// edge is the backward version of the original edge. |
|
884 class Edge : public Graph::Edge { |
|
885 friend class SubBidirGraphWrapper<Graph, |
|
886 ForwardFilterMap, BackwardFilterMap>; |
|
887 template<typename T> friend class EdgeMap; |
|
888 protected: |
|
889 bool backward; //true, iff backward |
|
890 public: |
|
891 Edge() { } |
|
892 /// \todo =false is needed, or causes problems? |
|
893 /// If \c _backward is false, then we get an edge corresponding to the |
|
894 /// original one, otherwise its oppositely directed pair is obtained. |
|
895 Edge(const typename Graph::Edge& e, bool _backward/*=false*/) : |
|
896 Graph::Edge(e), backward(_backward) { } |
|
897 Edge(Invalid i) : Graph::Edge(i), backward(true) { } |
|
898 bool operator==(const Edge& v) const { |
|
899 return (this->backward==v.backward && |
|
900 static_cast<typename Graph::Edge>(*this)== |
|
901 static_cast<typename Graph::Edge>(v)); |
|
902 } |
|
903 bool operator!=(const Edge& v) const { |
|
904 return (this->backward!=v.backward || |
|
905 static_cast<typename Graph::Edge>(*this)!= |
|
906 static_cast<typename Graph::Edge>(v)); |
|
907 } |
|
908 }; |
|
909 |
|
910 class OutEdgeIt : public Edge { |
|
911 friend class SubBidirGraphWrapper<Graph, |
|
912 ForwardFilterMap, BackwardFilterMap>; |
|
913 protected: |
|
914 const SubBidirGraphWrapper<Graph, |
|
915 ForwardFilterMap, BackwardFilterMap>* gw; |
|
916 public: |
|
917 OutEdgeIt() { } |
|
918 OutEdgeIt(Invalid i) : Edge(i) { } |
|
919 OutEdgeIt(const SubBidirGraphWrapper<Graph, |
|
920 ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) : |
|
921 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) { |
|
922 while (*static_cast<GraphEdge*>(this)!=INVALID && |
|
923 !(*(gw->forward_filter))[*this]) |
|
924 *(static_cast<GraphEdge*>(this))= |
|
925 ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); |
|
926 if (*static_cast<GraphEdge*>(this)==INVALID) { |
|
927 *static_cast<Edge*>(this)= |
|
928 Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true); |
|
929 while (*static_cast<GraphEdge*>(this)!=INVALID && |
|
930 !(*(gw->backward_filter))[*this]) |
|
931 *(static_cast<GraphEdge*>(this))= |
|
932 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); |
|
933 } |
|
934 } |
|
935 OutEdgeIt(const SubBidirGraphWrapper<Graph, |
|
936 ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) : |
|
937 Edge(e), gw(&_gw) { } |
|
938 OutEdgeIt& operator++() { |
|
939 if (!this->backward) { |
|
940 Node n=gw->source(*this); |
|
941 *(static_cast<GraphEdge*>(this))= |
|
942 ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); |
|
943 while (*static_cast<GraphEdge*>(this)!=INVALID && |
|
944 !(*(gw->forward_filter))[*this]) |
|
945 *(static_cast<GraphEdge*>(this))= |
|
946 ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); |
|
947 if (*static_cast<GraphEdge*>(this)==INVALID) { |
|
948 *static_cast<Edge*>(this)= |
|
949 Edge(typename Graph::InEdgeIt(*(gw->graph), n), true); |
|
950 while (*static_cast<GraphEdge*>(this)!=INVALID && |
|
951 !(*(gw->backward_filter))[*this]) |
|
952 *(static_cast<GraphEdge*>(this))= |
|
953 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); |
|
954 } |
|
955 } else { |
|
956 *(static_cast<GraphEdge*>(this))= |
|
957 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); |
|
958 while (*static_cast<GraphEdge*>(this)!=INVALID && |
|
959 !(*(gw->backward_filter))[*this]) |
|
960 *(static_cast<GraphEdge*>(this))= |
|
961 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); |
|
962 } |
|
963 return *this; |
|
964 } |
|
965 }; |
|
966 |
|
967 class InEdgeIt : public Edge { |
|
968 friend class SubBidirGraphWrapper<Graph, |
|
969 ForwardFilterMap, BackwardFilterMap>; |
|
970 protected: |
|
971 const SubBidirGraphWrapper<Graph, |
|
972 ForwardFilterMap, BackwardFilterMap>* gw; |
|
973 public: |
|
974 InEdgeIt() { } |
|
975 InEdgeIt(Invalid i) : Edge(i) { } |
|
976 InEdgeIt(const SubBidirGraphWrapper<Graph, |
|
977 ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) : |
|
978 Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) { |
|
979 while (*static_cast<GraphEdge*>(this)!=INVALID && |
|
980 !(*(gw->forward_filter))[*this]) |
|
981 *(static_cast<GraphEdge*>(this))= |
|
982 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); |
|
983 if (*static_cast<GraphEdge*>(this)==INVALID) { |
|
984 *static_cast<Edge*>(this)= |
|
985 Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true); |
|
986 while (*static_cast<GraphEdge*>(this)!=INVALID && |
|
987 !(*(gw->backward_filter))[*this]) |
|
988 *(static_cast<GraphEdge*>(this))= |
|
989 ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); |
|
990 } |
|
991 } |
|
992 InEdgeIt(const SubBidirGraphWrapper<Graph, |
|
993 ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) : |
|
994 Edge(e), gw(&_gw) { } |
|
995 InEdgeIt& operator++() { |
|
996 if (!this->backward) { |
|
997 Node n=gw->source(*this); |
|
998 *(static_cast<GraphEdge*>(this))= |
|
999 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); |
|
1000 while (*static_cast<GraphEdge*>(this)!=INVALID && |
|
1001 !(*(gw->forward_filter))[*this]) |
|
1002 *(static_cast<GraphEdge*>(this))= |
|
1003 ++(typename Graph::InEdgeIt(*(gw->graph), *this)); |
|
1004 if (*static_cast<GraphEdge*>(this)==INVALID) { |
|
1005 *static_cast<Edge*>(this)= |
|
1006 Edge(typename Graph::OutEdgeIt(*(gw->graph), n), true); |
|
1007 while (*static_cast<GraphEdge*>(this)!=INVALID && |
|
1008 !(*(gw->backward_filter))[*this]) |
|
1009 *(static_cast<GraphEdge*>(this))= |
|
1010 ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); |
|
1011 } |
|
1012 } else { |
|
1013 *(static_cast<GraphEdge*>(this))= |
|
1014 ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); |
|
1015 while (*static_cast<GraphEdge*>(this)!=INVALID && |
|
1016 !(*(gw->backward_filter))[*this]) |
|
1017 *(static_cast<GraphEdge*>(this))= |
|
1018 ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); |
|
1019 } |
|
1020 return *this; |
|
1021 } |
|
1022 }; |
|
1023 |
|
1024 class EdgeIt : public Edge { |
|
1025 friend class SubBidirGraphWrapper<Graph, |
|
1026 ForwardFilterMap, BackwardFilterMap>; |
|
1027 protected: |
|
1028 const SubBidirGraphWrapper<Graph, |
|
1029 ForwardFilterMap, BackwardFilterMap>* gw; |
|
1030 public: |
|
1031 EdgeIt() { } |
|
1032 EdgeIt(Invalid i) : Edge(i) { } |
|
1033 EdgeIt(const SubBidirGraphWrapper<Graph, |
|
1034 ForwardFilterMap, BackwardFilterMap>& _gw) : |
|
1035 Edge(typename Graph::EdgeIt(*(_gw.graph)), false), gw(&_gw) { |
|
1036 while (*static_cast<GraphEdge*>(this)!=INVALID && |
|
1037 !(*(gw->forward_filter))[*this]) |
|
1038 *(static_cast<GraphEdge*>(this))= |
|
1039 ++(typename Graph::EdgeIt(*(gw->graph), *this)); |
|
1040 if (*static_cast<GraphEdge*>(this)==INVALID) { |
|
1041 *static_cast<Edge*>(this)= |
|
1042 Edge(typename Graph::EdgeIt(*(_gw.graph)), true); |
|
1043 while (*static_cast<GraphEdge*>(this)!=INVALID && |
|
1044 !(*(gw->backward_filter))[*this]) |
|
1045 *(static_cast<GraphEdge*>(this))= |
|
1046 ++(typename Graph::EdgeIt(*(gw->graph), *this)); |
|
1047 } |
|
1048 } |
|
1049 EdgeIt(const SubBidirGraphWrapper<Graph, |
|
1050 ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) : |
|
1051 Edge(e), gw(&_gw) { } |
|
1052 EdgeIt& operator++() { |
|
1053 if (!this->backward) { |
|
1054 *(static_cast<GraphEdge*>(this))= |
|
1055 ++(typename Graph::EdgeIt(*(gw->graph), *this)); |
|
1056 while (*static_cast<GraphEdge*>(this)!=INVALID && |
|
1057 !(*(gw->forward_filter))[*this]) |
|
1058 *(static_cast<GraphEdge*>(this))= |
|
1059 ++(typename Graph::EdgeIt(*(gw->graph), *this)); |
|
1060 if (*static_cast<GraphEdge*>(this)==INVALID) { |
|
1061 *static_cast<Edge*>(this)= |
|
1062 Edge(typename Graph::EdgeIt(*(gw->graph)), true); |
|
1063 while (*static_cast<GraphEdge*>(this)!=INVALID && |
|
1064 !(*(gw->backward_filter))[*this]) |
|
1065 *(static_cast<GraphEdge*>(this))= |
|
1066 ++(typename Graph::EdgeIt(*(gw->graph), *this)); |
|
1067 } |
|
1068 } else { |
|
1069 *(static_cast<GraphEdge*>(this))= |
|
1070 ++(typename Graph::EdgeIt(*(gw->graph), *this)); |
|
1071 while (*static_cast<GraphEdge*>(this)!=INVALID && |
|
1072 !(*(gw->backward_filter))[*this]) |
|
1073 *(static_cast<GraphEdge*>(this))= |
|
1074 ++(typename Graph::EdgeIt(*(gw->graph), *this)); |
|
1075 } |
|
1076 return *this; |
|
1077 } |
|
1078 }; |
|
1079 |
|
1080 // using GraphWrapper<Graph>::first; |
|
1081 // OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
|
1082 // i=OutEdgeIt(*this, p); return i; |
|
1083 // } |
1255 // } |
1084 // InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
1256 // void setBackwardFilterMap(BackwardFilterMap& _backward_filter) { |
1085 // i=InEdgeIt(*this, p); return i; |
1257 // backward_filter=&_backward_filter; |
1086 // } |
1258 // } |
1087 // EdgeIt& first(EdgeIt& i) const { |
1259 |
1088 // i=EdgeIt(*this); return i; |
1260 // public: |
|
1261 |
|
1262 // SubBidirGraphWrapper(Graph& _graph, ForwardFilterMap& _forward_filter, |
|
1263 // BackwardFilterMap& _backward_filter) : |
|
1264 // GraphWrapper<Graph>(_graph), |
|
1265 // forward_filter(&_forward_filter), backward_filter(&_backward_filter) { } |
|
1266 // SubBidirGraphWrapper(const SubBidirGraphWrapper<Graph, |
|
1267 // ForwardFilterMap, BackwardFilterMap>& gw) : |
|
1268 // Parent(gw), |
|
1269 // forward_filter(gw.forward_filter), |
|
1270 // backward_filter(gw.backward_filter) { } |
|
1271 |
|
1272 // class Edge; |
|
1273 // class OutEdgeIt; |
|
1274 // friend class Edge; |
|
1275 // friend class OutEdgeIt; |
|
1276 |
|
1277 // template<typename T> class EdgeMap; |
|
1278 |
|
1279 // typedef typename GraphWrapper<Graph>::Node Node; |
|
1280 |
|
1281 // typedef typename Graph::Edge GraphEdge; |
|
1282 // /// SubBidirGraphWrapper<..., ..., ...>::Edge is inherited from |
|
1283 // /// Graph::Edge. It contains an extra bool flag which is true |
|
1284 // /// if and only if the |
|
1285 // /// edge is the backward version of the original edge. |
|
1286 // class Edge : public Graph::Edge { |
|
1287 // friend class SubBidirGraphWrapper<Graph, |
|
1288 // ForwardFilterMap, BackwardFilterMap>; |
|
1289 // template<typename T> friend class EdgeMap; |
|
1290 // protected: |
|
1291 // bool backward; //true, iff backward |
|
1292 // public: |
|
1293 // Edge() { } |
|
1294 // /// \todo =false is needed, or causes problems? |
|
1295 // /// If \c _backward is false, then we get an edge corresponding to the |
|
1296 // /// original one, otherwise its oppositely directed pair is obtained. |
|
1297 // Edge(const typename Graph::Edge& e, bool _backward/*=false*/) : |
|
1298 // Graph::Edge(e), backward(_backward) { } |
|
1299 // Edge(Invalid i) : Graph::Edge(i), backward(true) { } |
|
1300 // bool operator==(const Edge& v) const { |
|
1301 // return (this->backward==v.backward && |
|
1302 // static_cast<typename Graph::Edge>(*this)== |
|
1303 // static_cast<typename Graph::Edge>(v)); |
|
1304 // } |
|
1305 // bool operator!=(const Edge& v) const { |
|
1306 // return (this->backward!=v.backward || |
|
1307 // static_cast<typename Graph::Edge>(*this)!= |
|
1308 // static_cast<typename Graph::Edge>(v)); |
|
1309 // } |
|
1310 // }; |
|
1311 |
|
1312 // class OutEdgeIt : public Edge { |
|
1313 // friend class SubBidirGraphWrapper<Graph, |
|
1314 // ForwardFilterMap, BackwardFilterMap>; |
|
1315 // protected: |
|
1316 // const SubBidirGraphWrapper<Graph, |
|
1317 // ForwardFilterMap, BackwardFilterMap>* gw; |
|
1318 // public: |
|
1319 // OutEdgeIt() { } |
|
1320 // OutEdgeIt(Invalid i) : Edge(i) { } |
|
1321 // OutEdgeIt(const SubBidirGraphWrapper<Graph, |
|
1322 // ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) : |
|
1323 // Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) { |
|
1324 // while (*static_cast<GraphEdge*>(this)!=INVALID && |
|
1325 // !(*(gw->forward_filter))[*this]) |
|
1326 // *(static_cast<GraphEdge*>(this))= |
|
1327 // ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); |
|
1328 // if (*static_cast<GraphEdge*>(this)==INVALID) { |
|
1329 // *static_cast<Edge*>(this)= |
|
1330 // Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true); |
|
1331 // while (*static_cast<GraphEdge*>(this)!=INVALID && |
|
1332 // !(*(gw->backward_filter))[*this]) |
|
1333 // *(static_cast<GraphEdge*>(this))= |
|
1334 // ++(typename Graph::InEdgeIt(*(gw->graph), *this)); |
|
1335 // } |
|
1336 // } |
|
1337 // OutEdgeIt(const SubBidirGraphWrapper<Graph, |
|
1338 // ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) : |
|
1339 // Edge(e), gw(&_gw) { } |
|
1340 // OutEdgeIt& operator++() { |
|
1341 // if (!this->backward) { |
|
1342 // Node n=gw->source(*this); |
|
1343 // *(static_cast<GraphEdge*>(this))= |
|
1344 // ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); |
|
1345 // while (*static_cast<GraphEdge*>(this)!=INVALID && |
|
1346 // !(*(gw->forward_filter))[*this]) |
|
1347 // *(static_cast<GraphEdge*>(this))= |
|
1348 // ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); |
|
1349 // if (*static_cast<GraphEdge*>(this)==INVALID) { |
|
1350 // *static_cast<Edge*>(this)= |
|
1351 // Edge(typename Graph::InEdgeIt(*(gw->graph), n), true); |
|
1352 // while (*static_cast<GraphEdge*>(this)!=INVALID && |
|
1353 // !(*(gw->backward_filter))[*this]) |
|
1354 // *(static_cast<GraphEdge*>(this))= |
|
1355 // ++(typename Graph::InEdgeIt(*(gw->graph), *this)); |
|
1356 // } |
|
1357 // } else { |
|
1358 // *(static_cast<GraphEdge*>(this))= |
|
1359 // ++(typename Graph::InEdgeIt(*(gw->graph), *this)); |
|
1360 // while (*static_cast<GraphEdge*>(this)!=INVALID && |
|
1361 // !(*(gw->backward_filter))[*this]) |
|
1362 // *(static_cast<GraphEdge*>(this))= |
|
1363 // ++(typename Graph::InEdgeIt(*(gw->graph), *this)); |
|
1364 // } |
|
1365 // return *this; |
|
1366 // } |
|
1367 // }; |
|
1368 |
|
1369 // class InEdgeIt : public Edge { |
|
1370 // friend class SubBidirGraphWrapper<Graph, |
|
1371 // ForwardFilterMap, BackwardFilterMap>; |
|
1372 // protected: |
|
1373 // const SubBidirGraphWrapper<Graph, |
|
1374 // ForwardFilterMap, BackwardFilterMap>* gw; |
|
1375 // public: |
|
1376 // InEdgeIt() { } |
|
1377 // InEdgeIt(Invalid i) : Edge(i) { } |
|
1378 // InEdgeIt(const SubBidirGraphWrapper<Graph, |
|
1379 // ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) : |
|
1380 // Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) { |
|
1381 // while (*static_cast<GraphEdge*>(this)!=INVALID && |
|
1382 // !(*(gw->forward_filter))[*this]) |
|
1383 // *(static_cast<GraphEdge*>(this))= |
|
1384 // ++(typename Graph::InEdgeIt(*(gw->graph), *this)); |
|
1385 // if (*static_cast<GraphEdge*>(this)==INVALID) { |
|
1386 // *static_cast<Edge*>(this)= |
|
1387 // Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true); |
|
1388 // while (*static_cast<GraphEdge*>(this)!=INVALID && |
|
1389 // !(*(gw->backward_filter))[*this]) |
|
1390 // *(static_cast<GraphEdge*>(this))= |
|
1391 // ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); |
|
1392 // } |
|
1393 // } |
|
1394 // InEdgeIt(const SubBidirGraphWrapper<Graph, |
|
1395 // ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) : |
|
1396 // Edge(e), gw(&_gw) { } |
|
1397 // InEdgeIt& operator++() { |
|
1398 // if (!this->backward) { |
|
1399 // Node n=gw->source(*this); |
|
1400 // *(static_cast<GraphEdge*>(this))= |
|
1401 // ++(typename Graph::InEdgeIt(*(gw->graph), *this)); |
|
1402 // while (*static_cast<GraphEdge*>(this)!=INVALID && |
|
1403 // !(*(gw->forward_filter))[*this]) |
|
1404 // *(static_cast<GraphEdge*>(this))= |
|
1405 // ++(typename Graph::InEdgeIt(*(gw->graph), *this)); |
|
1406 // if (*static_cast<GraphEdge*>(this)==INVALID) { |
|
1407 // *static_cast<Edge*>(this)= |
|
1408 // Edge(typename Graph::OutEdgeIt(*(gw->graph), n), true); |
|
1409 // while (*static_cast<GraphEdge*>(this)!=INVALID && |
|
1410 // !(*(gw->backward_filter))[*this]) |
|
1411 // *(static_cast<GraphEdge*>(this))= |
|
1412 // ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); |
|
1413 // } |
|
1414 // } else { |
|
1415 // *(static_cast<GraphEdge*>(this))= |
|
1416 // ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); |
|
1417 // while (*static_cast<GraphEdge*>(this)!=INVALID && |
|
1418 // !(*(gw->backward_filter))[*this]) |
|
1419 // *(static_cast<GraphEdge*>(this))= |
|
1420 // ++(typename Graph::OutEdgeIt(*(gw->graph), *this)); |
|
1421 // } |
|
1422 // return *this; |
|
1423 // } |
|
1424 // }; |
|
1425 |
|
1426 // class EdgeIt : public Edge { |
|
1427 // friend class SubBidirGraphWrapper<Graph, |
|
1428 // ForwardFilterMap, BackwardFilterMap>; |
|
1429 // protected: |
|
1430 // const SubBidirGraphWrapper<Graph, |
|
1431 // ForwardFilterMap, BackwardFilterMap>* gw; |
|
1432 // public: |
|
1433 // EdgeIt() { } |
|
1434 // EdgeIt(Invalid i) : Edge(i) { } |
|
1435 // EdgeIt(const SubBidirGraphWrapper<Graph, |
|
1436 // ForwardFilterMap, BackwardFilterMap>& _gw) : |
|
1437 // Edge(typename Graph::EdgeIt(*(_gw.graph)), false), gw(&_gw) { |
|
1438 // while (*static_cast<GraphEdge*>(this)!=INVALID && |
|
1439 // !(*(gw->forward_filter))[*this]) |
|
1440 // *(static_cast<GraphEdge*>(this))= |
|
1441 // ++(typename Graph::EdgeIt(*(gw->graph), *this)); |
|
1442 // if (*static_cast<GraphEdge*>(this)==INVALID) { |
|
1443 // *static_cast<Edge*>(this)= |
|
1444 // Edge(typename Graph::EdgeIt(*(_gw.graph)), true); |
|
1445 // while (*static_cast<GraphEdge*>(this)!=INVALID && |
|
1446 // !(*(gw->backward_filter))[*this]) |
|
1447 // *(static_cast<GraphEdge*>(this))= |
|
1448 // ++(typename Graph::EdgeIt(*(gw->graph), *this)); |
|
1449 // } |
|
1450 // } |
|
1451 // EdgeIt(const SubBidirGraphWrapper<Graph, |
|
1452 // ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) : |
|
1453 // Edge(e), gw(&_gw) { } |
|
1454 // EdgeIt& operator++() { |
|
1455 // if (!this->backward) { |
|
1456 // *(static_cast<GraphEdge*>(this))= |
|
1457 // ++(typename Graph::EdgeIt(*(gw->graph), *this)); |
|
1458 // while (*static_cast<GraphEdge*>(this)!=INVALID && |
|
1459 // !(*(gw->forward_filter))[*this]) |
|
1460 // *(static_cast<GraphEdge*>(this))= |
|
1461 // ++(typename Graph::EdgeIt(*(gw->graph), *this)); |
|
1462 // if (*static_cast<GraphEdge*>(this)==INVALID) { |
|
1463 // *static_cast<Edge*>(this)= |
|
1464 // Edge(typename Graph::EdgeIt(*(gw->graph)), true); |
|
1465 // while (*static_cast<GraphEdge*>(this)!=INVALID && |
|
1466 // !(*(gw->backward_filter))[*this]) |
|
1467 // *(static_cast<GraphEdge*>(this))= |
|
1468 // ++(typename Graph::EdgeIt(*(gw->graph), *this)); |
|
1469 // } |
|
1470 // } else { |
|
1471 // *(static_cast<GraphEdge*>(this))= |
|
1472 // ++(typename Graph::EdgeIt(*(gw->graph), *this)); |
|
1473 // while (*static_cast<GraphEdge*>(this)!=INVALID && |
|
1474 // !(*(gw->backward_filter))[*this]) |
|
1475 // *(static_cast<GraphEdge*>(this))= |
|
1476 // ++(typename Graph::EdgeIt(*(gw->graph), *this)); |
|
1477 // } |
|
1478 // return *this; |
|
1479 // } |
|
1480 // }; |
|
1481 |
|
1482 // // using GraphWrapper<Graph>::first; |
|
1483 // // OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { |
|
1484 // // i=OutEdgeIt(*this, p); return i; |
|
1485 // // } |
|
1486 // // InEdgeIt& first(InEdgeIt& i, const Node& p) const { |
|
1487 // // i=InEdgeIt(*this, p); return i; |
|
1488 // // } |
|
1489 // // EdgeIt& first(EdgeIt& i) const { |
|
1490 // // i=EdgeIt(*this); return i; |
|
1491 // // } |
|
1492 |
|
1493 |
|
1494 // Node source(Edge e) const { |
|
1495 // return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); } |
|
1496 // Node target(Edge e) const { |
|
1497 // return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); } |
|
1498 |
|
1499 // /// Gives back the opposite edge. |
|
1500 // Edge opposite(const Edge& e) const { |
|
1501 // Edge f=e; |
|
1502 // f.backward=!f.backward; |
|
1503 // return f; |
1089 // } |
1504 // } |
1090 |
1505 |
1091 |
1506 // /// \warning This is a linear time operation and works only if |
1092 Node source(Edge e) const { |
1507 // /// \c Graph::EdgeIt is defined. |
1093 return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); } |
1508 // int edgeNum() const { |
1094 Node target(Edge e) const { |
1509 // int i=0; |
1095 return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); } |
1510 // for (EdgeIt e(*this); e!=INVALID; ++e) ++i; |
1096 |
1511 // return i; |
1097 /// Gives back the opposite edge. |
1512 // } |
1098 Edge opposite(const Edge& e) const { |
1513 |
1099 Edge f=e; |
1514 // bool forward(const Edge& e) const { return !e.backward; } |
1100 f.backward=!f.backward; |
1515 // bool backward(const Edge& e) const { return e.backward; } |
1101 return f; |
1516 |
1102 } |
1517 |
1103 |
1518 // template <typename T> |
1104 /// \warning This is a linear time operation and works only if |
1519 // /// \c SubBidirGraphWrapper<..., ..., ...>::EdgeMap contains two |
1105 /// \c Graph::EdgeIt is defined. |
1520 // /// Graph::EdgeMap one for the forward edges and |
1106 int edgeNum() const { |
1521 // /// one for the backward edges. |
1107 int i=0; |
1522 // class EdgeMap { |
1108 for (EdgeIt e(*this); e!=INVALID; ++e) ++i; |
1523 // template <typename TT> friend class EdgeMap; |
1109 return i; |
1524 // typename Graph::template EdgeMap<T> forward_map, backward_map; |
1110 } |
1525 // public: |
1111 |
1526 // typedef T Value; |
1112 bool forward(const Edge& e) const { return !e.backward; } |
1527 // typedef Edge Key; |
1113 bool backward(const Edge& e) const { return e.backward; } |
1528 |
1114 |
1529 // EdgeMap(const SubBidirGraphWrapper<Graph, |
1115 |
1530 // ForwardFilterMap, BackwardFilterMap>& g) : |
1116 template <typename T> |
1531 // forward_map(*(g.graph)), backward_map(*(g.graph)) { } |
1117 /// \c SubBidirGraphWrapper<..., ..., ...>::EdgeMap contains two |
1532 |
1118 /// Graph::EdgeMap one for the forward edges and |
1533 // EdgeMap(const SubBidirGraphWrapper<Graph, |
1119 /// one for the backward edges. |
1534 // ForwardFilterMap, BackwardFilterMap>& g, T a) : |
1120 class EdgeMap { |
1535 // forward_map(*(g.graph), a), backward_map(*(g.graph), a) { } |
1121 template <typename TT> friend class EdgeMap; |
1536 |
1122 typename Graph::template EdgeMap<T> forward_map, backward_map; |
1537 // template <typename TT> |
1123 public: |
1538 // EdgeMap(const EdgeMap<TT>& copy) |
1124 typedef T Value; |
1539 // : forward_map(copy.forward_map), backward_map(copy.backward_map) {} |
1125 typedef Edge Key; |
1540 |
1126 |
1541 // template <typename TT> |
1127 EdgeMap(const SubBidirGraphWrapper<Graph, |
1542 // EdgeMap& operator=(const EdgeMap<TT>& copy) { |
1128 ForwardFilterMap, BackwardFilterMap>& g) : |
1543 // forward_map = copy.forward_map; |
1129 forward_map(*(g.graph)), backward_map(*(g.graph)) { } |
1544 // backward_map = copy.backward_map; |
1130 |
1545 // return *this; |
1131 EdgeMap(const SubBidirGraphWrapper<Graph, |
1546 // } |
1132 ForwardFilterMap, BackwardFilterMap>& g, T a) : |
|
1133 forward_map(*(g.graph), a), backward_map(*(g.graph), a) { } |
|
1134 |
|
1135 template <typename TT> |
|
1136 EdgeMap(const EdgeMap<TT>& copy) |
|
1137 : forward_map(copy.forward_map), backward_map(copy.backward_map) {} |
|
1138 |
|
1139 template <typename TT> |
|
1140 EdgeMap& operator=(const EdgeMap<TT>& copy) { |
|
1141 forward_map = copy.forward_map; |
|
1142 backward_map = copy.backward_map; |
|
1143 return *this; |
|
1144 } |
|
1145 |
1547 |
1146 void set(Edge e, T a) { |
1548 // void set(Edge e, T a) { |
1147 if (!e.backward) |
1549 // if (!e.backward) |
1148 forward_map.set(e, a); |
1550 // forward_map.set(e, a); |
1149 else |
1551 // else |
1150 backward_map.set(e, a); |
1552 // backward_map.set(e, a); |
1151 } |
1553 // } |
1152 |
1554 |
1153 typename Graph::template EdgeMap<T>::ConstReference |
1555 // typename Graph::template EdgeMap<T>::ConstReference |
1154 operator[](Edge e) const { |
1556 // operator[](Edge e) const { |
1155 if (!e.backward) |
1557 // if (!e.backward) |
1156 return forward_map[e]; |
1558 // return forward_map[e]; |
1157 else |
1559 // else |
1158 return backward_map[e]; |
1560 // return backward_map[e]; |
1159 } |
1561 // } |
1160 |
1562 |
1161 typename Graph::template EdgeMap<T>::Reference |
1563 // typename Graph::template EdgeMap<T>::Reference |
1162 operator[](Edge e) { |
1564 // operator[](Edge e) { |
1163 if (!e.backward) |
1565 // if (!e.backward) |
1164 return forward_map[e]; |
1566 // return forward_map[e]; |
1165 else |
1567 // else |
1166 return backward_map[e]; |
1568 // return backward_map[e]; |
1167 } |
1569 // } |
1168 |
1570 |
1169 void update() { |
1571 // void update() { |
1170 forward_map.update(); |
1572 // forward_map.update(); |
1171 backward_map.update(); |
1573 // backward_map.update(); |
1172 } |
1574 // } |
1173 }; |
1575 // }; |
1174 |
1576 |
1175 |
1577 |
1176 // KEEP_NODE_MAP(Parent, SubBidirGraphWrapper); |
1578 // // KEEP_NODE_MAP(Parent, SubBidirGraphWrapper); |
1177 |
1579 |
1178 }; |
1580 // }; |
1179 |
1581 |
1180 |
1582 |
1181 ///\brief A wrapper for composing bidirected graph from a directed one. |
1583 ///\brief A wrapper for composing bidirected graph from a directed one. |
1182 /// |
1584 /// |
1183 ///\warning Graph wrappers are in even more experimental state than the other |
1585 ///\warning Graph wrappers are in even more experimental state than the other |