src/lemon/graph_wrapper.h
changeset 1194 7bce0ef61d6b
parent 1164 80bb73097736
child 1198 6f1604392dc8
equal deleted inserted replaced
17:603c14e2f4a8 18:c2889b303ea2
    32 
    32 
    33 namespace lemon {
    33 namespace lemon {
    34 
    34 
    35   // Graph wrappers
    35   // Graph wrappers
    36 
    36 
    37   /*! \addtogroup gwrappers
    37   /*!
    38     The main parts of LEMON are the different graph structures, 
       
    39     generic graph algorithms, graph concepts which couple these, and 
       
    40     graph wrappers. While the previous ones are more or less clear, the 
       
    41     latter notion needs further explanation.
       
    42     Graph wrappers are graph classes which serve for considering graph 
       
    43     structures in different ways. A short example makes the notion much 
       
    44     clearer. 
       
    45     Suppose that we have an instance \c g of a directed graph
       
    46     type say \c ListGraph and an algorithm 
       
    47     \code template<typename Graph> int algorithm(const Graph&); \endcode 
       
    48     is needed to run on the reversely oriented graph. 
       
    49     It may be expensive (in time or in memory usage) to copy 
       
    50     \c g with the reverse orientation. 
       
    51     Thus, a wrapper class
       
    52     \code template<typename Graph> class RevGraphWrapper; \endcode is used. 
       
    53     The code looks as follows
       
    54     \code
       
    55     ListGraph g;
       
    56     RevGraphWrapper<ListGraph> rgw(g);
       
    57     int result=algorithm(rgw);
       
    58     \endcode
       
    59     After running the algorithm, the original graph \c g 
       
    60     remains untouched. Thus the graph wrapper used above is to consider the 
       
    61     original graph with reverse orientation. 
       
    62     This techniques gives rise to an elegant code, and 
       
    63     based on stable graph wrappers, complex algorithms can be 
       
    64     implemented easily. 
       
    65     In flow, circulation and bipartite matching problems, the residual 
       
    66     graph is of particular importance. Combining a wrapper implementing 
       
    67     this, shortest path algorithms and minimum mean cycle algorithms, 
       
    68     a range of weighted and cardinality optimization algorithms can be 
       
    69     obtained. For lack of space, for other examples, 
       
    70     the interested user is referred to the detailed documentation of graph 
       
    71     wrappers. 
       
    72     The behavior of graph wrappers can be very different. Some of them keep 
       
    73     capabilities of the original graph while in other cases this would be 
       
    74     meaningless. This means that the concepts that they are a model of depend 
       
    75     on the graph wrapper, and the wrapped graph(s). 
       
    76     If an edge of \c rgw is deleted, this is carried out by 
       
    77     deleting the corresponding edge of \c g. But for a residual 
       
    78     graph, this operation has no sense. 
       
    79     Let we stand one more example here to simplify your work. 
       
    80     wrapper class
       
    81     \code template<typename Graph> class RevGraphWrapper; \endcode 
       
    82     has constructor 
       
    83     <tt> RevGraphWrapper(Graph& _g)</tt>. 
       
    84     This means that in a situation, 
       
    85     when a <tt> const ListGraph& </tt> reference to a graph is given, 
       
    86     then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
       
    87     \code
       
    88     int algorithm1(const ListGraph& g) {
       
    89     RevGraphWrapper<const ListGraph> rgw(g);
       
    90     return algorithm2(rgw);
       
    91     }
       
    92     \endcode
       
    93 
       
    94     \addtogroup gwrappers
    38     \addtogroup gwrappers
    95     @{
    39     @{
    96 
    40    */
       
    41 
       
    42   /*! 
    97     Base type for the Graph Wrappers
    43     Base type for the Graph Wrappers
    98 
    44 
    99     \warning Graph wrappers are in even more experimental state than the other
    45     \warning Graph wrappers are in even more experimental state than the other
   100     parts of the lib. Use them at you own risk.
    46     parts of the lib. Use them at you own risk.
   101   
    47