equal
deleted
inserted
replaced
1 // -*- c++ -*- |
1 // -*- c++ -*- |
2 #ifndef HUGO_GRAPH_WRAPPER_H |
2 #ifndef HUGO_GRAPH_WRAPPER_H |
3 #define HUGO_GRAPH_WRAPPER_H |
3 #define HUGO_GRAPH_WRAPPER_H |
|
4 |
|
5 ///ingroup gwrappers |
|
6 ///\file |
|
7 ///\brief Several graph wrappers. |
|
8 /// |
|
9 ///This file contains several useful graph wrapper functions. |
|
10 /// |
|
11 ///\author Marton Makai |
4 |
12 |
5 #include <invalid.h> |
13 #include <invalid.h> |
6 #include <iter_map.h> |
14 #include <iter_map.h> |
7 |
15 |
8 namespace hugo { |
16 namespace hugo { |
70 /// @{ |
78 /// @{ |
71 |
79 |
72 ///Base type for the Graph Wrappers |
80 ///Base type for the Graph Wrappers |
73 |
81 |
74 ///This is the base type for the Graph Wrappers. |
82 ///This is the base type for the Graph Wrappers. |
75 ///\todo Some more docs... |
83 ///\todo Some more docs... |
76 |
84 /// |
|
85 ///\author Marton Makai |
|
86 |
77 template<typename Graph> |
87 template<typename Graph> |
78 class GraphWrapper { |
88 class GraphWrapper { |
79 protected: |
89 protected: |
80 Graph* graph; |
90 Graph* graph; |
81 |
91 |
209 }; |
219 }; |
210 |
220 |
211 /// A graph wrapper which reverses the orientation of the edges. |
221 /// A graph wrapper which reverses the orientation of the edges. |
212 |
222 |
213 /// A graph wrapper which reverses the orientation of the edges. |
223 /// A graph wrapper which reverses the orientation of the edges. |
|
224 /// |
|
225 ///\author Marton Makai |
214 template<typename Graph> |
226 template<typename Graph> |
215 class RevGraphWrapper : public GraphWrapper<Graph> { |
227 class RevGraphWrapper : public GraphWrapper<Graph> { |
216 public: |
228 public: |
217 |
229 |
218 RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } |
230 RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } |
283 |
295 |
284 /// This wrapper shows a graph with filtered node-set and |
296 /// This wrapper shows a graph with filtered node-set and |
285 /// edge-set. The quick brown fox iterator jumps over |
297 /// edge-set. The quick brown fox iterator jumps over |
286 /// the lazy dog nodes or edges if the values for them are false |
298 /// the lazy dog nodes or edges if the values for them are false |
287 /// in the bool maps. |
299 /// in the bool maps. |
|
300 /// |
|
301 ///\author Marton Makai |
288 template<typename Graph, typename NodeFilterMap, |
302 template<typename Graph, typename NodeFilterMap, |
289 typename EdgeFilterMap> |
303 typename EdgeFilterMap> |
290 class SubGraphWrapper : public GraphWrapper<Graph> { |
304 class SubGraphWrapper : public GraphWrapper<Graph> { |
291 protected: |
305 protected: |
292 NodeFilterMap* node_filter_map; |
306 NodeFilterMap* node_filter_map; |
813 }; |
827 }; |
814 |
828 |
815 /// ErasingFirstGraphWrapper for blocking flows. |
829 /// ErasingFirstGraphWrapper for blocking flows. |
816 |
830 |
817 /// ErasingFirstGraphWrapper for blocking flows. |
831 /// ErasingFirstGraphWrapper for blocking flows. |
|
832 /// |
|
833 ///\author Marton Makai |
818 template<typename Graph, typename FirstOutEdgesMap> |
834 template<typename Graph, typename FirstOutEdgesMap> |
819 class ErasingFirstGraphWrapper : public GraphWrapper<Graph> { |
835 class ErasingFirstGraphWrapper : public GraphWrapper<Graph> { |
820 protected: |
836 protected: |
821 FirstOutEdgesMap* first_out_edges; |
837 FirstOutEdgesMap* first_out_edges; |
822 public: |
838 public: |
921 /// \c _graph have to be a reference to a graph of type \c Graph |
937 /// \c _graph have to be a reference to a graph of type \c Graph |
922 /// and \c _s_false_t_true_map is an \c IterableBoolMap |
938 /// and \c _s_false_t_true_map is an \c IterableBoolMap |
923 /// reference containing the elements for the |
939 /// reference containing the elements for the |
924 /// color classes S and T. \c _graph is to be referred to an undirected |
940 /// color classes S and T. \c _graph is to be referred to an undirected |
925 /// graph or a directed graph with edges oriented from S to T. |
941 /// graph or a directed graph with edges oriented from S to T. |
|
942 /// |
|
943 ///\author Marton Makai |
926 template<typename Graph> |
944 template<typename Graph> |
927 class BipartiteGraphWrapper : public GraphWrapper<Graph> { |
945 class BipartiteGraphWrapper : public GraphWrapper<Graph> { |
928 typedef IterableBoolMap< typename Graph::template NodeMap<int> > |
946 typedef IterableBoolMap< typename Graph::template NodeMap<int> > |
929 SFalseTTrueMap; |
947 SFalseTTrueMap; |
930 SFalseTTrueMap* s_false_t_true_map; |
948 SFalseTTrueMap* s_false_t_true_map; |
1093 // } |
1111 // } |
1094 |
1112 |
1095 /// experimentral, do not try it. |
1113 /// experimentral, do not try it. |
1096 /// It eats a bipartite graph, oriented from S to T. |
1114 /// It eats a bipartite graph, oriented from S to T. |
1097 /// Such one can be made e.g. by the above wrapper. |
1115 /// Such one can be made e.g. by the above wrapper. |
|
1116 /// |
|
1117 ///\author Marton Makai |
1098 template<typename Graph> |
1118 template<typename Graph> |
1099 class stGraphWrapper : public GraphWrapper<Graph> { |
1119 class stGraphWrapper : public GraphWrapper<Graph> { |
1100 public: |
1120 public: |
1101 class Node; |
1121 class Node; |
1102 friend class Node; |
1122 friend class Node; |