# HG changeset patch # User marci # Date 1109196005 0 # Node ID 37338ae42a2b18b93699a986d77a50ea4580fdbd # Parent f426c84a4e00e8c22ef5cb6d58c6ed15711b3a81 graphwrapper dox. everybody is asked to read doxygen.log diff -r f426c84a4e00 -r 37338ae42a2b doc/Doxyfile --- a/doc/Doxyfile Wed Feb 23 10:53:17 2005 +0000 +++ b/doc/Doxyfile Wed Feb 23 22:00:05 2005 +0000 @@ -458,6 +458,7 @@ developers_interface.dox \ graph_io.dox \ dirs.dox \ + gwrappers.dox \ ../src/lemon \ ../src/lemon/concept \ ../src/test/test_tools.h diff -r f426c84a4e00 -r 37338ae42a2b doc/groups.dox --- a/doc/groups.dox Wed Feb 23 10:53:17 2005 +0000 +++ b/doc/groups.dox Wed Feb 23 22:00:05 2005 +0000 @@ -9,20 +9,34 @@ @ingroup datas \brief Graph structures implemented in LEMON. -LEMON provides several data structures to meet the diverging requirements -of the possible users. -In order to save on running time or on memory usage, some structures may -fail to provide -some graph features like edge or node deletion. +The implementation of combinatorial algorithms heavily relies on +efficient graph implementations. LEMON offers data structures which are +planned to be easily used in an experimental phase of implementation studies, +and thereafter the program code can be made efficient by small modifications. -LEMON also offers special graphs that cannot be used alone but only -in conjunction with other graph representation. The examples for this are -\ref lemon::EdgeSet "EdgeSet", \ref lemon::NodeSet "NodeSet" -and the large variety of \ref gwrappers "graph wrappers". +The most efficient implementation of diverse applications require the usage of different physical graph implementations. These differences appear in the size of +graph we require to handle, memory or time usage limitations or in +the set of operations through which the graph can be accessed. +LEMON provides several physical graph structures to meet the +diverging requirements of the possible users. +In order to save on running time or on memory usage, some structures may +fail to provide some graph features like edge or node deletion. + +Alteration of standard containers need a very limited number of +operations, these together satisfy the everyday requirements. +In the case of graph strutures, different operations are needed which do +not alter the physical graph, but gives an other view. If some nodes or +edges have to be hidden or the reverse oriented graph have to be used, then +this is the case. It also may happen that in a flow implemenation +the residual graph can be accessed by an other algorithm, or a node-set +is to be shrunk for an other algorithm. +LEMON also provides a variety of graphs for these requirements called +\ref gwrappers "graph wrappers". Wrappers cannot be used alone but only +in conjunction with other graph representation. You are free to use the graph structure that fit your requirements the best, most graph algorithms and auxiliary data structures can be used -with any graph structures. +with any graph structures. */ /** @@ -53,12 +67,6 @@ */ /** -@defgroup gwrappers Wrapper Classes for Graphs -\brief This group contains several wrapper classes for graphs -@ingroup graphs -*/ - -/** @defgroup galgs Graph Algorithms \brief This group describes the several graph algorithms implemented in LEMON. diff -r f426c84a4e00 -r 37338ae42a2b doc/gwrappers.dox --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/doc/gwrappers.dox Wed Feb 23 22:00:05 2005 +0000 @@ -0,0 +1,61 @@ +/** + @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 ones are more or less clear, the + latter notion needs further explanation. + Graph wrappers are graph classes which serve for considering graph + structures in different ways. A short example makes the notion much + clearer. + Suppose that we have an instance \c g of a directed graph + type say \c ListGraph and an algorithm + \code template int algorithm(const Graph&); \endcode + is needed to run on the reversely oriented graph. + It may be expensive (in time or in memory usage) to copy + \c g with the reverse orientation. + Thus, a wrapper class + \code template class RevGraphWrapper; \endcode is used. + The code looks as follows + \code + ListGraph g; + RevGraphWrapper rgw(g); + int result=algorithm(rgw); + \endcode + After running the algorithm, the original graph \c g + remains untouched. Thus the graph wrapper used above is to consider the + original graph with reverse orientation. + 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 lack of space, for other examples, + the interested user is referred to the detailed documentation of graph + 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 a model 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. But for a residual + graph, this operation has no sense. + Let we stand one more example here to simplify your work. + wrapper class + \code template class RevGraphWrapper; \endcode + has constructor + RevGraphWrapper(Graph& _g). + This means that in a situation, + when a const ListGraph& reference to a graph is given, + then it have to be instantiated with Graph=const ListGraph. + \code + int algorithm1(const ListGraph& g) { + RevGraphWrapper rgw(g); + return algorithm2(rgw); + } + \endcode +*/ diff -r f426c84a4e00 -r 37338ae42a2b src/lemon/graph_wrapper.h --- a/src/lemon/graph_wrapper.h Wed Feb 23 10:53:17 2005 +0000 +++ b/src/lemon/graph_wrapper.h Wed Feb 23 22:00:05 2005 +0000 @@ -34,66 +34,12 @@ // Graph wrappers - /*! \addtogroup gwrappers - The main parts of LEMON are the different graph structures, - generic graph algorithms, graph concepts which couple these, and - graph wrappers. While the previous ones are more or less clear, the - latter notion needs further explanation. - Graph wrappers are graph classes which serve for considering graph - structures in different ways. A short example makes the notion much - clearer. - Suppose that we have an instance \c g of a directed graph - type say \c ListGraph and an algorithm - \code template int algorithm(const Graph&); \endcode - is needed to run on the reversely oriented graph. - It may be expensive (in time or in memory usage) to copy - \c g with the reverse orientation. - Thus, a wrapper class - \code template class RevGraphWrapper; \endcode is used. - The code looks as follows - \code - ListGraph g; - RevGraphWrapper rgw(g); - int result=algorithm(rgw); - \endcode - After running the algorithm, the original graph \c g - remains untouched. Thus the graph wrapper used above is to consider the - original graph with reverse orientation. - 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 lack of space, for other examples, - the interested user is referred to the detailed documentation of graph - 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 a model 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. But for a residual - graph, this operation has no sense. - Let we stand one more example here to simplify your work. - wrapper class - \code template class RevGraphWrapper; \endcode - has constructor - RevGraphWrapper(Graph& _g). - This means that in a situation, - when a const ListGraph& reference to a graph is given, - then it have to be instantiated with Graph=const ListGraph. - \code - int algorithm1(const ListGraph& g) { - RevGraphWrapper rgw(g); - return algorithm2(rgw); - } - \endcode - + /*! \addtogroup gwrappers @{ + */ + /*! Base type for the Graph Wrappers \warning Graph wrappers are in even more experimental state than the other diff -r f426c84a4e00 -r 37338ae42a2b src/lemon/maps.h --- a/src/lemon/maps.h Wed Feb 23 10:53:17 2005 +0000 +++ b/src/lemon/maps.h Wed Feb 23 22:00:05 2005 +0000 @@ -590,7 +590,7 @@ ///that is it provides an operator() to read its values. /// ///For the sake of convenience it also works as a ususal map, i.e - ///operator[] and the \c Key and \c Valu typedefs also exist. + ///operator[] and the \c Key and \c Value typedefs also exist. template class MapFunctor diff -r f426c84a4e00 -r 37338ae42a2b src/lemon/max_matching.h --- a/src/lemon/max_matching.h Wed Feb 23 10:53:17 2005 +0000 +++ b/src/lemon/max_matching.h Wed Feb 23 22:00:05 2005 +0000 @@ -161,7 +161,7 @@ ///map[v] must be an \c UndirEdge incident to \c v. This map must ///have the property that if \c g.oppositeNode(u,map[u])==v then ///\c \c g.oppositeNode(v,map[v])==u holds, and now some edge - ///joining \c u to \v will be an edge of the matching. + ///joining \c u to \c v will be an edge of the matching. template void readNMapEdge(NMapE& map) { for(NodeIt v(g); v!=INVALID; ++v) {