alpar@2391: /* -*- C++ -*-
alpar@2391:  *
alpar@2391:  * This file is a part of LEMON, a generic C++ optimization library
alpar@2391:  *
alpar@2391:  * Copyright (C) 2003-2007
alpar@2391:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@2391:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@2391:  *
alpar@2391:  * Permission to use, modify and distribute this software is granted
alpar@2391:  * provided that this copyright notice appears in all copies. For
alpar@2391:  * precise terms see the accompanying LICENSE file.
alpar@2391:  *
alpar@2391:  * This software is provided "AS IS" with no warranty of any kind,
alpar@2391:  * express or implied, and with no claim as to its suitability for any
alpar@2391:  * purpose.
alpar@2391:  *
alpar@2391:  */
alpar@2391: 
marci@1172: /**
alpar@1401:    @defgroup graph_adaptors Adaptor Classes for Graphs
alpar@1949:    @ingroup graphs
alpar@1401:    \brief This group contains several adaptor classes for graphs
marci@556:    
marci@1172:    The main parts of LEMON are the different graph structures, 
marci@1172:    generic graph algorithms, graph concepts which couple these, and 
alpar@1401:    graph adaptors. While the previous notions are more or less clear, the 
marci@1252:    latter one needs further explanation. 
alpar@1401:    Graph adaptors are graph classes which serve for considering graph 
marci@1252:    structures in different ways. 
marci@1252: 
marci@1252:    A short example makes this much 
marci@1172:    clearer. 
marci@1172:    Suppose that we have an instance \c g of a directed graph
marci@1252:    type say ListGraph and an algorithm 
marci@1172:    \code template<typename Graph> int algorithm(const Graph&); \endcode 
marci@1252:    is needed to run on the reversed oriented graph. 
marci@1172:    It may be expensive (in time or in memory usage) to copy 
marci@1252:    \c g with the reversed orientation. 
alpar@1401:    In this case, an adaptor class is used, which 
marci@1252:    (according to LEMON graph concepts) works as a graph. 
alpar@1401:    The adaptor uses 
marci@1252:    the original graph structure and graph operations when methods of the 
marci@1252:    reversed oriented graph are called. 
alpar@1401:    This means that the adaptor have minor memory usage, 
marci@1252:    and do not perform sophisticated algorithmic actions. 
marci@1252:    The purpose of it is to give a tool for the cases when 
marci@1252:    a graph have to be used in a specific alteration. 
marci@1252:    If this alteration is obtained by a usual construction 
marci@1252:    like filtering the edge-set or considering a new orientation, then 
alpar@1401:    an adaptor is worthwhile to use. 
marci@1252:    To come back to the reversed oriented graph, in this situation 
alpar@1401:    \code template<typename Graph> class RevGraphAdaptor; \endcode 
marci@1252:    template class can be used. 
marci@1252:    The code looks as follows 
marci@1172:    \code
marci@1172:    ListGraph g;
deba@2084:    RevGraphAdaptor<ListGraph> rga(g);
deba@2084:    int result=algorithm(rga);
marci@1172:    \endcode
marci@1172:    After running the algorithm, the original graph \c g 
marci@1252:    is untouched. 
marci@1172:    This techniques gives rise to an elegant code, and 
alpar@1401:    based on stable graph adaptors, complex algorithms can be 
marci@1172:    implemented easily. 
marci@1252: 
marci@1172:    In flow, circulation and bipartite matching problems, the residual 
alpar@1401:    graph is of particular importance. Combining an adaptor implementing 
marci@1172:    this, shortest path algorithms and minimum mean cycle algorithms, 
marci@1172:    a range of weighted and cardinality optimization algorithms can be 
marci@1252:    obtained. 
marci@1252:    For other examples, 
marci@1252:    the interested user is referred to the detailed documentation of 
alpar@1401:    particular adaptors. 
marci@1252: 
alpar@1401:    The behavior of graph adaptors can be very different. Some of them keep 
marci@1172:    capabilities of the original graph while in other cases this would be 
marci@1252:    meaningless. This means that the concepts that they are models of depend 
alpar@1401:    on the graph adaptor, and the wrapped graph(s). 
deba@2084:    If an edge of \c rga is deleted, this is carried out by 
alpar@1401:    deleting the corresponding edge of \c g, thus the adaptor modifies the 
marci@1252:    original graph. 
marci@1252:    But for a residual 
marci@1172:    graph, this operation has no sense. 
marci@1252:    Let us stand one more example here to simplify your work. 
alpar@1401:    RevGraphAdaptor has constructor 
marci@1252:    \code 
alpar@1401:    RevGraphAdaptor(Graph& _g);
marci@1252:    \endcode
marci@1172:    This means that in a situation, 
marci@1172:    when a <tt> const ListGraph& </tt> reference to a graph is given, 
marci@1172:    then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
marci@1172:    \code
marci@1172:    int algorithm1(const ListGraph& g) {
deba@2084:    RevGraphAdaptor<const ListGraph> rga(g);
deba@2084:    return algorithm2(rga);
marci@1172:    }
marci@1172:    \endcode
marci@1172: */