doc/gwrappers.dox
author alpar
Sat, 19 Mar 2005 09:38:31 +0000
changeset 1227 01f668e3e168
parent 1164 80bb73097736
child 1252 4fee8e9d9014
permissions -rw-r--r--
- A primitive function type interface for Preflow.
- A compilation bug fixed
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
*/