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