Changes in doc/groups.dox [406:a578265aa8a6:418:ad483acf1654] in lemon1.2
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

doc/groups.dox
r406 r418 60 60 61 61 <b>See also:</b> \ref graph_concepts "Graph Structure Concepts". 62 */ 63 64 /** 65 @defgroup graph_adaptors Adaptor Classes for graphs 66 @ingroup graphs 67 \brief This group contains several adaptor classes for digraphs and graphs 68 69 The main parts of LEMON are the different graph structures, generic 70 graph algorithms, graph concepts which couple these, and graph 71 adaptors. While the previous notions are more or less clear, the 72 latter one needs further explanation. Graph adaptors are graph classes 73 which serve for considering graph structures in different ways. 74 75 A short example makes this much clearer. Suppose that we have an 76 instance \c g of a directed graph type say ListDigraph and an algorithm 77 \code 78 template <typename Digraph> 79 int algorithm(const Digraph&); 80 \endcode 81 is needed to run on the reverse oriented graph. It may be expensive 82 (in time or in memory usage) to copy \c g with the reversed 83 arcs. In this case, an adaptor class is used, which (according 84 to LEMON digraph concepts) works as a digraph. The adaptor uses the 85 original digraph structure and digraph operations when methods of the 86 reversed oriented graph are called. This means that the adaptor have 87 minor memory usage, and do not perform sophisticated algorithmic 88 actions. The purpose of it is to give a tool for the cases when a 89 graph have to be used in a specific alteration. If this alteration is 90 obtained by a usual construction like filtering the arcset or 91 considering a new orientation, then an adaptor is worthwhile to use. 92 To come back to the reverse oriented graph, in this situation 93 \code 94 template<typename Digraph> class ReverseDigraph; 95 \endcode 96 template class can be used. The code looks as follows 97 \code 98 ListDigraph g; 99 ReverseDigraph<ListGraph> rg(g); 100 int result = algorithm(rg); 101 \endcode 102 After running the algorithm, the original graph \c g is untouched. 103 This techniques gives rise to an elegant code, and based on stable 104 graph adaptors, complex algorithms can be implemented easily. 105 106 In flow, circulation and bipartite matching problems, the residual 107 graph is of particular importance. Combining an adaptor implementing 108 this, shortest path algorithms and minimum mean cycle algorithms, 109 a range of weighted and cardinality optimization algorithms can be 110 obtained. For other examples, the interested user is referred to the 111 detailed documentation of particular adaptors. 112 113 The behavior of graph adaptors can be very different. Some of them keep 114 capabilities of the original graph while in other cases this would be 115 meaningless. This means that the concepts that they are models of depend 116 on the graph adaptor, and the wrapped graph(s). 117 If an arc of \c rg is deleted, this is carried out by deleting the 118 corresponding arc of \c g, thus the adaptor modifies the original graph. 119 120 But for a residual graph, this operation has no sense. 121 Let us stand one more example here to simplify your work. 122 RevGraphAdaptor has constructor 123 \code 124 ReverseDigraph(Digraph& digraph); 125 \endcode 126 This means that in a situation, when a <tt>const ListDigraph&</tt> 127 reference to a graph is given, then it have to be instantiated with 128 <tt>Digraph=const ListDigraph</tt>. 129 \code 130 int algorithm1(const ListDigraph& g) { 131 RevGraphAdaptor<const ListDigraph> rg(g); 132 return algorithm2(rg); 133 } 134 \endcode 62 135 */ 63 136
Note: See TracChangeset
for help on using the changeset viewer.