COIN-OR::LEMON - Graph Library

Changes in / [418:ad483acf1654:413:d8b87e9b90c3] in lemon-1.2

5 deleted
3 edited


  • doc/groups.dox

    r418 r406  
    6161<b>See also:</b> \ref graph_concepts "Graph Structure Concepts".
    62 */
    64 /**
    65 @defgroup graph_adaptors Adaptor Classes for graphs
    66 @ingroup graphs
    67 \brief This group contains several adaptor classes for digraphs and graphs
    69 The main parts of LEMON are the different graph structures, generic
    70 graph algorithms, graph concepts which couple these, and graph
    71 adaptors. While the previous notions are more or less clear, the
    72 latter one needs further explanation. Graph adaptors are graph classes
    73 which serve for considering graph structures in different ways.
    75 A short example makes this much clearer.  Suppose that we have an
    76 instance \c g of a directed graph type say ListDigraph and an algorithm
    77 \code
    78 template <typename Digraph>
    79 int algorithm(const Digraph&);
    80 \endcode
    81 is needed to run on the reverse oriented graph.  It may be expensive
    82 (in time or in memory usage) to copy \c g with the reversed
    83 arcs.  In this case, an adaptor class is used, which (according
    84 to LEMON digraph concepts) works as a digraph.  The adaptor uses the
    85 original digraph structure and digraph operations when methods of the
    86 reversed oriented graph are called.  This means that the adaptor have
    87 minor memory usage, and do not perform sophisticated algorithmic
    88 actions.  The purpose of it is to give a tool for the cases when a
    89 graph have to be used in a specific alteration.  If this alteration is
    90 obtained by a usual construction like filtering the arc-set or
    91 considering a new orientation, then an adaptor is worthwhile to use.
    92 To come back to the reverse oriented graph, in this situation
    93 \code
    94 template<typename Digraph> class ReverseDigraph;
    95 \endcode
    96 template class can be used. The code looks as follows
    97 \code
    98 ListDigraph g;
    99 ReverseDigraph<ListGraph> rg(g);
    100 int result = algorithm(rg);
    101 \endcode
    102 After running the algorithm, the original graph \c g is untouched.
    103 This techniques gives rise to an elegant code, and based on stable
    104 graph adaptors, complex algorithms can be implemented easily.
    106 In flow, circulation and bipartite matching problems, the residual
    107 graph is of particular importance. Combining an adaptor implementing
    108 this, shortest path algorithms and minimum mean cycle algorithms,
    109 a range of weighted and cardinality optimization algorithms can be
    110 obtained. For other examples, the interested user is referred to the
    111 detailed documentation of particular adaptors.
    113 The behavior of graph adaptors can be very different. Some of them keep
    114 capabilities of the original graph while in other cases this would be
    115 meaningless. This means that the concepts that they are models of depend
    116 on the graph adaptor, and the wrapped graph(s).
    117 If an arc of \c rg is deleted, this is carried out by deleting the
    118 corresponding arc of \c g, thus the adaptor modifies the original graph.
    120 But for a residual graph, this operation has no sense.
    121 Let us stand one more example here to simplify your work.
    122 RevGraphAdaptor has constructor
    123 \code
    124 ReverseDigraph(Digraph& digraph);
    125 \endcode
    126 This means that in a situation, when a <tt>const ListDigraph&</tt>
    127 reference to a graph is given, then it have to be instantiated with
    128 <tt>Digraph=const ListDigraph</tt>.
    129 \code
    130 int algorithm1(const ListDigraph& g) {
    131   RevGraphAdaptor<const ListDigraph> rg(g);
    132   return algorithm2(rg);
    133 }
    134 \endcode
  • lemon/

    r418 r409  
    1818lemon_HEADERS += \
    19         lemon/adaptors.h \
    2019        lemon/arg_parser.h \
    2120        lemon/assert.h \
    6261        lemon/bits/default_map.h \
    6362        lemon/bits/enable_if.h \
    64         lemon/bits/graph_adaptor_extender.h \
    6563        lemon/bits/graph_extender.h \
    6664        lemon/bits/map_extender.h \
    6765        lemon/bits/path_dump.h \
    6866        lemon/bits/traits.h \
    69         lemon/bits/variant.h \
    7067        lemon/bits/vector_map.h
  • test/

    r418 r410  
    1717        test/dim_test \
    1818        test/error_test \
    19         test/graph_adaptor_test \
    2019        test/graph_copy_test \
    2120        test/graph_test \
    4645test_dim_test_SOURCES = test/
    4746test_error_test_SOURCES = test/
    48 test_graph_adaptor_test_SOURCES = test/
    4947test_graph_copy_test_SOURCES = test/
    5048test_graph_test_SOURCES = test/
Note: See TracChangeset for help on using the changeset viewer.