1.1 --- a/doc/groups.dox Sun Nov 30 19:00:30 2008 +0100
1.2 +++ b/doc/groups.dox Sun Nov 30 19:18:32 2008 +0100
1.3 @@ -60,6 +60,79 @@
1.4 */
1.5
1.6 /**
1.7 +@defgroup graph_adaptors Adaptor Classes for graphs
1.8 +@ingroup graphs
1.9 +\brief This group contains several adaptor classes for digraphs and graphs
1.10 +
1.11 +The main parts of LEMON are the different graph structures, generic
1.12 +graph algorithms, graph concepts which couple these, and graph
1.13 +adaptors. While the previous notions are more or less clear, the
1.14 +latter one needs further explanation. Graph adaptors are graph classes
1.15 +which serve for considering graph structures in different ways.
1.16 +
1.17 +A short example makes this much clearer. Suppose that we have an
1.18 +instance \c g of a directed graph type say ListDigraph and an algorithm
1.19 +\code
1.20 +template <typename Digraph>
1.21 +int algorithm(const Digraph&);
1.22 +\endcode
1.23 +is needed to run on the reverse oriented graph. It may be expensive
1.24 +(in time or in memory usage) to copy \c g with the reversed
1.25 +arcs. In this case, an adaptor class is used, which (according
1.26 +to LEMON digraph concepts) works as a digraph. The adaptor uses the
1.27 +original digraph structure and digraph operations when methods of the
1.28 +reversed oriented graph are called. This means that the adaptor have
1.29 +minor memory usage, and do not perform sophisticated algorithmic
1.30 +actions. The purpose of it is to give a tool for the cases when a
1.31 +graph have to be used in a specific alteration. If this alteration is
1.32 +obtained by a usual construction like filtering the arc-set or
1.33 +considering a new orientation, then an adaptor is worthwhile to use.
1.34 +To come back to the reverse oriented graph, in this situation
1.35 +\code
1.36 +template<typename Digraph> class ReverseDigraph;
1.37 +\endcode
1.38 +template class can be used. The code looks as follows
1.39 +\code
1.40 +ListDigraph g;
1.41 +ReverseDigraph<ListGraph> rg(g);
1.42 +int result = algorithm(rg);
1.43 +\endcode
1.44 +After running the algorithm, the original graph \c g is untouched.
1.45 +This techniques gives rise to an elegant code, and based on stable
1.46 +graph adaptors, complex algorithms can be implemented easily.
1.47 +
1.48 +In flow, circulation and bipartite matching problems, the residual
1.49 +graph is of particular importance. Combining an adaptor implementing
1.50 +this, shortest path algorithms and minimum mean cycle algorithms,
1.51 +a range of weighted and cardinality optimization algorithms can be
1.52 +obtained. For other examples, the interested user is referred to the
1.53 +detailed documentation of particular adaptors.
1.54 +
1.55 +The behavior of graph adaptors can be very different. Some of them keep
1.56 +capabilities of the original graph while in other cases this would be
1.57 +meaningless. This means that the concepts that they are models of depend
1.58 +on the graph adaptor, and the wrapped graph(s).
1.59 +If an arc of \c rg is deleted, this is carried out by deleting the
1.60 +corresponding arc of \c g, thus the adaptor modifies the original graph.
1.61 +
1.62 +But for a residual graph, this operation has no sense.
1.63 +Let us stand one more example here to simplify your work.
1.64 +RevGraphAdaptor has constructor
1.65 +\code
1.66 +ReverseDigraph(Digraph& digraph);
1.67 +\endcode
1.68 +This means that in a situation, when a <tt>const ListDigraph&</tt>
1.69 +reference to a graph is given, then it have to be instantiated with
1.70 +<tt>Digraph=const ListDigraph</tt>.
1.71 +\code
1.72 +int algorithm1(const ListDigraph& g) {
1.73 + RevGraphAdaptor<const ListDigraph> rg(g);
1.74 + return algorithm2(rg);
1.75 +}
1.76 +\endcode
1.77 +*/
1.78 +
1.79 +/**
1.80 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs
1.81 @ingroup graphs
1.82 \brief Graph types between real graphs and graph adaptors.