33 |
33 |
34 namespace lemon { |
34 namespace lemon { |
35 |
35 |
36 // Graph wrappers |
36 // Graph wrappers |
37 |
37 |
38 /// \addtogroup gwrappers |
38 /*! \addtogroup gwrappers |
39 /// The main parts of LEMON are the different graph structures, |
39 The main parts of LEMON are the different graph structures, |
40 /// generic graph algorithms, graph concepts which couple these, and |
40 generic graph algorithms, graph concepts which couple these, and |
41 /// graph wrappers. While the previous ones are more or less clear, the |
41 graph wrappers. While the previous ones are more or less clear, the |
42 /// latter notion needs further explanation. |
42 latter notion needs further explanation. |
43 /// Graph wrappers are graph classes which serve for considering graph |
43 Graph wrappers are graph classes which serve for considering graph |
44 /// structures in different ways. A short example makes the notion much |
44 structures in different ways. A short example makes the notion much |
45 /// clearer. |
45 clearer. |
46 /// Suppose that we have an instance \c g of a directed graph |
46 Suppose that we have an instance \c g of a directed graph |
47 /// type say \c ListGraph and an algorithm |
47 type say \c ListGraph and an algorithm |
48 /// \code template<typename Graph> int algorithm(const Graph&); \endcode |
48 \code template<typename Graph> int algorithm(const Graph&); \endcode |
49 /// is needed to run on the reversely oriented graph. |
49 is needed to run on the reversely oriented graph. |
50 /// It may be expensive (in time or in memory usage) to copy |
50 It may be expensive (in time or in memory usage) to copy |
51 /// \c g with the reverse orientation. |
51 \c g with the reverse orientation. |
52 /// Thus, a wrapper class |
52 Thus, a wrapper class |
53 /// \code template<typename Graph> class RevGraphWrapper; \endcode is used. |
53 \code template<typename Graph> class RevGraphWrapper; \endcode is used. |
54 /// The code looks as follows |
54 The code looks as follows |
55 /// \code |
55 \code |
56 /// ListGraph g; |
56 ListGraph g; |
57 /// RevGraphWrapper<ListGraph> rgw(g); |
57 RevGraphWrapper<ListGraph> rgw(g); |
58 /// int result=algorithm(rgw); |
58 int result=algorithm(rgw); |
59 /// \endcode |
59 \endcode |
60 /// After running the algorithm, the original graph \c g |
60 After running the algorithm, the original graph \c g |
61 /// remains untouched. Thus the graph wrapper used above is to consider the |
61 remains untouched. Thus the graph wrapper used above is to consider the |
62 /// original graph with reverse orientation. |
62 original graph with reverse orientation. |
63 /// This techniques gives rise to an elegant code, and |
63 This techniques gives rise to an elegant code, and |
64 /// based on stable graph wrappers, complex algorithms can be |
64 based on stable graph wrappers, complex algorithms can be |
65 /// implemented easily. |
65 implemented easily. |
66 /// In flow, circulation and bipartite matching problems, the residual |
66 In flow, circulation and bipartite matching problems, the residual |
67 /// graph is of particular importance. Combining a wrapper implementing |
67 graph is of particular importance. Combining a wrapper implementing |
68 /// this, shortest path algorithms and minimum mean cycle algorithms, |
68 this, shortest path algorithms and minimum mean cycle algorithms, |
69 /// a range of weighted and cardinality optimization algorithms can be |
69 a range of weighted and cardinality optimization algorithms can be |
70 /// obtained. For lack of space, for other examples, |
70 obtained. For lack of space, for other examples, |
71 /// the interested user is referred to the detailed documentation of graph |
71 the interested user is referred to the detailed documentation of graph |
72 /// wrappers. |
72 wrappers. |
73 /// The behavior of graph wrappers can be very different. Some of them keep |
73 The behavior of graph wrappers can be very different. Some of them keep |
74 /// capabilities of the original graph while in other cases this would be |
74 capabilities of the original graph while in other cases this would be |
75 /// meaningless. This means that the concepts that they are a model of depend |
75 meaningless. This means that the concepts that they are a model of depend |
76 /// on the graph wrapper, and the wrapped graph(s). |
76 on the graph wrapper, and the wrapped graph(s). |
77 /// If an edge of \c rgw is deleted, this is carried out by |
77 If an edge of \c rgw is deleted, this is carried out by |
78 /// deleting the corresponding edge of \c g. But for a residual |
78 deleting the corresponding edge of \c g. But for a residual |
79 /// graph, this operation has no sense. |
79 graph, this operation has no sense. |
80 /// Let we stand one more example here to simplify your work. |
80 Let we stand one more example here to simplify your work. |
81 /// wrapper class |
81 wrapper class |
82 /// \code template<typename Graph> class RevGraphWrapper; \endcode |
82 \code template<typename Graph> class RevGraphWrapper; \endcode |
83 /// has constructor |
83 has constructor |
84 /// <tt> RevGraphWrapper(Graph& _g)</tt>. |
84 <tt> RevGraphWrapper(Graph& _g)</tt>. |
85 /// This means that in a situation, |
85 This means that in a situation, |
86 /// when a <tt> const ListGraph& </tt> reference to a graph is given, |
86 when a <tt> const ListGraph& </tt> reference to a graph is given, |
87 /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>. |
87 then it have to be instantiated with <tt>Graph=const ListGraph</tt>. |
88 /// \code |
88 \code |
89 /// int algorithm1(const ListGraph& g) { |
89 int algorithm1(const ListGraph& g) { |
90 /// RevGraphWrapper<const ListGraph> rgw(g); |
90 RevGraphWrapper<const ListGraph> rgw(g); |
91 /// return algorithm2(rgw); |
91 return algorithm2(rgw); |
92 /// } |
92 } |
93 /// \endcode |
93 \endcode |
94 |
94 |
95 /// \addtogroup gwrappers |
95 \addtogroup gwrappers |
96 /// @{ |
96 @{ |
97 |
97 |
98 ///Base type for the Graph Wrappers |
98 Base type for the Graph Wrappers |
99 |
99 |
100 ///\warning Graph wrappers are in even more experimental state than the other |
100 \warning Graph wrappers are in even more experimental state than the other |
101 ///parts of the lib. Use them at you own risk. |
101 parts of the lib. Use them at you own risk. |
102 /// |
102 |
103 /// This is the base type for most of LEMON graph wrappers. |
103 This is the base type for most of LEMON graph wrappers. |
104 /// This class implements a trivial graph wrapper i.e. it only wraps the |
104 This class implements a trivial graph wrapper i.e. it only wraps the |
105 /// functions and types of the graph. The purpose of this class is to |
105 functions and types of the graph. The purpose of this class is to |
106 /// make easier implementing graph wrappers. E.g. if a wrapper is |
106 make easier implementing graph wrappers. E.g. if a wrapper is |
107 /// considered which differs from the wrapped graph only in some of its |
107 considered which differs from the wrapped graph only in some of its |
108 /// functions or types, then it can be derived from GraphWrapper, and only the |
108 functions or types, then it can be derived from GraphWrapper, and only the |
109 /// differences should be implemented. |
109 differences should be implemented. |
110 /// |
110 |
111 ///\author Marton Makai |
111 \author Marton Makai |
|
112 */ |
112 template<typename _Graph> |
113 template<typename _Graph> |
113 class GraphWrapperBase { |
114 class GraphWrapperBase { |
114 public: |
115 public: |
115 typedef _Graph Graph; |
116 typedef _Graph Graph; |
116 /// \todo Is it needed? |
117 /// \todo Is it needed? |