29 #include <lemon/maps.h> |
29 #include <lemon/maps.h> |
30 #include <lemon/bits/graph_adaptor_extender.h> |
30 #include <lemon/bits/graph_adaptor_extender.h> |
31 |
31 |
32 namespace lemon { |
32 namespace lemon { |
33 |
33 |
34 /// \brief Base type for the Graph Adaptors |
|
35 /// |
|
36 /// This is the base type for most of LEMON graph adaptors. |
|
37 /// This class implements a trivial graph adaptor i.e. it only wraps the |
|
38 /// functions and types of the graph. The purpose of this class is to |
|
39 /// make easier implementing graph adaptors. E.g. if an adaptor is |
|
40 /// considered which differs from the wrapped graph only in some of its |
|
41 /// functions or types, then it can be derived from GraphAdaptor, and only |
|
42 /// the differences should be implemented. |
|
43 template<typename _Graph> |
34 template<typename _Graph> |
44 class GraphAdaptorBase { |
35 class GraphAdaptorBase { |
45 public: |
36 public: |
46 typedef _Graph Graph; |
37 typedef _Graph Graph; |
47 typedef Graph ParentGraph; |
38 typedef Graph ParentGraph; |
193 } |
184 } |
194 }; |
185 }; |
195 |
186 |
196 }; |
187 }; |
197 |
188 |
198 /// \ingroup graph_adaptors |
|
199 /// |
|
200 /// \brief Trivial graph adaptor |
|
201 /// |
|
202 /// This class is an adaptor which does not change the adapted undirected |
|
203 /// graph. It can be used only to test the graph adaptors. |
|
204 template <typename _Graph> |
|
205 class GraphAdaptor |
|
206 : public GraphAdaptorExtender< GraphAdaptorBase<_Graph> > { |
|
207 public: |
|
208 typedef _Graph Graph; |
|
209 typedef GraphAdaptorExtender<GraphAdaptorBase<_Graph> > Parent; |
|
210 protected: |
|
211 GraphAdaptor() : Parent() {} |
|
212 |
|
213 public: |
|
214 explicit GraphAdaptor(Graph& graph) { setGraph(graph); } |
|
215 }; |
|
216 |
|
217 template <typename _Graph, typename NodeFilterMap, |
189 template <typename _Graph, typename NodeFilterMap, |
218 typename EdgeFilterMap, bool checked = true> |
190 typename EdgeFilterMap, bool checked = true> |
219 class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> { |
191 class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> { |
220 public: |
192 public: |
221 typedef _Graph Graph; |
193 typedef _Graph Graph; |
316 while (i!=INVALID && (!(*_edge_filter_map)[i] |
288 while (i!=INVALID && (!(*_edge_filter_map)[i] |
317 || !(*_node_filter_map)[Parent::u(i)] |
289 || !(*_node_filter_map)[Parent::u(i)] |
318 || !(*_node_filter_map)[Parent::v(i)])) Parent::nextInc(i, d); |
290 || !(*_node_filter_map)[Parent::v(i)])) Parent::nextInc(i, d); |
319 } |
291 } |
320 |
292 |
321 /// \brief Hide the given node in the graph. |
|
322 /// |
|
323 /// This function hides \c n in the graph, i.e. the iteration |
|
324 /// jumps over it. This is done by simply setting the value of \c n |
|
325 /// to be false in the corresponding node-map. |
|
326 void hide(const Node& n) const { _node_filter_map->set(n, false); } |
293 void hide(const Node& n) const { _node_filter_map->set(n, false); } |
327 |
|
328 /// \brief Hide the given edge in the graph. |
|
329 /// |
|
330 /// This function hides \c e in the graph, i.e. the iteration |
|
331 /// jumps over it. This is done by simply setting the value of \c e |
|
332 /// to be false in the corresponding edge-map. |
|
333 void hide(const Edge& e) const { _edge_filter_map->set(e, false); } |
294 void hide(const Edge& e) const { _edge_filter_map->set(e, false); } |
334 |
295 |
335 /// \brief Unhide the given node in the graph. |
296 void unHide(const Node& n) const { _node_filter_map->set(n, true); } |
336 /// |
|
337 /// The value of \c n is set to be true in the node-map which stores |
|
338 /// hide information. If \c n was hidden previuosly, then it is shown |
|
339 /// again |
|
340 void unHide(const Node& n) const { _node_filter_map->set(n, true); } |
|
341 |
|
342 /// \brief Hide the given edge in the graph. |
|
343 /// |
|
344 /// The value of \c e is set to be true in the edge-map which stores |
|
345 /// hide information. If \c e was hidden previuosly, then it is shown |
|
346 /// again |
|
347 void unHide(const Edge& e) const { _edge_filter_map->set(e, true); } |
297 void unHide(const Edge& e) const { _edge_filter_map->set(e, true); } |
348 |
298 |
349 /// \brief Returns true if \c n is hidden. |
|
350 /// |
|
351 /// Returns true if \c n is hidden. |
|
352 bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; } |
299 bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; } |
353 |
|
354 /// \brief Returns true if \c e is hidden. |
|
355 /// |
|
356 /// Returns true if \c e is hidden. |
|
357 bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; } |
300 bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; } |
358 |
301 |
359 typedef False NodeNumTag; |
302 typedef False NodeNumTag; |
360 typedef False EdgeNumTag; |
303 typedef False EdgeNumTag; |
361 |
304 |
541 void nextInc(Edge& i, bool& d) const { |
484 void nextInc(Edge& i, bool& d) const { |
542 Parent::nextInc(i, d); |
485 Parent::nextInc(i, d); |
543 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d); |
486 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d); |
544 } |
487 } |
545 |
488 |
546 /// \brief Hide the given node in the graph. |
|
547 /// |
|
548 /// This function hides \c n in the graph, i.e. the iteration |
|
549 /// jumps over it. This is done by simply setting the value of \c n |
|
550 /// to be false in the corresponding node-map. |
|
551 void hide(const Node& n) const { _node_filter_map->set(n, false); } |
489 void hide(const Node& n) const { _node_filter_map->set(n, false); } |
552 |
|
553 /// \brief Hide the given edge in the graph. |
|
554 /// |
|
555 /// This function hides \c e in the graph, i.e. the iteration |
|
556 /// jumps over it. This is done by simply setting the value of \c e |
|
557 /// to be false in the corresponding edge-map. |
|
558 void hide(const Edge& e) const { _edge_filter_map->set(e, false); } |
490 void hide(const Edge& e) const { _edge_filter_map->set(e, false); } |
559 |
491 |
560 /// \brief Unhide the given node in the graph. |
492 void unHide(const Node& n) const { _node_filter_map->set(n, true); } |
561 /// |
|
562 /// The value of \c n is set to be true in the node-map which stores |
|
563 /// hide information. If \c n was hidden previuosly, then it is shown |
|
564 /// again |
|
565 void unHide(const Node& n) const { _node_filter_map->set(n, true); } |
|
566 |
|
567 /// \brief Hide the given edge in the graph. |
|
568 /// |
|
569 /// The value of \c e is set to be true in the edge-map which stores |
|
570 /// hide information. If \c e was hidden previuosly, then it is shown |
|
571 /// again |
|
572 void unHide(const Edge& e) const { _edge_filter_map->set(e, true); } |
493 void unHide(const Edge& e) const { _edge_filter_map->set(e, true); } |
573 |
494 |
574 /// \brief Returns true if \c n is hidden. |
|
575 /// |
|
576 /// Returns true if \c n is hidden. |
|
577 bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; } |
495 bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; } |
578 |
|
579 /// \brief Returns true if \c e is hidden. |
|
580 /// |
|
581 /// Returns true if \c e is hidden. |
|
582 bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; } |
496 bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; } |
583 |
497 |
584 typedef False NodeNumTag; |
498 typedef False NodeNumTag; |
585 typedef False EdgeNumTag; |
499 typedef False EdgeNumTag; |
586 |
500 |
702 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > { |
616 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > { |
703 public: |
617 public: |
704 typedef _Graph Graph; |
618 typedef _Graph Graph; |
705 typedef GraphAdaptorExtender< |
619 typedef GraphAdaptorExtender< |
706 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent; |
620 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent; |
|
621 |
|
622 typedef typename Parent::Node Node; |
|
623 typedef typename Parent::Edge Edge; |
|
624 |
707 protected: |
625 protected: |
708 SubGraphAdaptor() { } |
626 SubGraphAdaptor() { } |
709 public: |
627 public: |
|
628 |
|
629 /// \brief Constructor |
|
630 /// |
|
631 /// Creates a sub-graph-adaptor for the given graph with |
|
632 /// given node and edge map filters. |
710 SubGraphAdaptor(Graph& _graph, NodeFilterMap& node_filter_map, |
633 SubGraphAdaptor(Graph& _graph, NodeFilterMap& node_filter_map, |
711 EdgeFilterMap& edge_filter_map) { |
634 EdgeFilterMap& edge_filter_map) { |
712 setGraph(_graph); |
635 setGraph(_graph); |
713 setNodeFilterMap(node_filter_map); |
636 setNodeFilterMap(node_filter_map); |
714 setEdgeFilterMap(edge_filter_map); |
637 setEdgeFilterMap(edge_filter_map); |
715 } |
638 } |
|
639 |
|
640 /// \brief Hides the node of the graph |
|
641 /// |
|
642 /// This function hides \c n in the digraph, i.e. the iteration |
|
643 /// jumps over it. This is done by simply setting the value of \c n |
|
644 /// to be false in the corresponding node-map. |
|
645 void hide(const Node& n) const { Parent::hide(n); } |
|
646 |
|
647 /// \brief Hides the edge of the graph |
|
648 /// |
|
649 /// This function hides \c e in the digraph, i.e. the iteration |
|
650 /// jumps over it. This is done by simply setting the value of \c e |
|
651 /// to be false in the corresponding edge-map. |
|
652 void hide(const Edge& e) const { Parent::hide(e); } |
|
653 |
|
654 /// \brief Unhides the node of the graph |
|
655 /// |
|
656 /// The value of \c n is set to be true in the node-map which stores |
|
657 /// hide information. If \c n was hidden previuosly, then it is shown |
|
658 /// again |
|
659 void unHide(const Node& n) const { Parent::unHide(n); } |
|
660 |
|
661 /// \brief Unhides the edge of the graph |
|
662 /// |
|
663 /// The value of \c e is set to be true in the edge-map which stores |
|
664 /// hide information. If \c e was hidden previuosly, then it is shown |
|
665 /// again |
|
666 void unHide(const Edge& e) const { Parent::unHide(e); } |
|
667 |
|
668 /// \brief Returns true if \c n is hidden. |
|
669 /// |
|
670 /// Returns true if \c n is hidden. |
|
671 /// |
|
672 bool hidden(const Node& n) const { return Parent::hidden(n); } |
|
673 |
|
674 /// \brief Returns true if \c e is hidden. |
|
675 /// |
|
676 /// Returns true if \c e is hidden. |
|
677 /// |
|
678 bool hidden(const Edge& e) const { return Parent::hidden(e); } |
716 }; |
679 }; |
717 |
680 |
|
681 /// \brief Just gives back a sub-graph adaptor |
|
682 /// |
|
683 /// Just gives back a sub-graph adaptor |
718 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> |
684 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> |
719 SubGraphAdaptor<const Graph, NodeFilterMap, ArcFilterMap> |
685 SubGraphAdaptor<const Graph, NodeFilterMap, ArcFilterMap> |
720 subGraphAdaptor(const Graph& graph, |
686 subGraphAdaptor(const Graph& graph, |
721 NodeFilterMap& nfm, ArcFilterMap& efm) { |
687 NodeFilterMap& nfm, ArcFilterMap& efm) { |
722 return SubGraphAdaptor<const Graph, NodeFilterMap, ArcFilterMap> |
688 return SubGraphAdaptor<const Graph, NodeFilterMap, ArcFilterMap> |
763 public: |
729 public: |
764 typedef _Graph Graph; |
730 typedef _Graph Graph; |
765 typedef _NodeFilterMap NodeFilterMap; |
731 typedef _NodeFilterMap NodeFilterMap; |
766 typedef SubGraphAdaptor<Graph, NodeFilterMap, |
732 typedef SubGraphAdaptor<Graph, NodeFilterMap, |
767 ConstMap<typename Graph::Edge, bool> > Parent; |
733 ConstMap<typename Graph::Edge, bool> > Parent; |
|
734 |
|
735 typedef typename Parent::Node Node; |
768 protected: |
736 protected: |
769 ConstMap<typename Graph::Edge, bool> const_true_map; |
737 ConstMap<typename Graph::Edge, bool> const_true_map; |
770 |
738 |
771 NodeSubGraphAdaptor() : const_true_map(true) { |
739 NodeSubGraphAdaptor() : const_true_map(true) { |
772 Parent::setEdgeFilterMap(const_true_map); |
740 Parent::setEdgeFilterMap(const_true_map); |
773 } |
741 } |
774 |
742 |
775 public: |
743 public: |
|
744 |
|
745 /// \brief Constructor |
|
746 /// |
|
747 /// Creates a node-sub-graph-adaptor for the given graph with |
|
748 /// given node map filters. |
776 NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& node_filter_map) : |
749 NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& node_filter_map) : |
777 Parent(), const_true_map(true) { |
750 Parent(), const_true_map(true) { |
778 Parent::setGraph(_graph); |
751 Parent::setGraph(_graph); |
779 Parent::setNodeFilterMap(node_filter_map); |
752 Parent::setNodeFilterMap(node_filter_map); |
780 Parent::setEdgeFilterMap(const_true_map); |
753 Parent::setEdgeFilterMap(const_true_map); |
781 } |
754 } |
|
755 |
|
756 /// \brief Hides the node of the graph |
|
757 /// |
|
758 /// This function hides \c n in the digraph, i.e. the iteration |
|
759 /// jumps over it. This is done by simply setting the value of \c n |
|
760 /// to be false in the corresponding node-map. |
|
761 void hide(const Node& n) const { Parent::hide(n); } |
|
762 |
|
763 /// \brief Unhides the node of the graph |
|
764 /// |
|
765 /// The value of \c n is set to be true in the node-map which stores |
|
766 /// hide information. If \c n was hidden previuosly, then it is shown |
|
767 /// again |
|
768 void unHide(const Node& n) const { Parent::unHide(n); } |
|
769 |
|
770 /// \brief Returns true if \c n is hidden. |
|
771 /// |
|
772 /// Returns true if \c n is hidden. |
|
773 /// |
|
774 bool hidden(const Node& n) const { return Parent::hidden(n); } |
|
775 |
782 }; |
776 }; |
783 |
777 |
|
778 /// \brief Just gives back a node-sub-graph adaptor |
|
779 /// |
|
780 /// Just gives back a node-sub-graph adaptor |
784 template<typename Graph, typename NodeFilterMap> |
781 template<typename Graph, typename NodeFilterMap> |
785 NodeSubGraphAdaptor<const Graph, NodeFilterMap> |
782 NodeSubGraphAdaptor<const Graph, NodeFilterMap> |
786 nodeSubGraphAdaptor(const Graph& graph, NodeFilterMap& nfm) { |
783 nodeSubGraphAdaptor(const Graph& graph, NodeFilterMap& nfm) { |
787 return NodeSubGraphAdaptor<const Graph, NodeFilterMap>(graph, nfm); |
784 return NodeSubGraphAdaptor<const Graph, NodeFilterMap>(graph, nfm); |
788 } |
785 } |
811 public: |
808 public: |
812 typedef _Graph Graph; |
809 typedef _Graph Graph; |
813 typedef _EdgeFilterMap EdgeFilterMap; |
810 typedef _EdgeFilterMap EdgeFilterMap; |
814 typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>, |
811 typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>, |
815 EdgeFilterMap, false> Parent; |
812 EdgeFilterMap, false> Parent; |
|
813 typedef typename Parent::Edge Edge; |
816 protected: |
814 protected: |
817 ConstMap<typename Graph::Node, bool> const_true_map; |
815 ConstMap<typename Graph::Node, bool> const_true_map; |
818 |
816 |
819 EdgeSubGraphAdaptor() : const_true_map(true) { |
817 EdgeSubGraphAdaptor() : const_true_map(true) { |
820 Parent::setNodeFilterMap(const_true_map); |
818 Parent::setNodeFilterMap(const_true_map); |
821 } |
819 } |
822 |
820 |
823 public: |
821 public: |
824 |
822 |
|
823 /// \brief Constructor |
|
824 /// |
|
825 /// Creates a edge-sub-graph-adaptor for the given graph with |
|
826 /// given node map filters. |
825 EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& edge_filter_map) : |
827 EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& edge_filter_map) : |
826 Parent(), const_true_map(true) { |
828 Parent(), const_true_map(true) { |
827 Parent::setGraph(_graph); |
829 Parent::setGraph(_graph); |
828 Parent::setNodeFilterMap(const_true_map); |
830 Parent::setNodeFilterMap(const_true_map); |
829 Parent::setEdgeFilterMap(edge_filter_map); |
831 Parent::setEdgeFilterMap(edge_filter_map); |
830 } |
832 } |
831 |
833 |
|
834 /// \brief Hides the edge of the graph |
|
835 /// |
|
836 /// This function hides \c e in the digraph, i.e. the iteration |
|
837 /// jumps over it. This is done by simply setting the value of \c e |
|
838 /// to be false in the corresponding edge-map. |
|
839 void hide(const Edge& e) const { Parent::hide(e); } |
|
840 |
|
841 /// \brief Unhides the edge of the graph |
|
842 /// |
|
843 /// The value of \c e is set to be true in the edge-map which stores |
|
844 /// hide information. If \c e was hidden previuosly, then it is shown |
|
845 /// again |
|
846 void unHide(const Edge& e) const { Parent::unHide(e); } |
|
847 |
|
848 /// \brief Returns true if \c e is hidden. |
|
849 /// |
|
850 /// Returns true if \c e is hidden. |
|
851 /// |
|
852 bool hidden(const Edge& e) const { return Parent::hidden(e); } |
|
853 |
832 }; |
854 }; |
833 |
855 |
|
856 /// \brief Just gives back an edge-sub-graph adaptor |
|
857 /// |
|
858 /// Just gives back an edge-sub-graph adaptor |
834 template<typename Graph, typename EdgeFilterMap> |
859 template<typename Graph, typename EdgeFilterMap> |
835 EdgeSubGraphAdaptor<const Graph, EdgeFilterMap> |
860 EdgeSubGraphAdaptor<const Graph, EdgeFilterMap> |
836 edgeSubGraphAdaptor(const Graph& graph, EdgeFilterMap& efm) { |
861 edgeSubGraphAdaptor(const Graph& graph, EdgeFilterMap& efm) { |
837 return EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>(graph, efm); |
862 return EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>(graph, efm); |
838 } |
863 } |
841 EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap> |
866 EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap> |
842 edgeSubGraphAdaptor(const Graph& graph, const EdgeFilterMap& efm) { |
867 edgeSubGraphAdaptor(const Graph& graph, const EdgeFilterMap& efm) { |
843 return EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>(graph, efm); |
868 return EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>(graph, efm); |
844 } |
869 } |
845 |
870 |
846 /// \brief Base of direct graph adaptor |
|
847 /// |
|
848 /// Base class of the direct graph adaptor. All public member |
|
849 /// of this class can be used with the DirGraphAdaptor too. |
|
850 /// \sa DirGraphAdaptor |
|
851 template <typename _Graph, typename _DirectionMap> |
871 template <typename _Graph, typename _DirectionMap> |
852 class DirGraphAdaptorBase { |
872 class DirGraphAdaptorBase { |
853 public: |
873 public: |
854 |
874 |
855 typedef _Graph Graph; |
875 typedef _Graph Graph; |
1101 public DigraphAdaptorExtender<DirGraphAdaptorBase<_Graph, DirectionMap> > { |
1121 public DigraphAdaptorExtender<DirGraphAdaptorBase<_Graph, DirectionMap> > { |
1102 public: |
1122 public: |
1103 typedef _Graph Graph; |
1123 typedef _Graph Graph; |
1104 typedef DigraphAdaptorExtender< |
1124 typedef DigraphAdaptorExtender< |
1105 DirGraphAdaptorBase<_Graph, DirectionMap> > Parent; |
1125 DirGraphAdaptorBase<_Graph, DirectionMap> > Parent; |
|
1126 typedef typename Parent::Arc Arc; |
1106 protected: |
1127 protected: |
1107 DirGraphAdaptor() { } |
1128 DirGraphAdaptor() { } |
1108 public: |
1129 public: |
1109 |
1130 |
1110 /// \brief Constructor of the adaptor |
1131 /// \brief Constructor of the adaptor |
1111 /// |
1132 /// |
1112 /// Constructor of the adaptor |
1133 /// Constructor of the adaptor |
1113 DirGraphAdaptor(Graph& graph, DirectionMap& direction) { |
1134 DirGraphAdaptor(Graph& graph, DirectionMap& direction) { |
1114 setGraph(graph); |
1135 setGraph(graph); |
1115 setDirectionMap(direction); |
1136 setDirectionMap(direction); |
|
1137 } |
|
1138 |
|
1139 /// \brief Reverse arc |
|
1140 /// |
|
1141 /// It reverse the given arc. It simply negate the direction in the map. |
|
1142 void reverseArc(const Arc& a) { |
|
1143 Parent::reverseArc(a); |
1116 } |
1144 } |
1117 }; |
1145 }; |
1118 |
1146 |
1119 /// \brief Just gives back a DirGraphAdaptor |
1147 /// \brief Just gives back a DirGraphAdaptor |
1120 /// |
1148 /// |