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

 2 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, 
src/lemon/graph_wrapper.h
r1242 r1252 435 435 nonnegative edgelengths. Note that 436 436 the comprehension of the presented solution 437 need's some knowledge from elementarycombinatorial optimization.437 need's some elementary knowledge from combinatorial optimization. 438 438 439 439 If a single shortest path is to be 440 searched between two nodes\c s and \c t, then this can be done easily by441 applying the Dijkstra algorithm class. What happens, if a maximum number of440 searched between \c s and \c t, then this can be done easily by 441 applying the Dijkstra algorithm. What happens, if a maximum number of 442 442 edgedisjoint shortest paths is to be computed. It can be proved that an 443 443 edge can be in a shortest path if and only if it is tight with respect to … … 924 924 /// SubBidirGraphWrapper by considering everywhere true 925 925 /// valued maps both for forward_filter and backward_filter. 926 /// Finally, one of the most important applications of SubBidirGraphWrapper 926 /// 927 /// The most important application of SubBidirGraphWrapper 927 928 /// is ResGraphWrapper, which stands for the residual graph in directed 928 929 /// flow and circulation problems.
Note: See TracChangeset
for help on using the changeset viewer.