doc/graph-adaptors.dox
author deba
Wed, 01 Mar 2006 10:25:30 +0000
changeset 1991 d7442141d9ef
parent 1401 9588dcef6793
child 2084 59769591eb60
permissions -rw-r--r--
The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor, where
we have to proxy the signals from the graph.

The SubBidirGraphAdaptor is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor<UndirGraphAdaptor<Graph>>.

The ResGraphAdaptor is based on this composition.
marci@1172
     1
/**
alpar@1401
     2
   @defgroup graph_adaptors Adaptor Classes for Graphs
alpar@1949
     3
   @ingroup graphs
alpar@1401
     4
   \brief This group contains several adaptor classes for 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
*/