Changes in / [418:ad483acf1654:413:d8b87e9b90c3] in lemon1.2
 Files:

 5 deleted
 3 edited
Legend:
 Unmodified
 Added
 Removed

doc/groups.dox
r418 r406 60 60 61 61 <b>See also:</b> \ref graph_concepts "Graph Structure Concepts". 62 */63 64 /**65 @defgroup graph_adaptors Adaptor Classes for graphs66 @ingroup graphs67 \brief This group contains several adaptor classes for digraphs and graphs68 69 The main parts of LEMON are the different graph structures, generic70 graph algorithms, graph concepts which couple these, and graph71 adaptors. While the previous notions are more or less clear, the72 latter one needs further explanation. Graph adaptors are graph classes73 which serve for considering graph structures in different ways.74 75 A short example makes this much clearer. Suppose that we have an76 instance \c g of a directed graph type say ListDigraph and an algorithm77 \code78 template <typename Digraph>79 int algorithm(const Digraph&);80 \endcode81 is needed to run on the reverse oriented graph. It may be expensive82 (in time or in memory usage) to copy \c g with the reversed83 arcs. In this case, an adaptor class is used, which (according84 to LEMON digraph concepts) works as a digraph. The adaptor uses the85 original digraph structure and digraph operations when methods of the86 reversed oriented graph are called. This means that the adaptor have87 minor memory usage, and do not perform sophisticated algorithmic88 actions. The purpose of it is to give a tool for the cases when a89 graph have to be used in a specific alteration. If this alteration is90 obtained by a usual construction like filtering the arcset or91 considering a new orientation, then an adaptor is worthwhile to use.92 To come back to the reverse oriented graph, in this situation93 \code94 template<typename Digraph> class ReverseDigraph;95 \endcode96 template class can be used. The code looks as follows97 \code98 ListDigraph g;99 ReverseDigraph<ListGraph> rg(g);100 int result = algorithm(rg);101 \endcode102 After running the algorithm, the original graph \c g is untouched.103 This techniques gives rise to an elegant code, and based on stable104 graph adaptors, complex algorithms can be implemented easily.105 106 In flow, circulation and bipartite matching problems, the residual107 graph is of particular importance. Combining an adaptor implementing108 this, shortest path algorithms and minimum mean cycle algorithms,109 a range of weighted and cardinality optimization algorithms can be110 obtained. For other examples, the interested user is referred to the111 detailed documentation of particular adaptors.112 113 The behavior of graph adaptors can be very different. Some of them keep114 capabilities of the original graph while in other cases this would be115 meaningless. This means that the concepts that they are models of depend116 on the graph adaptor, and the wrapped graph(s).117 If an arc of \c rg is deleted, this is carried out by deleting the118 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 constructor123 \code124 ReverseDigraph(Digraph& digraph);125 \endcode126 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 with128 <tt>Digraph=const ListDigraph</tt>.129 \code130 int algorithm1(const ListDigraph& g) {131 RevGraphAdaptor<const ListDigraph> rg(g);132 return algorithm2(rg);133 }134 \endcode135 62 */ 136 63 
lemon/Makefile.am
r418 r409 17 17 18 18 lemon_HEADERS += \ 19 lemon/adaptors.h \20 19 lemon/arg_parser.h \ 21 20 lemon/assert.h \ … … 62 61 lemon/bits/default_map.h \ 63 62 lemon/bits/enable_if.h \ 64 lemon/bits/graph_adaptor_extender.h \65 63 lemon/bits/graph_extender.h \ 66 64 lemon/bits/map_extender.h \ 67 65 lemon/bits/path_dump.h \ 68 66 lemon/bits/traits.h \ 69 lemon/bits/variant.h \70 67 lemon/bits/vector_map.h 71 68 
test/Makefile.am
r418 r410 17 17 test/dim_test \ 18 18 test/error_test \ 19 test/graph_adaptor_test \20 19 test/graph_copy_test \ 21 20 test/graph_test \ … … 46 45 test_dim_test_SOURCES = test/dim_test.cc 47 46 test_error_test_SOURCES = test/error_test.cc 48 test_graph_adaptor_test_SOURCES = test/graph_adaptor_test.cc49 47 test_graph_copy_test_SOURCES = test/graph_copy_test.cc 50 48 test_graph_test_SOURCES = test/graph_test.cc
Note: See TracChangeset
for help on using the changeset viewer.