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.