Last change on this file since 2083:f50c8c191cbd was 1949:5db4ff8d69de, checked in by Alpar Juttner, 15 years ago

Fight with Doxygen.
Victory hasn't been reached yet, but it's on the horizon.

File size: 3.3 KB
RevLine
[1172]1/**
[1949]3   @ingroup graphs
[1401]4   \brief This group contains several adaptor classes for graphs
[556]5
[1172]6   The main parts of LEMON are the different graph structures,
7   generic graph algorithms, graph concepts which couple these, and
[1401]8   graph adaptors. While the previous notions are more or less clear, the
[1252]9   latter one needs further explanation.
[1401]10   Graph adaptors are graph classes which serve for considering graph
[1252]11   structures in different ways.
12
13   A short example makes this much
[1172]14   clearer.
15   Suppose that we have an instance \c g of a directed graph
[1252]16   type say ListGraph and an algorithm
[1172]17   \code template<typename Graph> int algorithm(const Graph&); \endcode
[1252]18   is needed to run on the reversed oriented graph.
[1172]19   It may be expensive (in time or in memory usage) to copy
[1252]20   \c g with the reversed orientation.
[1401]21   In this case, an adaptor class is used, which
[1252]22   (according to LEMON graph concepts) works as a graph.
[1252]24   the original graph structure and graph operations when methods of the
25   reversed oriented graph are called.
[1401]26   This means that the adaptor have minor memory usage,
[1252]27   and do not perform sophisticated algorithmic actions.
28   The purpose of it is to give a tool for the cases when
29   a graph have to be used in a specific alteration.
30   If this alteration is obtained by a usual construction
31   like filtering the edge-set or considering a new orientation, then
[1401]32   an adaptor is worthwhile to use.
[1252]33   To come back to the reversed oriented graph, in this situation
[1401]34   \code template<typename Graph> class RevGraphAdaptor; \endcode
[1252]35   template class can be used.
36   The code looks as follows
[1172]37   \code
38   ListGraph g;
[1172]40   int result=algorithm(rgw);
41   \endcode
42   After running the algorithm, the original graph \c g
[1252]43   is untouched.
[1172]44   This techniques gives rise to an elegant code, and
[1401]45   based on stable graph adaptors, complex algorithms can be
[1172]46   implemented easily.
[1252]47
[1172]48   In flow, circulation and bipartite matching problems, the residual
[1401]49   graph is of particular importance. Combining an adaptor implementing
[1172]50   this, shortest path algorithms and minimum mean cycle algorithms,
51   a range of weighted and cardinality optimization algorithms can be
[1252]52   obtained.
53   For other examples,
54   the interested user is referred to the detailed documentation of
[1252]56
[1401]57   The behavior of graph adaptors can be very different. Some of them keep
[1172]58   capabilities of the original graph while in other cases this would be
[1252]59   meaningless. This means that the concepts that they are models of depend
[1401]60   on the graph adaptor, and the wrapped graph(s).
[1172]61   If an edge of \c rgw is deleted, this is carried out by
[1401]62   deleting the corresponding edge of \c g, thus the adaptor modifies the
[1252]63   original graph.
64   But for a residual
[1172]65   graph, this operation has no sense.
[1252]66   Let us stand one more example here to simplify your work.
[1252]68   \code