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