Changeset 1172:37338ae42a2b in lemon0.x for src/lemon/graph_wrapper.h
 Timestamp:
 02/23/05 23:00:05 (15 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1578
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/lemon/graph_wrapper.h
r1164 r1172 35 35 // Graph wrappers 36 36 37 /*! \addtogroup gwrappers 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 37 /*! 94 38 \addtogroup gwrappers 95 39 @{ 96 40 */ 41 42 /*! 97 43 Base type for the Graph Wrappers 98 44
Note: See TracChangeset
for help on using the changeset viewer.