COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/graph-adaptors.dox @ 2166:c67e8b928a95

Last change on this file since 2166:c67e8b928a95 was 2084:59769591eb60, checked in by Balazs Dezso, 15 years ago

Documentation improvements


IO modules

New documentation:




File size: 3.3 KB
[1401]2   @defgroup graph_adaptors Adaptor Classes for Graphs
[1949]3   @ingroup graphs
[1401]4   \brief This group contains several adaptor classes for graphs
[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.
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.
[1401]23   The adaptor uses
[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;
[2084]39   RevGraphAdaptor<ListGraph> rga(g);
40   int result=algorithm(rga);
[1172]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.
[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
[1401]55   particular adaptors.
[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).
[2084]61   If an edge of \c rga 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.
[1401]67   RevGraphAdaptor has constructor
[1252]68   \code
[1401]69   RevGraphAdaptor(Graph& _g);
[1252]70   \endcode
[1172]71   This means that in a situation,
72   when a <tt> const ListGraph& </tt> reference to a graph is given,
73   then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
74   \code
75   int algorithm1(const ListGraph& g) {
[2084]76   RevGraphAdaptor<const ListGraph> rga(g);
77   return algorithm2(rga);
[1172]78   }
79   \endcode
Note: See TracBrowser for help on using the repository browser.