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