source: lemon-0.x/doc/gwrappers.dox @ 1252:4fee8e9d9014

/**
   @defgroup gwrappers Wrapper Classes for Graphs
   \brief This group contains several wrapper classes for graphs
   @ingroup graphs
   
   The main parts of LEMON are the different graph structures, 
   generic graph algorithms, graph concepts which couple these, and 
   graph wrappers. While the previous notions are more or less clear, the 
   latter one needs further explanation. 
   Graph wrappers are graph classes which serve for considering graph 
   structures in different ways. 

   A short example makes this much 
   clearer. 
   Suppose that we have an instance \c g of a directed graph
   type say ListGraph and an algorithm 
   \code template<typename Graph> int algorithm(const Graph&); \endcode 
   is needed to run on the reversed oriented graph. 
   It may be expensive (in time or in memory usage) to copy 
   \c g with the reversed orientation. 
   In this case, a wrapper class is used, which 
   (according to LEMON graph concepts) works as a graph. 
   The wrapper uses 
   the original graph structure and graph operations when methods of the 
   reversed oriented graph are called. 
   This means that the wrapper have minor memory usage, 
   and do not perform sophisticated algorithmic actions. 
   The purpose of it is to give a tool for the cases when 
   a graph have to be used in a specific alteration. 
   If this alteration is obtained by a usual construction 
   like filtering the edge-set or considering a new orientation, then 
   a wrapper is worthwhile to use. 
   To come back to the reversed oriented graph, in this situation 
   \code template<typename Graph> class RevGraphWrapper; \endcode 
   template class can be used. 
   The code looks as follows 
   \code
   ListGraph g;
   RevGraphWrapper<ListGraph> rgw(g);
   int result=algorithm(rgw);
   \endcode
   After running the algorithm, the original graph \c g 
   is untouched. 
   This techniques gives rise to an elegant code, and 
   based on stable graph wrappers, complex algorithms can be 
   implemented easily. 

   In flow, circulation and bipartite matching problems, the residual 
   graph is of particular importance. Combining a wrapper implementing 
   this, shortest path algorithms and minimum mean cycle algorithms, 
   a range of weighted and cardinality optimization algorithms can be 
   obtained. 
   For other examples, 
   the interested user is referred to the detailed documentation of 
   particular wrappers. 

   The behavior of graph wrappers can be very different. Some of them keep 
   capabilities of the original graph while in other cases this would be 
   meaningless. This means that the concepts that they are models of depend 
   on the graph wrapper, and the wrapped graph(s). 
   If an edge of \c rgw is deleted, this is carried out by 
   deleting the corresponding edge of \c g, thus the wrapper modifies the 
   original graph. 
   But for a residual 
   graph, this operation has no sense. 
   Let us stand one more example here to simplify your work. 
   RevGraphWrapper has constructor 
   \code 
   RevGraphWrapper(Graph& _g);
   \endcode
   This means that in a situation, 
   when a <tt> const ListGraph& </tt> reference to a graph is given, 
   then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
   \code
   int algorithm1(const ListGraph& g) {
   RevGraphWrapper<const ListGraph> rgw(g);
   return algorithm2(rgw);
   }
   \endcode
*/