doc/graph-adaptors.dox
author alpar
Fri, 03 Feb 2006 09:18:17 +0000
changeset 1949 5db4ff8d69de
parent 1401 9588dcef6793
child 2084 59769591eb60
permissions -rw-r--r--
Fight with Doxygen.
Victory hasn't been reached yet, but it's on the horizon.
     1 /**
     2    @defgroup graph_adaptors Adaptor Classes for Graphs
     3    @ingroup graphs
     4    \brief This group contains several adaptor classes for graphs
     5    
     6    The main parts of LEMON are the different graph structures, 
     7    generic graph algorithms, graph concepts which couple these, and 
     8    graph adaptors. While the previous notions are more or less clear, the 
     9    latter one needs further explanation. 
    10    Graph adaptors are graph classes which serve for considering graph 
    11    structures in different ways. 
    12 
    13    A short example makes this much 
    14    clearer. 
    15    Suppose that we have an instance \c g of a directed graph
    16    type say ListGraph and an algorithm 
    17    \code template<typename Graph> int algorithm(const Graph&); \endcode 
    18    is needed to run on the reversed oriented graph. 
    19    It may be expensive (in time or in memory usage) to copy 
    20    \c g with the reversed orientation. 
    21    In this case, an adaptor class is used, which 
    22    (according to LEMON graph concepts) works as a graph. 
    23    The adaptor uses 
    24    the original graph structure and graph operations when methods of the 
    25    reversed oriented graph are called. 
    26    This means that the adaptor have minor memory usage, 
    27    and do not perform sophisticated algorithmic actions. 
    28    The purpose of it is to give a tool for the cases when 
    29    a graph have to be used in a specific alteration. 
    30    If this alteration is obtained by a usual construction 
    31    like filtering the edge-set or considering a new orientation, then 
    32    an adaptor is worthwhile to use. 
    33    To come back to the reversed oriented graph, in this situation 
    34    \code template<typename Graph> class RevGraphAdaptor; \endcode 
    35    template class can be used. 
    36    The code looks as follows 
    37    \code
    38    ListGraph g;
    39    RevGraphAdaptor<ListGraph> rgw(g);
    40    int result=algorithm(rgw);
    41    \endcode
    42    After running the algorithm, the original graph \c g 
    43    is untouched. 
    44    This techniques gives rise to an elegant code, and 
    45    based on stable graph adaptors, complex algorithms can be 
    46    implemented easily. 
    47 
    48    In flow, circulation and bipartite matching problems, the residual 
    49    graph is of particular importance. Combining an adaptor implementing 
    50    this, shortest path algorithms and minimum mean cycle algorithms, 
    51    a range of weighted and cardinality optimization algorithms can be 
    52    obtained. 
    53    For other examples, 
    54    the interested user is referred to the detailed documentation of 
    55    particular adaptors. 
    56 
    57    The behavior of graph adaptors can be very different. Some of them keep 
    58    capabilities of the original graph while in other cases this would be 
    59    meaningless. This means that the concepts that they are models of depend 
    60    on the graph adaptor, and the wrapped graph(s). 
    61    If an edge of \c rgw is deleted, this is carried out by 
    62    deleting the corresponding edge of \c g, thus the adaptor modifies the 
    63    original graph. 
    64    But for a residual 
    65    graph, this operation has no sense. 
    66    Let us stand one more example here to simplify your work. 
    67    RevGraphAdaptor has constructor 
    68    \code 
    69    RevGraphAdaptor(Graph& _g);
    70    \endcode
    71    This means that in a situation, 
    72    when a <tt> const ListGraph& </tt> reference to a graph is given, 
    73    then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
    74    \code
    75    int algorithm1(const ListGraph& g) {
    76    RevGraphAdaptor<const ListGraph> rgw(g);
    77    return algorithm2(rgw);
    78    }
    79    \endcode
    80 */