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