COIN-OR::LEMON - Graph Library

Changeset 1004:b94037830dc8 in lemon-0.x


Ignore:
Timestamp:
11/17/04 20:56:46 (19 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1394
Message:

misc

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/graph_wrapper.h

    r998 r1004  
    3636  // Graph wrappers
    3737
    38   /// \addtogroup gwrappers
    39   /// The main parts of LEMON are the different graph structures,
    40   /// generic graph algorithms, graph concepts which couple these, and
    41   /// graph wrappers. While the previous ones are more or less clear, the
    42   /// latter notion needs further explanation.
    43   /// Graph wrappers are graph classes which serve for considering graph
    44   /// structures in different ways. A short example makes the notion much
    45   /// clearer.
    46   /// Suppose that we have an instance \c g of a directed graph
    47   /// type say \c ListGraph and an algorithm
    48   /// \code template<typename Graph> int algorithm(const Graph&); \endcode
    49   /// is needed to run on the reversely oriented graph.
    50   /// It may be expensive (in time or in memory usage) to copy
    51   /// \c g with the reverse orientation.
    52   /// Thus, a wrapper class
    53   /// \code template<typename Graph> class RevGraphWrapper; \endcode is used.
    54   /// The code looks as follows
    55   /// \code
    56   /// ListGraph g;
    57   /// RevGraphWrapper<ListGraph> rgw(g);
    58   /// int result=algorithm(rgw);
    59   /// \endcode
    60   /// After running the algorithm, the original graph \c g
    61   /// remains untouched. Thus the graph wrapper used above is to consider the
    62   /// original graph with reverse orientation.
    63   /// This techniques gives rise to an elegant code, and
    64   /// based on stable graph wrappers, complex algorithms can be
    65   /// implemented easily.
    66   /// In flow, circulation and bipartite matching problems, the residual
    67   /// graph is of particular importance. Combining a wrapper implementing
    68   /// this, shortest path algorithms and minimum mean cycle algorithms,
    69   /// a range of weighted and cardinality optimization algorithms can be
    70   /// obtained. For lack of space, for other examples,
    71   /// the interested user is referred to the detailed documentation of graph
    72   /// wrappers.
    73   /// The behavior of graph wrappers can be very different. Some of them keep
    74   /// capabilities of the original graph while in other cases this would be
    75   /// meaningless. This means that the concepts that they are a model of depend
    76   /// on the graph wrapper, and the wrapped graph(s).
    77   /// If an edge of \c rgw is deleted, this is carried out by
    78   /// deleting the corresponding edge of \c g. But for a residual
    79   /// graph, this operation has no sense.
    80   /// Let we stand one more example here to simplify your work.
    81   /// wrapper class
    82   /// \code template<typename Graph> class RevGraphWrapper; \endcode
    83   /// has constructor
    84   /// <tt> RevGraphWrapper(Graph& _g)</tt>.
    85   /// This means that in a situation,
    86   /// when a <tt> const ListGraph& </tt> reference to a graph is given,
    87   /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
    88   /// \code
    89   /// int algorithm1(const ListGraph& g) {
    90   ///   RevGraphWrapper<const ListGraph> rgw(g);
    91   ///   return algorithm2(rgw);
    92   /// }
    93   /// \endcode
    94 
    95   /// \addtogroup gwrappers
    96   /// @{
    97 
    98   ///Base type for the Graph Wrappers
    99 
    100   ///\warning Graph wrappers are in even more experimental state than the other
    101   ///parts of the lib. Use them at you own risk.
    102   ///
    103   /// This is the base type for most of LEMON graph wrappers.
    104   /// This class implements a trivial graph wrapper i.e. it only wraps the
    105   /// functions and types of the graph. The purpose of this class is to
    106   /// make easier implementing graph wrappers. E.g. if a wrapper is
    107   /// considered which differs from the wrapped graph only in some of its
    108   /// functions or types, then it can be derived from GraphWrapper, and only the
    109   /// differences should be implemented.
    110   ///
    111   ///\author Marton Makai
     38  /*! \addtogroup gwrappers
     39    The main parts of LEMON are the different graph structures,
     40    generic graph algorithms, graph concepts which couple these, and
     41    graph wrappers. While the previous ones are more or less clear, the
     42    latter notion needs further explanation.
     43    Graph wrappers are graph classes which serve for considering graph
     44    structures in different ways. A short example makes the notion much
     45    clearer.
     46    Suppose that we have an instance \c g of a directed graph
     47    type say \c ListGraph and an algorithm
     48    \code template<typename Graph> int algorithm(const Graph&); \endcode
     49    is needed to run on the reversely oriented graph.
     50    It may be expensive (in time or in memory usage) to copy
     51    \c g with the reverse orientation.
     52    Thus, a wrapper class
     53    \code template<typename Graph> class RevGraphWrapper; \endcode is used.
     54    The code looks as follows
     55    \code
     56    ListGraph g;
     57    RevGraphWrapper<ListGraph> rgw(g);
     58    int result=algorithm(rgw);
     59    \endcode
     60    After running the algorithm, the original graph \c g
     61    remains untouched. Thus the graph wrapper used above is to consider the
     62    original graph with reverse orientation.
     63    This techniques gives rise to an elegant code, and
     64    based on stable graph wrappers, complex algorithms can be
     65    implemented easily.
     66    In flow, circulation and bipartite matching problems, the residual
     67    graph is of particular importance. Combining a wrapper implementing
     68    this, shortest path algorithms and minimum mean cycle algorithms,
     69    a range of weighted and cardinality optimization algorithms can be
     70    obtained. For lack of space, for other examples,
     71    the interested user is referred to the detailed documentation of graph
     72    wrappers.
     73    The behavior of graph wrappers can be very different. Some of them keep
     74    capabilities of the original graph while in other cases this would be
     75    meaningless. This means that the concepts that they are a model of depend
     76    on the graph wrapper, and the wrapped graph(s).
     77    If an edge of \c rgw is deleted, this is carried out by
     78    deleting the corresponding edge of \c g. But for a residual
     79    graph, this operation has no sense.
     80    Let we stand one more example here to simplify your work.
     81    wrapper class
     82    \code template<typename Graph> class RevGraphWrapper; \endcode
     83    has constructor
     84    <tt> RevGraphWrapper(Graph& _g)</tt>.
     85    This means that in a situation,
     86    when a <tt> const ListGraph& </tt> reference to a graph is given,
     87    then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
     88    \code
     89    int algorithm1(const ListGraph& g) {
     90    RevGraphWrapper<const ListGraph> rgw(g);
     91    return algorithm2(rgw);
     92    }
     93    \endcode
     94
     95    \addtogroup gwrappers
     96    @{
     97
     98    Base type for the Graph Wrappers
     99
     100    \warning Graph wrappers are in even more experimental state than the other
     101    parts of the lib. Use them at you own risk.
     102 
     103    This is the base type for most of LEMON graph wrappers.
     104    This class implements a trivial graph wrapper i.e. it only wraps the
     105    functions and types of the graph. The purpose of this class is to
     106    make easier implementing graph wrappers. E.g. if a wrapper is
     107    considered which differs from the wrapped graph only in some of its
     108    functions or types, then it can be derived from GraphWrapper, and only the
     109    differences should be implemented.
     110 
     111    \author Marton Makai
     112  */
    112113  template<typename _Graph>
    113114  class GraphWrapperBase {
Note: See TracChangeset for help on using the changeset viewer.