doc/gwrappers.dox
author deba
Tue, 12 Apr 2005 17:33:41 +0000
changeset 1342 e335eebdae5b
parent 1172 37338ae42a2b
permissions -rw-r--r--
Demo program
Dijkstra with reduced lengths
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@1252
     8
   graph wrappers. While the previous notions are more or less clear, the 
marci@1252
     9
   latter one needs further explanation. 
marci@1172
    10
   Graph wrappers 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. 
marci@1252
    21
   In this case, a wrapper class is used, which 
marci@1252
    22
   (according to LEMON graph concepts) works as a graph. 
marci@1252
    23
   The wrapper uses 
marci@1252
    24
   the original graph structure and graph operations when methods of the 
marci@1252
    25
   reversed oriented graph are called. 
marci@1252
    26
   This means that the wrapper 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 
marci@1252
    32
   a wrapper is worthwhile to use. 
marci@1252
    33
   To come back to the reversed oriented graph, in this situation 
marci@1252
    34
   \code template<typename Graph> class RevGraphWrapper; \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;
marci@1172
    39
   RevGraphWrapper<ListGraph> rgw(g);
marci@1172
    40
   int result=algorithm(rgw);
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 
marci@1172
    45
   based on stable graph wrappers, complex algorithms can be 
marci@1172
    46
   implemented easily. 
marci@1252
    47
marci@1172
    48
   In flow, circulation and bipartite matching problems, the residual 
marci@1172
    49
   graph is of particular importance. Combining a wrapper 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 
marci@1252
    55
   particular wrappers. 
marci@1252
    56
marci@1172
    57
   The behavior of graph wrappers 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 
marci@1172
    60
   on the graph wrapper, and the wrapped graph(s). 
marci@1172
    61
   If an edge of \c rgw is deleted, this is carried out by 
marci@1252
    62
   deleting the corresponding edge of \c g, thus the wrapper 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. 
marci@1252
    67
   RevGraphWrapper has constructor 
marci@1252
    68
   \code 
marci@1252
    69
   RevGraphWrapper(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) {
marci@1172
    76
   RevGraphWrapper<const ListGraph> rgw(g);
marci@1172
    77
   return algorithm2(rgw);
marci@1172
    78
   }
marci@1172
    79
   \endcode
marci@1172
    80
*/