COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/graph-adaptors.dox @ 2196:09af6d2b683b

Last change on this file since 2196:09af6d2b683b was 2084:59769591eb60, checked in by Balazs Dezso, 18 years ago

Documentation improvements

Rearrangements:

IO modules
Algorithms

New documentation:

SwapBpUGraphAdaptor

Demos:

strongly_connected_orientation.cc

Benchmarks:

swap_bipartite_bench.cc

File size: 3.3 KB
Line 
1/**
2   @defgroup graph_adaptors Adaptor Classes for Graphs
3   @ingroup graphs
4   \brief This group contains several adaptor classes for graphs
5   
6   The main parts of LEMON are the different graph structures,
7   generic graph algorithms, graph concepts which couple these, and
8   graph adaptors. While the previous notions are more or less clear, the
9   latter one needs further explanation.
10   Graph adaptors are graph classes which serve for considering graph
11   structures in different ways.
12
13   A short example makes this much
14   clearer.
15   Suppose that we have an instance \c g of a directed graph
16   type say ListGraph and an algorithm
17   \code template<typename Graph> int algorithm(const Graph&); \endcode
18   is needed to run on the reversed oriented graph.
19   It may be expensive (in time or in memory usage) to copy
20   \c g with the reversed orientation.
21   In this case, an adaptor class is used, which
22   (according to LEMON graph concepts) works as a graph.
23   The adaptor uses
24   the original graph structure and graph operations when methods of the
25   reversed oriented graph are called.
26   This means that the adaptor have minor memory usage,
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
32   an adaptor is worthwhile to use.
33   To come back to the reversed oriented graph, in this situation
34   \code template<typename Graph> class RevGraphAdaptor; \endcode
35   template class can be used.
36   The code looks as follows
37   \code
38   ListGraph g;
39   RevGraphAdaptor<ListGraph> rga(g);
40   int result=algorithm(rga);
41   \endcode
42   After running the algorithm, the original graph \c g
43   is untouched.
44   This techniques gives rise to an elegant code, and
45   based on stable graph adaptors, complex algorithms can be
46   implemented easily.
47
48   In flow, circulation and bipartite matching problems, the residual
49   graph is of particular importance. Combining an adaptor implementing
50   this, shortest path algorithms and minimum mean cycle algorithms,
51   a range of weighted and cardinality optimization algorithms can be
52   obtained.
53   For other examples,
54   the interested user is referred to the detailed documentation of
55   particular adaptors.
56
57   The behavior of graph adaptors can be very different. Some of them keep
58   capabilities of the original graph while in other cases this would be
59   meaningless. This means that the concepts that they are models of depend
60   on the graph adaptor, and the wrapped graph(s).
61   If an edge of \c rga is deleted, this is carried out by
62   deleting the corresponding edge of \c g, thus the adaptor modifies the
63   original graph.
64   But for a residual
65   graph, this operation has no sense.
66   Let us stand one more example here to simplify your work.
67   RevGraphAdaptor has constructor
68   \code
69   RevGraphAdaptor(Graph& _g);
70   \endcode
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) {
76   RevGraphAdaptor<const ListGraph> rga(g);
77   return algorithm2(rga);
78   }
79   \endcode
80*/
Note: See TracBrowser for help on using the repository browser.