COIN-OR::LEMON - Graph Library

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

Last change on this file was 2553:bfced05fa852, checked in by Alpar Juttner, 16 years ago

Happy New Year to LEMON (+ better update-copyright-header script)

File size: 3.9 KB
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
20   @defgroup graph_adaptors Adaptor Classes for Graphs
21   @ingroup graphs
22   \brief This group contains several adaptor classes for graphs
24   The main parts of LEMON are the different graph structures,
25   generic graph algorithms, graph concepts which couple these, and
26   graph adaptors. While the previous notions are more or less clear, the
27   latter one needs further explanation.
28   Graph adaptors are graph classes which serve for considering graph
29   structures in different ways.
31   A short example makes this much
32   clearer.
33   Suppose that we have an instance \c g of a directed graph
34   type say ListGraph and an algorithm
35   \code template<typename Graph> int algorithm(const Graph&); \endcode
36   is needed to run on the reversed oriented graph.
37   It may be expensive (in time or in memory usage) to copy
38   \c g with the reversed orientation.
39   In this case, an adaptor class is used, which
40   (according to LEMON graph concepts) works as a graph.
41   The adaptor uses
42   the original graph structure and graph operations when methods of the
43   reversed oriented graph are called.
44   This means that the adaptor have minor memory usage,
45   and do not perform sophisticated algorithmic actions.
46   The purpose of it is to give a tool for the cases when
47   a graph have to be used in a specific alteration.
48   If this alteration is obtained by a usual construction
49   like filtering the edge-set or considering a new orientation, then
50   an adaptor is worthwhile to use.
51   To come back to the reversed oriented graph, in this situation
52   \code template<typename Graph> class RevGraphAdaptor; \endcode
53   template class can be used.
54   The code looks as follows
55   \code
56   ListGraph g;
57   RevGraphAdaptor<ListGraph> rga(g);
58   int result=algorithm(rga);
59   \endcode
60   After running the algorithm, the original graph \c g
61   is untouched.
62   This techniques gives rise to an elegant code, and
63   based on stable graph adaptors, complex algorithms can be
64   implemented easily.
66   In flow, circulation and bipartite matching problems, the residual
67   graph is of particular importance. Combining an adaptor implementing
68   this, shortest path algorithms and minimum mean cycle algorithms,
69   a range of weighted and cardinality optimization algorithms can be
70   obtained.
71   For other examples,
72   the interested user is referred to the detailed documentation of
73   particular adaptors.
75   The behavior of graph adaptors can be very different. Some of them keep
76   capabilities of the original graph while in other cases this would be
77   meaningless. This means that the concepts that they are models of depend
78   on the graph adaptor, and the wrapped graph(s).
79   If an edge of \c rga is deleted, this is carried out by
80   deleting the corresponding edge of \c g, thus the adaptor modifies the
81   original graph.
82   But for a residual
83   graph, this operation has no sense.
84   Let us stand one more example here to simplify your work.
85   RevGraphAdaptor has constructor
86   \code
87   RevGraphAdaptor(Graph& _g);
88   \endcode
89   This means that in a situation,
90   when a <tt> const ListGraph& </tt> reference to a graph is given,
91   then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
92   \code
93   int algorithm1(const ListGraph& g) {
94   RevGraphAdaptor<const ListGraph> rga(g);
95   return algorithm2(rga);
96   }
97   \endcode
Note: See TracBrowser for help on using the repository browser.