1 /** |
1 /** |
2 @defgroup gwrappers Wrapper Classes for Graphs |
2 @defgroup graph_adaptors Adaptor Classes for Graphs |
3 \brief This group contains several wrapper classes for graphs |
3 \brief This group contains several adaptor classes for graphs |
4 @ingroup graphs |
4 @ingroup graphs |
5 |
5 |
6 The main parts of LEMON are the different graph structures, |
6 The main parts of LEMON are the different graph structures, |
7 generic graph algorithms, graph concepts which couple these, and |
7 generic graph algorithms, graph concepts which couple these, and |
8 graph wrappers. While the previous notions are more or less clear, the |
8 graph adaptors. While the previous notions are more or less clear, the |
9 latter one needs further explanation. |
9 latter one needs further explanation. |
10 Graph wrappers are graph classes which serve for considering graph |
10 Graph adaptors are graph classes which serve for considering graph |
11 structures in different ways. |
11 structures in different ways. |
12 |
12 |
13 A short example makes this much |
13 A short example makes this much |
14 clearer. |
14 clearer. |
15 Suppose that we have an instance \c g of a directed graph |
15 Suppose that we have an instance \c g of a directed graph |
16 type say ListGraph and an algorithm |
16 type say ListGraph and an algorithm |
17 \code template<typename Graph> int algorithm(const Graph&); \endcode |
17 \code template<typename Graph> int algorithm(const Graph&); \endcode |
18 is needed to run on the reversed oriented graph. |
18 is needed to run on the reversed oriented graph. |
19 It may be expensive (in time or in memory usage) to copy |
19 It may be expensive (in time or in memory usage) to copy |
20 \c g with the reversed orientation. |
20 \c g with the reversed orientation. |
21 In this case, a wrapper class is used, which |
21 In this case, an adaptor class is used, which |
22 (according to LEMON graph concepts) works as a graph. |
22 (according to LEMON graph concepts) works as a graph. |
23 The wrapper uses |
23 The adaptor uses |
24 the original graph structure and graph operations when methods of the |
24 the original graph structure and graph operations when methods of the |
25 reversed oriented graph are called. |
25 reversed oriented graph are called. |
26 This means that the wrapper have minor memory usage, |
26 This means that the adaptor have minor memory usage, |
27 and do not perform sophisticated algorithmic actions. |
27 and do not perform sophisticated algorithmic actions. |
28 The purpose of it is to give a tool for the cases when |
28 The purpose of it is to give a tool for the cases when |
29 a graph have to be used in a specific alteration. |
29 a graph have to be used in a specific alteration. |
30 If this alteration is obtained by a usual construction |
30 If this alteration is obtained by a usual construction |
31 like filtering the edge-set or considering a new orientation, then |
31 like filtering the edge-set or considering a new orientation, then |
32 a wrapper is worthwhile to use. |
32 an adaptor is worthwhile to use. |
33 To come back to the reversed oriented graph, in this situation |
33 To come back to the reversed oriented graph, in this situation |
34 \code template<typename Graph> class RevGraphWrapper; \endcode |
34 \code template<typename Graph> class RevGraphAdaptor; \endcode |
35 template class can be used. |
35 template class can be used. |
36 The code looks as follows |
36 The code looks as follows |
37 \code |
37 \code |
38 ListGraph g; |
38 ListGraph g; |
39 RevGraphWrapper<ListGraph> rgw(g); |
39 RevGraphAdaptor<ListGraph> rgw(g); |
40 int result=algorithm(rgw); |
40 int result=algorithm(rgw); |
41 \endcode |
41 \endcode |
42 After running the algorithm, the original graph \c g |
42 After running the algorithm, the original graph \c g |
43 is untouched. |
43 is untouched. |
44 This techniques gives rise to an elegant code, and |
44 This techniques gives rise to an elegant code, and |
45 based on stable graph wrappers, complex algorithms can be |
45 based on stable graph adaptors, complex algorithms can be |
46 implemented easily. |
46 implemented easily. |
47 |
47 |
48 In flow, circulation and bipartite matching problems, the residual |
48 In flow, circulation and bipartite matching problems, the residual |
49 graph is of particular importance. Combining a wrapper implementing |
49 graph is of particular importance. Combining an adaptor implementing |
50 this, shortest path algorithms and minimum mean cycle algorithms, |
50 this, shortest path algorithms and minimum mean cycle algorithms, |
51 a range of weighted and cardinality optimization algorithms can be |
51 a range of weighted and cardinality optimization algorithms can be |
52 obtained. |
52 obtained. |
53 For other examples, |
53 For other examples, |
54 the interested user is referred to the detailed documentation of |
54 the interested user is referred to the detailed documentation of |
55 particular wrappers. |
55 particular adaptors. |
56 |
56 |
57 The behavior of graph wrappers can be very different. Some of them keep |
57 The behavior of graph adaptors can be very different. Some of them keep |
58 capabilities of the original graph while in other cases this would be |
58 capabilities of the original graph while in other cases this would be |
59 meaningless. This means that the concepts that they are models of depend |
59 meaningless. This means that the concepts that they are models of depend |
60 on the graph wrapper, and the wrapped graph(s). |
60 on the graph adaptor, and the wrapped graph(s). |
61 If an edge of \c rgw is deleted, this is carried out by |
61 If an edge of \c rgw is deleted, this is carried out by |
62 deleting the corresponding edge of \c g, thus the wrapper modifies the |
62 deleting the corresponding edge of \c g, thus the adaptor modifies the |
63 original graph. |
63 original graph. |
64 But for a residual |
64 But for a residual |
65 graph, this operation has no sense. |
65 graph, this operation has no sense. |
66 Let us stand one more example here to simplify your work. |
66 Let us stand one more example here to simplify your work. |
67 RevGraphWrapper has constructor |
67 RevGraphAdaptor has constructor |
68 \code |
68 \code |
69 RevGraphWrapper(Graph& _g); |
69 RevGraphAdaptor(Graph& _g); |
70 \endcode |
70 \endcode |
71 This means that in a situation, |
71 This means that in a situation, |
72 when a <tt> const ListGraph& </tt> reference to a graph is given, |
72 when a <tt> const ListGraph& </tt> reference to a graph is given, |
73 then it have to be instantiated with <tt>Graph=const ListGraph</tt>. |
73 then it have to be instantiated with <tt>Graph=const ListGraph</tt>. |
74 \code |
74 \code |
75 int algorithm1(const ListGraph& g) { |
75 int algorithm1(const ListGraph& g) { |
76 RevGraphWrapper<const ListGraph> rgw(g); |
76 RevGraphAdaptor<const ListGraph> rgw(g); |
77 return algorithm2(rgw); |
77 return algorithm2(rgw); |
78 } |
78 } |
79 \endcode |
79 \endcode |
80 */ |
80 */ |