doc/groups.dox
changeset 419 9afe81e4c543
parent 406 a578265aa8a6
parent 416 76287c8caa26
child 440 88ed40ad0d4f
child 451 fbd6e04acf44
equal deleted inserted replaced
14:63a6d05271ae 16:15f6159aa2bb
    57 You are free to use the graph structure that fit your requirements
    57 You are free to use the graph structure that fit your requirements
    58 the best, most graph algorithms and auxiliary data structures can be used
    58 the best, most graph algorithms and auxiliary data structures can be used
    59 with any graph structure.
    59 with any graph structure.
    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 */
       
    63 
       
    64 /**
       
    65 @defgroup graph_adaptors Adaptor Classes for graphs
       
    66 @ingroup graphs
       
    67 \brief This group contains several adaptor classes for digraphs and graphs
       
    68 
       
    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.
       
    74 
       
    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.
       
   105 
       
   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.
       
   112 
       
   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.
       
   119 
       
   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
    62 */
   135 */
    63 
   136 
    64 /**
   137 /**
    65 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs
   138 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs
    66 @ingroup graphs
   139 @ingroup graphs