Changeset 451:fbd6e04acf44 in lemon1.2 for doc/groups.dox
 Timestamp:
 01/09/09 12:54:27 (11 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

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