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