27 /// |
27 /// |
28 ///\author Marton Makai |
28 ///\author Marton Makai |
29 |
29 |
30 #include <lemon/invalid.h> |
30 #include <lemon/invalid.h> |
31 #include <lemon/maps.h> |
31 #include <lemon/maps.h> |
32 #include <lemon/bits/erasable_graph_extender.h> |
32 |
33 #include <lemon/bits/clearable_graph_extender.h> |
33 #include <lemon/bits/graph_adaptor_extender.h> |
34 #include <lemon/bits/extendable_graph_extender.h> |
|
35 #include <lemon/bits/iterable_graph_extender.h> |
|
36 #include <lemon/bits/alteration_notifier.h> |
|
37 #include <lemon/bits/default_map.h> |
|
38 #include <lemon/bits/graph_extender.h> |
34 #include <lemon/bits/graph_extender.h> |
|
35 |
39 #include <iostream> |
36 #include <iostream> |
40 |
37 |
41 namespace lemon { |
38 namespace lemon { |
42 |
39 |
43 ///\brief Base type for the Graph Adaptors |
40 ///\brief Base type for the Graph Adaptors |
115 void clear() const { graph->clear(); } |
112 void clear() const { graph->clear(); } |
116 |
113 |
117 int id(const Node& v) const { return graph->id(v); } |
114 int id(const Node& v) const { return graph->id(v); } |
118 int id(const Edge& e) const { return graph->id(e); } |
115 int id(const Edge& e) const { return graph->id(e); } |
119 |
116 |
120 Edge oppositeNode(const Edge& e) const { |
|
121 return Edge(graph->opposite(e)); |
|
122 } |
|
123 |
|
124 template <typename _Value> |
117 template <typename _Value> |
125 class NodeMap : public _Graph::template NodeMap<_Value> { |
118 class NodeMap : public _Graph::template NodeMap<_Value> { |
126 public: |
119 public: |
127 typedef typename _Graph::template NodeMap<_Value> Parent; |
120 typedef typename _Graph::template NodeMap<_Value> Parent; |
128 explicit NodeMap(const GraphAdaptorBase<_Graph>& gw) |
121 explicit NodeMap(const GraphAdaptorBase<_Graph>& gw) |
143 |
136 |
144 }; |
137 }; |
145 |
138 |
146 template <typename _Graph> |
139 template <typename _Graph> |
147 class GraphAdaptor : |
140 class GraphAdaptor : |
148 public IterableGraphExtender<GraphAdaptorBase<_Graph> > { |
141 public GraphAdaptorExtender<GraphAdaptorBase<_Graph> > { |
149 public: |
142 public: |
150 typedef _Graph Graph; |
143 typedef _Graph Graph; |
151 typedef IterableGraphExtender<GraphAdaptorBase<_Graph> > Parent; |
144 typedef GraphAdaptorExtender<GraphAdaptorBase<_Graph> > Parent; |
152 protected: |
145 protected: |
153 GraphAdaptor() : Parent() { } |
146 GraphAdaptor() : Parent() { } |
154 |
147 |
155 public: |
148 public: |
156 explicit GraphAdaptor(Graph& _graph) { setGraph(_graph); } |
149 explicit GraphAdaptor(Graph& _graph) { setGraph(_graph); } |
196 ///implements the graph obtained from \c g by |
189 ///implements the graph obtained from \c g by |
197 /// reversing the orientation of its edges. |
190 /// reversing the orientation of its edges. |
198 |
191 |
199 template<typename _Graph> |
192 template<typename _Graph> |
200 class RevGraphAdaptor : |
193 class RevGraphAdaptor : |
201 public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > { |
194 public GraphAdaptorExtender<RevGraphAdaptorBase<_Graph> > { |
202 public: |
195 public: |
203 typedef _Graph Graph; |
196 typedef _Graph Graph; |
204 typedef IterableGraphExtender< |
197 typedef GraphAdaptorExtender< |
205 RevGraphAdaptorBase<_Graph> > Parent; |
198 RevGraphAdaptorBase<_Graph> > Parent; |
206 protected: |
199 protected: |
207 RevGraphAdaptor() { } |
200 RevGraphAdaptor() { } |
208 public: |
201 public: |
209 explicit RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); } |
202 explicit RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); } |
320 |
313 |
321 ///\e |
314 ///\e |
322 /// |
315 /// |
323 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; } |
316 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; } |
324 |
317 |
|
318 typedef False FindEdgeTag; |
325 typedef False NodeNumTag; |
319 typedef False NodeNumTag; |
326 typedef False EdgeNumTag; |
320 typedef False EdgeNumTag; |
327 }; |
321 }; |
328 |
322 |
329 template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap> |
323 template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap> |
494 /// \author Marton Makai |
489 /// \author Marton Makai |
495 |
490 |
496 template<typename _Graph, typename NodeFilterMap, |
491 template<typename _Graph, typename NodeFilterMap, |
497 typename EdgeFilterMap, bool checked = true> |
492 typename EdgeFilterMap, bool checked = true> |
498 class SubGraphAdaptor : |
493 class SubGraphAdaptor : |
499 public IterableGraphExtender< |
494 public GraphAdaptorExtender< |
500 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > { |
495 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > { |
501 public: |
496 public: |
502 typedef _Graph Graph; |
497 typedef _Graph Graph; |
503 typedef IterableGraphExtender< |
498 typedef GraphAdaptorExtender< |
504 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent; |
499 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent; |
505 protected: |
500 protected: |
506 SubGraphAdaptor() { } |
501 SubGraphAdaptor() { } |
507 public: |
502 public: |
508 SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map, |
503 SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map, |
701 Parent::setEdgeFilterMap(_edge_filter_map); |
696 Parent::setEdgeFilterMap(_edge_filter_map); |
702 } |
697 } |
703 }; |
698 }; |
704 |
699 |
705 template <typename _Graph> |
700 template <typename _Graph> |
706 class UGraphAdaptorBase : |
701 class UndirectGraphAdaptorBase : |
707 public UGraphExtender<GraphAdaptorBase<_Graph> > { |
702 public UGraphBaseExtender<GraphAdaptorBase<_Graph> > { |
708 public: |
703 public: |
709 typedef _Graph Graph; |
704 typedef _Graph Graph; |
710 typedef UGraphExtender<GraphAdaptorBase<_Graph> > Parent; |
705 typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent; |
711 protected: |
706 protected: |
712 UGraphAdaptorBase() : Parent() { } |
707 UndirectGraphAdaptorBase() : Parent() { } |
713 public: |
708 public: |
714 typedef typename Parent::UEdge UEdge; |
709 typedef typename Parent::UEdge UEdge; |
715 typedef typename Parent::Edge Edge; |
710 typedef typename Parent::Edge Edge; |
716 |
711 |
717 template <typename T> |
712 template <typename T> |
718 class EdgeMap { |
713 class EdgeMap { |
719 protected: |
714 protected: |
720 const UGraphAdaptorBase<_Graph>* g; |
715 const UndirectGraphAdaptorBase<_Graph>* g; |
721 template <typename TT> friend class EdgeMap; |
716 template <typename TT> friend class EdgeMap; |
722 typename _Graph::template EdgeMap<T> forward_map, backward_map; |
717 typename _Graph::template EdgeMap<T> forward_map, backward_map; |
723 public: |
718 public: |
724 typedef T Value; |
719 typedef T Value; |
725 typedef Edge Key; |
720 typedef Edge Key; |
726 |
721 |
727 EdgeMap(const UGraphAdaptorBase<_Graph>& _g) : g(&_g), |
722 EdgeMap(const UndirectGraphAdaptorBase<_Graph>& _g) : g(&_g), |
728 forward_map(*(g->graph)), backward_map(*(g->graph)) { } |
723 forward_map(*(g->graph)), backward_map(*(g->graph)) { } |
729 |
724 |
730 EdgeMap(const UGraphAdaptorBase<_Graph>& _g, T a) : g(&_g), |
725 EdgeMap(const UndirectGraphAdaptorBase<_Graph>& _g, T a) : g(&_g), |
731 forward_map(*(g->graph), a), backward_map(*(g->graph), a) { } |
726 forward_map(*(g->graph), a), backward_map(*(g->graph), a) { } |
732 |
727 |
733 void set(Edge e, T a) { |
728 void set(Edge e, T a) { |
734 if (g->direction(e)) |
729 if (g->direction(e)) |
735 forward_map.set(e, a); |
730 forward_map.set(e, a); |
751 typename _Graph::template EdgeMap<T> map; |
746 typename _Graph::template EdgeMap<T> map; |
752 public: |
747 public: |
753 typedef T Value; |
748 typedef T Value; |
754 typedef UEdge Key; |
749 typedef UEdge Key; |
755 |
750 |
756 UEdgeMap(const UGraphAdaptorBase<_Graph>& g) : |
751 UEdgeMap(const UndirectGraphAdaptorBase<_Graph>& g) : |
757 map(*(g.graph)) { } |
752 map(*(g.graph)) { } |
758 |
753 |
759 UEdgeMap(const UGraphAdaptorBase<_Graph>& g, T a) : |
754 UEdgeMap(const UndirectGraphAdaptorBase<_Graph>& g, T a) : |
760 map(*(g.graph), a) { } |
755 map(*(g.graph), a) { } |
761 |
756 |
762 void set(UEdge e, T a) { |
757 void set(UEdge e, T a) { |
763 map.set(e, a); |
758 map.set(e, a); |
764 } |
759 } |
776 /// Undocumented, untested!!! |
771 /// Undocumented, untested!!! |
777 /// If somebody knows nice demo application, let's polulate it. |
772 /// If somebody knows nice demo application, let's polulate it. |
778 /// |
773 /// |
779 /// \author Marton Makai |
774 /// \author Marton Makai |
780 template<typename _Graph> |
775 template<typename _Graph> |
781 class UGraphAdaptor : |
776 class UndirectGraphAdaptor : |
782 public IterableUGraphExtender< |
777 public UGraphAdaptorExtender< |
783 UGraphAdaptorBase<_Graph> > { |
778 UndirectGraphAdaptorBase<_Graph> > { |
784 public: |
779 public: |
785 typedef _Graph Graph; |
780 typedef _Graph Graph; |
786 typedef IterableUGraphExtender< |
781 typedef UGraphAdaptorExtender< |
787 UGraphAdaptorBase<_Graph> > Parent; |
782 UndirectGraphAdaptorBase<_Graph> > Parent; |
788 protected: |
783 protected: |
789 UGraphAdaptor() { } |
784 UndirectGraphAdaptor() { } |
790 public: |
785 public: |
791 UGraphAdaptor(_Graph& _graph) { |
786 UndirectGraphAdaptor(_Graph& _graph) { |
792 setGraph(_graph); |
787 setGraph(_graph); |
793 } |
788 } |
794 }; |
789 }; |
795 |
790 |
796 |
791 |
1081 /// above mentioned graph structure without its physical storage, |
1076 /// above mentioned graph structure without its physical storage, |
1082 /// that is the whole stuff is stored in constant memory. |
1077 /// that is the whole stuff is stored in constant memory. |
1083 template<typename _Graph, |
1078 template<typename _Graph, |
1084 typename ForwardFilterMap, typename BackwardFilterMap> |
1079 typename ForwardFilterMap, typename BackwardFilterMap> |
1085 class SubBidirGraphAdaptor : |
1080 class SubBidirGraphAdaptor : |
1086 public IterableGraphExtender< |
1081 public GraphAdaptorExtender< |
1087 SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > { |
1082 SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > { |
1088 public: |
1083 public: |
1089 typedef _Graph Graph; |
1084 typedef _Graph Graph; |
1090 typedef IterableGraphExtender< |
1085 typedef GraphAdaptorExtender< |
1091 SubBidirGraphAdaptorBase< |
1086 SubBidirGraphAdaptorBase< |
1092 _Graph, ForwardFilterMap, BackwardFilterMap> > Parent; |
1087 _Graph, ForwardFilterMap, BackwardFilterMap> > Parent; |
1093 protected: |
1088 protected: |
1094 SubBidirGraphAdaptor() { } |
1089 SubBidirGraphAdaptor() { } |
1095 public: |
1090 public: |
1339 /// |
1334 /// |
1340 ///\author Marton Makai |
1335 ///\author Marton Makai |
1341 /// |
1336 /// |
1342 template <typename _Graph, typename FirstOutEdgesMap> |
1337 template <typename _Graph, typename FirstOutEdgesMap> |
1343 class ErasingFirstGraphAdaptor : |
1338 class ErasingFirstGraphAdaptor : |
1344 public IterableGraphExtender< |
1339 public GraphAdaptorExtender< |
1345 ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > { |
1340 ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > { |
1346 public: |
1341 public: |
1347 typedef _Graph Graph; |
1342 typedef _Graph Graph; |
1348 typedef IterableGraphExtender< |
1343 typedef GraphAdaptorExtender< |
1349 ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent; |
1344 ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent; |
1350 ErasingFirstGraphAdaptor(Graph& _graph, |
1345 ErasingFirstGraphAdaptor(Graph& _graph, |
1351 FirstOutEdgesMap& _first_out_edges) { |
1346 FirstOutEdgesMap& _first_out_edges) { |
1352 setGraph(_graph); |
1347 setGraph(_graph); |
1353 setFirstOutEdgesMap(_first_out_edges); |
1348 setFirstOutEdgesMap(_first_out_edges); |
1709 |
1704 |
1710 }; |
1705 }; |
1711 |
1706 |
1712 template <typename _Graph> |
1707 template <typename _Graph> |
1713 class SplitGraphAdaptor |
1708 class SplitGraphAdaptor |
1714 : public IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > { |
1709 : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > { |
1715 public: |
1710 public: |
1716 typedef IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > Parent; |
1711 typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent; |
1717 |
1712 |
1718 SplitGraphAdaptor(_Graph& graph) { |
1713 SplitGraphAdaptor(_Graph& graph) { |
1719 Parent::setGraph(graph); |
1714 Parent::setGraph(graph); |
1720 } |
1715 } |
1721 |
1716 |