marci@1172
|
1 |
/**
|
marci@1172
|
2 |
@defgroup gwrappers Wrapper Classes for Graphs
|
marci@1172
|
3 |
\brief This group contains several wrapper classes for graphs
|
marci@1172
|
4 |
@ingroup 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
|
marci@1172
|
8 |
graph wrappers. While the previous ones are more or less clear, the
|
marci@1172
|
9 |
latter notion needs further explanation.
|
marci@1172
|
10 |
Graph wrappers are graph classes which serve for considering graph
|
marci@1172
|
11 |
structures in different ways. A short example makes the notion much
|
marci@1172
|
12 |
clearer.
|
marci@1172
|
13 |
Suppose that we have an instance \c g of a directed graph
|
marci@1172
|
14 |
type say \c ListGraph and an algorithm
|
marci@1172
|
15 |
\code template<typename Graph> int algorithm(const Graph&); \endcode
|
marci@1172
|
16 |
is needed to run on the reversely oriented graph.
|
marci@1172
|
17 |
It may be expensive (in time or in memory usage) to copy
|
marci@1172
|
18 |
\c g with the reverse orientation.
|
marci@1172
|
19 |
Thus, a wrapper class
|
marci@1172
|
20 |
\code template<typename Graph> class RevGraphWrapper; \endcode is used.
|
marci@1172
|
21 |
The code looks as follows
|
marci@1172
|
22 |
\code
|
marci@1172
|
23 |
ListGraph g;
|
marci@1172
|
24 |
RevGraphWrapper<ListGraph> rgw(g);
|
marci@1172
|
25 |
int result=algorithm(rgw);
|
marci@1172
|
26 |
\endcode
|
marci@1172
|
27 |
After running the algorithm, the original graph \c g
|
marci@1172
|
28 |
remains untouched. Thus the graph wrapper used above is to consider the
|
marci@1172
|
29 |
original graph with reverse orientation.
|
marci@1172
|
30 |
This techniques gives rise to an elegant code, and
|
marci@1172
|
31 |
based on stable graph wrappers, complex algorithms can be
|
marci@1172
|
32 |
implemented easily.
|
marci@1172
|
33 |
In flow, circulation and bipartite matching problems, the residual
|
marci@1172
|
34 |
graph is of particular importance. Combining a wrapper implementing
|
marci@1172
|
35 |
this, shortest path algorithms and minimum mean cycle algorithms,
|
marci@1172
|
36 |
a range of weighted and cardinality optimization algorithms can be
|
marci@1172
|
37 |
obtained. For lack of space, for other examples,
|
marci@1172
|
38 |
the interested user is referred to the detailed documentation of graph
|
marci@1172
|
39 |
wrappers.
|
marci@1172
|
40 |
The behavior of graph wrappers can be very different. Some of them keep
|
marci@1172
|
41 |
capabilities of the original graph while in other cases this would be
|
marci@1172
|
42 |
meaningless. This means that the concepts that they are a model of depend
|
marci@1172
|
43 |
on the graph wrapper, and the wrapped graph(s).
|
marci@1172
|
44 |
If an edge of \c rgw is deleted, this is carried out by
|
marci@1172
|
45 |
deleting the corresponding edge of \c g. But for a residual
|
marci@1172
|
46 |
graph, this operation has no sense.
|
marci@1172
|
47 |
Let we stand one more example here to simplify your work.
|
marci@1172
|
48 |
wrapper class
|
marci@1172
|
49 |
\code template<typename Graph> class RevGraphWrapper; \endcode
|
marci@1172
|
50 |
has constructor
|
marci@1172
|
51 |
<tt> RevGraphWrapper(Graph& _g)</tt>.
|
marci@1172
|
52 |
This means that in a situation,
|
marci@1172
|
53 |
when a <tt> const ListGraph& </tt> reference to a graph is given,
|
marci@1172
|
54 |
then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
|
marci@1172
|
55 |
\code
|
marci@1172
|
56 |
int algorithm1(const ListGraph& g) {
|
marci@1172
|
57 |
RevGraphWrapper<const ListGraph> rgw(g);
|
marci@1172
|
58 |
return algorithm2(rgw);
|
marci@1172
|
59 |
}
|
marci@1172
|
60 |
\endcode
|
marci@1172
|
61 |
*/
|