COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/gwrappers.dox @ 1172:37338ae42a2b

Last change on this file since 1172:37338ae42a2b was 1172:37338ae42a2b, checked in by marci, 18 years ago

graphwrapper dox. everybody is asked to read doxygen.log

File size: 2.8 KB
2   @defgroup gwrappers Wrapper Classes for Graphs
3   \brief This group contains several wrapper classes for graphs
4   @ingroup graphs
6   The main parts of LEMON are the different graph structures,
7   generic graph algorithms, graph concepts which couple these, and
8   graph wrappers. While the previous ones are more or less clear, the
9   latter notion needs further explanation.
10   Graph wrappers are graph classes which serve for considering graph
11   structures in different ways. A short example makes the notion much
12   clearer.
13   Suppose that we have an instance \c g of a directed graph
14   type say \c ListGraph and an algorithm
15   \code template<typename Graph> int algorithm(const Graph&); \endcode
16   is needed to run on the reversely oriented graph.
17   It may be expensive (in time or in memory usage) to copy
18   \c g with the reverse orientation.
19   Thus, a wrapper class
20   \code template<typename Graph> class RevGraphWrapper; \endcode is used.
21   The code looks as follows
22   \code
23   ListGraph g;
24   RevGraphWrapper<ListGraph> rgw(g);
25   int result=algorithm(rgw);
26   \endcode
27   After running the algorithm, the original graph \c g
28   remains untouched. Thus the graph wrapper used above is to consider the
29   original graph with reverse orientation.
30   This techniques gives rise to an elegant code, and
31   based on stable graph wrappers, complex algorithms can be
32   implemented easily.
33   In flow, circulation and bipartite matching problems, the residual
34   graph is of particular importance. Combining a wrapper implementing
35   this, shortest path algorithms and minimum mean cycle algorithms,
36   a range of weighted and cardinality optimization algorithms can be
37   obtained. For lack of space, for other examples,
38   the interested user is referred to the detailed documentation of graph
39   wrappers.
40   The behavior of graph wrappers can be very different. Some of them keep
41   capabilities of the original graph while in other cases this would be
42   meaningless. This means that the concepts that they are a model of depend
43   on the graph wrapper, and the wrapped graph(s).
44   If an edge of \c rgw is deleted, this is carried out by
45   deleting the corresponding edge of \c g. But for a residual
46   graph, this operation has no sense.
47   Let we stand one more example here to simplify your work.
48   wrapper class
49   \code template<typename Graph> class RevGraphWrapper; \endcode
50   has constructor
51   <tt> RevGraphWrapper(Graph& _g)</tt>.
52   This means that in a situation,
53   when a <tt> const ListGraph& </tt> reference to a graph is given,
54   then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
55   \code
56   int algorithm1(const ListGraph& g) {
57   RevGraphWrapper<const ListGraph> rgw(g);
58   return algorithm2(rgw);
59   }
60   \endcode
Note: See TracBrowser for help on using the repository browser.