Changeset 1004:b94037830dc8 in lemon0.x for src/lemon/graph_wrapper.h
 Timestamp:
 11/17/04 20:56:46 (16 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1394
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/lemon/graph_wrapper.h
r998 r1004 36 36 // Graph wrappers 37 37 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 */ 112 113 template<typename _Graph> 113 114 class GraphWrapperBase {
Note: See TracChangeset
for help on using the changeset viewer.