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