COIN-OR::LEMON - Graph Library

Changeset 1252:4fee8e9d9014 in lemon-0.x


Ignore:
Timestamp:
03/23/05 17:59:13 (15 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1679
Message:

documentation

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • doc/gwrappers.dox

    r1172 r1252  
    66   The main parts of LEMON are the different graph structures,
    77   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.
     8   graph wrappers. While the previous notions are more or less clear, the
     9   latter one needs further explanation.
    1010   Graph wrappers are graph classes which serve for considering graph
    11    structures in different ways. A short example makes the notion much
     11   structures in different ways.
     12
     13   A short example makes this much
    1214   clearer.
    1315   Suppose that we have an instance \c g of a directed graph
    14    type say \c ListGraph and an algorithm
     16   type say ListGraph and an algorithm
    1517   \code template<typename Graph> int algorithm(const Graph&); \endcode
    16    is needed to run on the reversely oriented graph.
     18   is needed to run on the reversed oriented graph.
    1719   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
     20   \c g with the reversed orientation.
     21   In this case, a wrapper class is used, which
     22   (according to LEMON graph concepts) works as a graph.
     23   The wrapper uses
     24   the original graph structure and graph operations when methods of the
     25   reversed oriented graph are called.
     26   This means that the wrapper 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   a wrapper is worthwhile to use.
     33   To come back to the reversed oriented graph, in this situation
     34   \code template<typename Graph> class RevGraphWrapper; \endcode
     35   template class can be used.
     36   The code looks as follows
    2237   \code
    2338   ListGraph g;
     
    2641   \endcode
    2742   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.
     43   is untouched.
    3044   This techniques gives rise to an elegant code, and
    3145   based on stable graph wrappers, complex algorithms can be
    3246   implemented easily.
     47
    3348   In flow, circulation and bipartite matching problems, the residual
    3449   graph is of particular importance. Combining a wrapper implementing
    3550   this, shortest path algorithms and minimum mean cycle algorithms,
    3651   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.
     52   obtained.
     53   For other examples,
     54   the interested user is referred to the detailed documentation of
     55   particular wrappers.
     56
    4057   The behavior of graph wrappers can be very different. Some of them keep
    4158   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
     59   meaningless. This means that the concepts that they are models of depend
    4360   on the graph wrapper, and the wrapped graph(s).
    4461   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
     62   deleting the corresponding edge of \c g, thus the wrapper modifies the
     63   original graph.
     64   But for a residual
    4665   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>.
     66   Let us stand one more example here to simplify your work.
     67   RevGraphWrapper has constructor
     68   \code
     69   RevGraphWrapper(Graph& _g);
     70   \endcode
    5271   This means that in a situation,
    5372   when a <tt> const ListGraph& </tt> reference to a graph is given,
  • src/lemon/graph_wrapper.h

    r1242 r1252  
    435435  non-negative edge-lengths. Note that
    436436  the comprehension of the presented solution
    437   need's some knowledge from elementary combinatorial optimization.
     437  need's some elementary knowledge from combinatorial optimization.
    438438
    439439  If a single shortest path is to be
    440   searched between two nodes \c s and \c t, then this can be done easily by
    441   applying the Dijkstra algorithm class. What happens, if a maximum number of
     440  searched between \c s and \c t, then this can be done easily by
     441  applying the Dijkstra algorithm. What happens, if a maximum number of
    442442  edge-disjoint shortest paths is to be computed. It can be proved that an
    443443  edge can be in a shortest path if and only if it is tight with respect to
     
    924924  /// SubBidirGraphWrapper by considering everywhere true
    925925  /// valued maps both for forward_filter and backward_filter.
    926   /// Finally, one of the most important applications of SubBidirGraphWrapper
     926  ///
     927  /// The most important application of SubBidirGraphWrapper
    927928  /// is ResGraphWrapper, which stands for the residual graph in directed
    928929  /// flow and circulation problems.
Note: See TracChangeset for help on using the changeset viewer.