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