Changeset 344:9b24714c3b1c in lemon0.x for src/work/marci/graph_wrapper.h
 Timestamp:
 04/17/04 00:00:11 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@463
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/marci/graph_wrapper.h
r341 r344 9 9 /// Graph wrappers 10 10 11 /// Themain parts of HUGOlib are the different graph structures,11 /// A main parts of HUGOlib are the different graph structures, 12 12 /// generic graph algorithms, graph concepts which couple these, and 13 13 /// graph wrappers. While the previous ones are more or less clear, the 14 14 /// latter notion needs further explanation. 15 15 /// Graph wrappers are graph classes which serve for considering graph 16 /// structures in different ways. A short example makes the notion much more17 /// clear .18 /// Suppose that we have an instance \c ode g \endcodeof a directed graph19 /// type say \c ode ListGraph \endcodeand an algorithm16 /// structures in different ways. A short example makes the notion much 17 /// clearer. 18 /// Suppose that we have an instance \c g of a directed graph 19 /// type say \c ListGraph and an algorithm 20 20 /// \code template<typename Graph> int algorithm(const Graph&); \endcode 21 /// is needed to run on the reverse doriented graph.22 /// It canbe expensive (in time or in memory usage) to copy23 /// \c ode g \endcode with the reversedorientation.21 /// is needed to run on the reversely oriented graph. 22 /// It may be expensive (in time or in memory usage) to copy 23 /// \c g with the reverse orientation. 24 24 /// Thus, a wrapper class 25 25 /// \code template<typename Graph> class RevGraphWrapper; \endcode is used. … … 30 30 /// int result=algorithm(rgw); 31 31 /// \endcode 32 /// After running the algorithm, the original graph \c ode g \endcode33 /// is untouched. Thus the above used graph wrapperis to consider the34 /// original graph with reverse dorientation.32 /// After running the algorithm, the original graph \c g 33 /// remains untouched. Thus the graph wrapper used above is to consider the 34 /// original graph with reverse orientation. 35 35 /// This techniques gives rise to an elegant code, and 36 36 /// based on stable graph wrappers, complex algorithms can be 37 37 /// implemented easily. 38 38 /// In flow, circulation and bipartite matching problems, the residual 39 /// graph is of particu alar significance. Combining a wrapper impleneting40 /// this, shortest path algorithms and mi mimum mean cycle algorithms,39 /// graph is of particular importance. Combining a wrapper implementing 40 /// this, shortest path algorithms and minimum mean cycle algorithms, 41 41 /// a range of weighted and cardinality optimization algorithms can be 42 42 /// obtained. For lack of space, for other examples, 43 /// the interested user is referred to the detailed do mumentation of graph43 /// the interested user is referred to the detailed documentation of graph 44 44 /// wrappers. 45 /// The behavior of graph wrappers are very different. Some of them keep45 /// The behavior of graph wrappers can be very different. Some of them keep 46 46 /// capabilities of the original graph while in other cases this would be 47 /// meaningless. This means that the concepts that they are model of depend47 /// meaningless. This means that the concepts that they are a model of depend 48 48 /// on the graph wrapper, and the wrapped graph(s). 49 /// If an edge of \c ode rgw \endcodeis deleted, this is carried out by50 /// deleting the corresponding edge of \c ode g \endcode. But for a residual49 /// If an edge of \c rgw is deleted, this is carried out by 50 /// deleting the corresponding edge of \c g. But for a residual 51 51 /// graph, this operation has no sense. 52 52 /// Let we stand one more example here to simplify your work. … … 54 54 /// \code template<typename Graph> class RevGraphWrapper; \endcode 55 55 /// has constructor 56 /// \code RevGraphWrapper(Graph& _g); \endcode.56 /// <tt> RevGraphWrapper(Graph& _g)</tt>. 57 57 /// This means that in a situation, 58 /// when a \code const ListGraph& \endcodereference to a graph is given,59 /// then it have to be insta tiated with Graph=const ListGraph.58 /// when a <tt> const ListGraph& </tt> reference to a graph is given, 59 /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>. 60 60 /// \code 61 61 /// int algorithm1(const ListGraph& g) {
Note: See TracChangeset
for help on using the changeset viewer.