# Changeset 1004:b94037830dc8 in lemon-0.x

Ignore:
Timestamp:
11/17/04 20:56:46 (16 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1394
Message:

misc

File:
1 edited

Unmodified
Added
Removed
• ## src/lemon/graph_wrapper.h

 r998 // 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 ///parts of the lib. Use them at you own risk. /// /// This is the base type for most of LEMON graph wrappers. /// This class implements a trivial graph wrapper i.e. it only wraps the /// functions and types of the graph. The purpose of this class is to /// make easier implementing graph wrappers. E.g. if a wrapper is /// considered which differs from the wrapped graph only in some of its /// functions or types, then it can be derived from GraphWrapper, and only the /// differences should be implemented. /// ///\author Marton Makai /*! \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 parts of the lib. Use them at you own risk. This is the base type for most of LEMON graph wrappers. This class implements a trivial graph wrapper i.e. it only wraps the functions and types of the graph. The purpose of this class is to make easier implementing graph wrappers. E.g. if a wrapper is considered which differs from the wrapped graph only in some of its functions or types, then it can be derived from GraphWrapper, and only the differences should be implemented. \author Marton Makai */ template class GraphWrapperBase {
Note: See TracChangeset for help on using the changeset viewer.