Changeset 432:76287c8caa26 in lemon for doc/groups.dox
 Timestamp:
 11/30/08 19:18:32 (12 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

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