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