doc/graph-adaptors.dox
author deba
Fri, 14 Oct 2005 10:58:54 +0000
changeset 1724 b20777184ba8
parent 1252 4fee8e9d9014
child 1949 5db4ff8d69de
permissions -rw-r--r--
Heap not for the dijkstra

It will be used in the minCut algorithm
marci@1172
     1
/**
alpar@1401
     2
   @defgroup graph_adaptors Adaptor Classes for Graphs
alpar@1401
     3
   \brief This group contains several adaptor 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 
alpar@1401
     8
   graph adaptors. While the previous notions are more or less clear, the 
marci@1252
     9
   latter one needs further explanation. 
alpar@1401
    10
   Graph adaptors 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. 
alpar@1401
    21
   In this case, an adaptor class is used, which 
marci@1252
    22
   (according to LEMON graph concepts) works as a graph. 
alpar@1401
    23
   The adaptor uses 
marci@1252
    24
   the original graph structure and graph operations when methods of the 
marci@1252
    25
   reversed oriented graph are called. 
alpar@1401
    26
   This means that the adaptor 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 
alpar@1401
    32
   an adaptor is worthwhile to use. 
marci@1252
    33
   To come back to the reversed oriented graph, in this situation 
alpar@1401
    34
   \code template<typename Graph> class RevGraphAdaptor; \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;
alpar@1401
    39
   RevGraphAdaptor<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 
alpar@1401
    45
   based on stable graph adaptors, complex algorithms can be 
marci@1172
    46
   implemented easily. 
marci@1252
    47
marci@1172
    48
   In flow, circulation and bipartite matching problems, the residual 
alpar@1401
    49
   graph is of particular importance. Combining an adaptor 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 
alpar@1401
    55
   particular adaptors. 
marci@1252
    56
alpar@1401
    57
   The behavior of graph adaptors 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 
alpar@1401
    60
   on the graph adaptor, and the wrapped graph(s). 
marci@1172
    61
   If an edge of \c rgw is deleted, this is carried out by 
alpar@1401
    62
   deleting the corresponding edge of \c g, thus the adaptor 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. 
alpar@1401
    67
   RevGraphAdaptor has constructor 
marci@1252
    68
   \code 
alpar@1401
    69
   RevGraphAdaptor(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) {
alpar@1401
    76
   RevGraphAdaptor<const ListGraph> rgw(g);
marci@1172
    77
   return algorithm2(rgw);
marci@1172
    78
   }
marci@1172
    79
   \endcode
marci@1172
    80
*/