Changeset 1252:4fee8e9d9014 in lemon0.x for doc/gwrappers.dox
 Timestamp:
 03/23/05 17:59:13 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1679
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

doc/gwrappers.dox
r1172 r1252 6 6 The main parts of LEMON are the different graph structures, 7 7 generic graph algorithms, graph concepts which couple these, and 8 graph wrappers. While the previous ones are more or less clear, the9 latter notion needs further explanation.8 graph wrappers. While the previous notions are more or less clear, the 9 latter one needs further explanation. 10 10 Graph wrappers are graph classes which serve for considering graph 11 structures in different ways. A short example makes the notion much 11 structures in different ways. 12 13 A short example makes this much 12 14 clearer. 13 15 Suppose that we have an instance \c g of a directed graph 14 type say \cListGraph and an algorithm16 type say ListGraph and an algorithm 15 17 \code template<typename Graph> int algorithm(const Graph&); \endcode 16 is needed to run on the reverse lyoriented graph.18 is needed to run on the reversed oriented graph. 17 19 It may be expensive (in time or in memory usage) to copy 18 \c g with the reverse orientation. 19 Thus, a wrapper class 20 \code template<typename Graph> class RevGraphWrapper; \endcode is used. 21 The code looks as follows 20 \c g with the reversed orientation. 21 In this case, a wrapper class is used, which 22 (according to LEMON graph concepts) works as a graph. 23 The wrapper uses 24 the original graph structure and graph operations when methods of the 25 reversed oriented graph are called. 26 This means that the wrapper have minor memory usage, 27 and do not perform sophisticated algorithmic actions. 28 The purpose of it is to give a tool for the cases when 29 a graph have to be used in a specific alteration. 30 If this alteration is obtained by a usual construction 31 like filtering the edgeset or considering a new orientation, then 32 a wrapper is worthwhile to use. 33 To come back to the reversed oriented graph, in this situation 34 \code template<typename Graph> class RevGraphWrapper; \endcode 35 template class can be used. 36 The code looks as follows 22 37 \code 23 38 ListGraph g; … … 26 41 \endcode 27 42 After running the algorithm, the original graph \c g 28 remains untouched. Thus the graph wrapper used above is to consider the 29 original graph with reverse orientation. 43 is untouched. 30 44 This techniques gives rise to an elegant code, and 31 45 based on stable graph wrappers, complex algorithms can be 32 46 implemented easily. 47 33 48 In flow, circulation and bipartite matching problems, the residual 34 49 graph is of particular importance. Combining a wrapper implementing 35 50 this, shortest path algorithms and minimum mean cycle algorithms, 36 51 a range of weighted and cardinality optimization algorithms can be 37 obtained. For lack of space, for other examples, 38 the interested user is referred to the detailed documentation of graph 39 wrappers. 52 obtained. 53 For other examples, 54 the interested user is referred to the detailed documentation of 55 particular wrappers. 56 40 57 The behavior of graph wrappers can be very different. Some of them keep 41 58 capabilities of the original graph while in other cases this would be 42 meaningless. This means that the concepts that they are a modelof depend59 meaningless. This means that the concepts that they are models of depend 43 60 on the graph wrapper, and the wrapped graph(s). 44 61 If an edge of \c rgw is deleted, this is carried out by 45 deleting the corresponding edge of \c g. But for a residual 62 deleting the corresponding edge of \c g, thus the wrapper modifies the 63 original graph. 64 But for a residual 46 65 graph, this operation has no sense. 47 Let westand one more example here to simplify your work.48 wrapper class49 \code template<typename Graph> class RevGraphWrapper; \endcode50 has constructor51 <tt> RevGraphWrapper(Graph& _g)</tt>.66 Let us stand one more example here to simplify your work. 67 RevGraphWrapper has constructor 68 \code 69 RevGraphWrapper(Graph& _g); 70 \endcode 52 71 This means that in a situation, 53 72 when a <tt> const ListGraph& </tt> reference to a graph is given,
Note: See TracChangeset
for help on using the changeset viewer.