1.1 --- a/src/lemon/graph_wrapper.h Wed Nov 17 19:47:08 2004 +0000
1.2 +++ b/src/lemon/graph_wrapper.h Wed Nov 17 19:56:46 2004 +0000
1.3 @@ -35,80 +35,81 @@
1.4
1.5 // Graph wrappers
1.6
1.7 - /// \addtogroup gwrappers
1.8 - /// The main parts of LEMON are the different graph structures,
1.9 - /// generic graph algorithms, graph concepts which couple these, and
1.10 - /// graph wrappers. While the previous ones are more or less clear, the
1.11 - /// latter notion needs further explanation.
1.12 - /// Graph wrappers are graph classes which serve for considering graph
1.13 - /// structures in different ways. A short example makes the notion much
1.14 - /// clearer.
1.15 - /// Suppose that we have an instance \c g of a directed graph
1.16 - /// type say \c ListGraph and an algorithm
1.17 - /// \code template<typename Graph> int algorithm(const Graph&); \endcode
1.18 - /// is needed to run on the reversely oriented graph.
1.19 - /// It may be expensive (in time or in memory usage) to copy
1.20 - /// \c g with the reverse orientation.
1.21 - /// Thus, a wrapper class
1.22 - /// \code template<typename Graph> class RevGraphWrapper; \endcode is used.
1.23 - /// The code looks as follows
1.24 - /// \code
1.25 - /// ListGraph g;
1.26 - /// RevGraphWrapper<ListGraph> rgw(g);
1.27 - /// int result=algorithm(rgw);
1.28 - /// \endcode
1.29 - /// After running the algorithm, the original graph \c g
1.30 - /// remains untouched. Thus the graph wrapper used above is to consider the
1.31 - /// original graph with reverse orientation.
1.32 - /// This techniques gives rise to an elegant code, and
1.33 - /// based on stable graph wrappers, complex algorithms can be
1.34 - /// implemented easily.
1.35 - /// In flow, circulation and bipartite matching problems, the residual
1.36 - /// graph is of particular importance. Combining a wrapper implementing
1.37 - /// this, shortest path algorithms and minimum mean cycle algorithms,
1.38 - /// a range of weighted and cardinality optimization algorithms can be
1.39 - /// obtained. For lack of space, for other examples,
1.40 - /// the interested user is referred to the detailed documentation of graph
1.41 - /// wrappers.
1.42 - /// The behavior of graph wrappers can be very different. Some of them keep
1.43 - /// capabilities of the original graph while in other cases this would be
1.44 - /// meaningless. This means that the concepts that they are a model of depend
1.45 - /// on the graph wrapper, and the wrapped graph(s).
1.46 - /// If an edge of \c rgw is deleted, this is carried out by
1.47 - /// deleting the corresponding edge of \c g. But for a residual
1.48 - /// graph, this operation has no sense.
1.49 - /// Let we stand one more example here to simplify your work.
1.50 - /// wrapper class
1.51 - /// \code template<typename Graph> class RevGraphWrapper; \endcode
1.52 - /// has constructor
1.53 - /// <tt> RevGraphWrapper(Graph& _g)</tt>.
1.54 - /// This means that in a situation,
1.55 - /// when a <tt> const ListGraph& </tt> reference to a graph is given,
1.56 - /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
1.57 - /// \code
1.58 - /// int algorithm1(const ListGraph& g) {
1.59 - /// RevGraphWrapper<const ListGraph> rgw(g);
1.60 - /// return algorithm2(rgw);
1.61 - /// }
1.62 - /// \endcode
1.63 + /*! \addtogroup gwrappers
1.64 + The main parts of LEMON are the different graph structures,
1.65 + generic graph algorithms, graph concepts which couple these, and
1.66 + graph wrappers. While the previous ones are more or less clear, the
1.67 + latter notion needs further explanation.
1.68 + Graph wrappers are graph classes which serve for considering graph
1.69 + structures in different ways. A short example makes the notion much
1.70 + clearer.
1.71 + Suppose that we have an instance \c g of a directed graph
1.72 + type say \c ListGraph and an algorithm
1.73 + \code template<typename Graph> int algorithm(const Graph&); \endcode
1.74 + is needed to run on the reversely oriented graph.
1.75 + It may be expensive (in time or in memory usage) to copy
1.76 + \c g with the reverse orientation.
1.77 + Thus, a wrapper class
1.78 + \code template<typename Graph> class RevGraphWrapper; \endcode is used.
1.79 + The code looks as follows
1.80 + \code
1.81 + ListGraph g;
1.82 + RevGraphWrapper<ListGraph> rgw(g);
1.83 + int result=algorithm(rgw);
1.84 + \endcode
1.85 + After running the algorithm, the original graph \c g
1.86 + remains untouched. Thus the graph wrapper used above is to consider the
1.87 + original graph with reverse orientation.
1.88 + This techniques gives rise to an elegant code, and
1.89 + based on stable graph wrappers, complex algorithms can be
1.90 + implemented easily.
1.91 + In flow, circulation and bipartite matching problems, the residual
1.92 + graph is of particular importance. Combining a wrapper implementing
1.93 + this, shortest path algorithms and minimum mean cycle algorithms,
1.94 + a range of weighted and cardinality optimization algorithms can be
1.95 + obtained. For lack of space, for other examples,
1.96 + the interested user is referred to the detailed documentation of graph
1.97 + wrappers.
1.98 + The behavior of graph wrappers can be very different. Some of them keep
1.99 + capabilities of the original graph while in other cases this would be
1.100 + meaningless. This means that the concepts that they are a model of depend
1.101 + on the graph wrapper, and the wrapped graph(s).
1.102 + If an edge of \c rgw is deleted, this is carried out by
1.103 + deleting the corresponding edge of \c g. But for a residual
1.104 + graph, this operation has no sense.
1.105 + Let we stand one more example here to simplify your work.
1.106 + wrapper class
1.107 + \code template<typename Graph> class RevGraphWrapper; \endcode
1.108 + has constructor
1.109 + <tt> RevGraphWrapper(Graph& _g)</tt>.
1.110 + This means that in a situation,
1.111 + when a <tt> const ListGraph& </tt> reference to a graph is given,
1.112 + then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
1.113 + \code
1.114 + int algorithm1(const ListGraph& g) {
1.115 + RevGraphWrapper<const ListGraph> rgw(g);
1.116 + return algorithm2(rgw);
1.117 + }
1.118 + \endcode
1.119
1.120 - /// \addtogroup gwrappers
1.121 - /// @{
1.122 + \addtogroup gwrappers
1.123 + @{
1.124
1.125 - ///Base type for the Graph Wrappers
1.126 + Base type for the Graph Wrappers
1.127
1.128 - ///\warning Graph wrappers are in even more experimental state than the other
1.129 - ///parts of the lib. Use them at you own risk.
1.130 - ///
1.131 - /// This is the base type for most of LEMON graph wrappers.
1.132 - /// This class implements a trivial graph wrapper i.e. it only wraps the
1.133 - /// functions and types of the graph. The purpose of this class is to
1.134 - /// make easier implementing graph wrappers. E.g. if a wrapper is
1.135 - /// considered which differs from the wrapped graph only in some of its
1.136 - /// functions or types, then it can be derived from GraphWrapper, and only the
1.137 - /// differences should be implemented.
1.138 - ///
1.139 - ///\author Marton Makai
1.140 + \warning Graph wrappers are in even more experimental state than the other
1.141 + parts of the lib. Use them at you own risk.
1.142 +
1.143 + This is the base type for most of LEMON graph wrappers.
1.144 + This class implements a trivial graph wrapper i.e. it only wraps the
1.145 + functions and types of the graph. The purpose of this class is to
1.146 + make easier implementing graph wrappers. E.g. if a wrapper is
1.147 + considered which differs from the wrapped graph only in some of its
1.148 + functions or types, then it can be derived from GraphWrapper, and only the
1.149 + differences should be implemented.
1.150 +
1.151 + \author Marton Makai
1.152 + */
1.153 template<typename _Graph>
1.154 class GraphWrapperBase {
1.155 public: