COIN-OR::LEMON - Graph Library

Changeset 1172:37338ae42a2b in lemon-0.x for src

02/23/05 23:00:05 (17 years ago)

graphwrapper dox. everybody is asked to read doxygen.log

3 edited


  • src/lemon/graph_wrapper.h

    r1164 r1172  
    3535  // Graph wrappers
    37   /*! \addtogroup gwrappers
    38     The main parts of LEMON are the different graph structures,
    39     generic graph algorithms, graph concepts which couple these, and
    40     graph wrappers. While the previous ones are more or less clear, the
    41     latter notion needs further explanation.
    42     Graph wrappers are graph classes which serve for considering graph
    43     structures in different ways. A short example makes the notion much
    44     clearer.
    45     Suppose that we have an instance \c g of a directed graph
    46     type say \c ListGraph and an algorithm
    47     \code template<typename Graph> int algorithm(const Graph&); \endcode
    48     is needed to run on the reversely oriented graph.
    49     It may be expensive (in time or in memory usage) to copy
    50     \c g with the reverse orientation.
    51     Thus, a wrapper class
    52     \code template<typename Graph> class RevGraphWrapper; \endcode is used.
    53     The code looks as follows
    54     \code
    55     ListGraph g;
    56     RevGraphWrapper<ListGraph> rgw(g);
    57     int result=algorithm(rgw);
    58     \endcode
    59     After running the algorithm, the original graph \c g
    60     remains untouched. Thus the graph wrapper used above is to consider the
    61     original graph with reverse orientation.
    62     This techniques gives rise to an elegant code, and
    63     based on stable graph wrappers, complex algorithms can be
    64     implemented easily.
    65     In flow, circulation and bipartite matching problems, the residual
    66     graph is of particular importance. Combining a wrapper implementing
    67     this, shortest path algorithms and minimum mean cycle algorithms,
    68     a range of weighted and cardinality optimization algorithms can be
    69     obtained. For lack of space, for other examples,
    70     the interested user is referred to the detailed documentation of graph
    71     wrappers.
    72     The behavior of graph wrappers can be very different. Some of them keep
    73     capabilities of the original graph while in other cases this would be
    74     meaningless. This means that the concepts that they are a model of depend
    75     on the graph wrapper, and the wrapped graph(s).
    76     If an edge of \c rgw is deleted, this is carried out by
    77     deleting the corresponding edge of \c g. But for a residual
    78     graph, this operation has no sense.
    79     Let we stand one more example here to simplify your work.
    80     wrapper class
    81     \code template<typename Graph> class RevGraphWrapper; \endcode
    82     has constructor
    83     <tt> RevGraphWrapper(Graph& _g)</tt>.
    84     This means that in a situation,
    85     when a <tt> const ListGraph& </tt> reference to a graph is given,
    86     then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
    87     \code
    88     int algorithm1(const ListGraph& g) {
    89     RevGraphWrapper<const ListGraph> rgw(g);
    90     return algorithm2(rgw);
    91     }
    92     \endcode
     37  /*!
    9438    \addtogroup gwrappers
    9539    @{
     40   */
     42  /*!
    9743    Base type for the Graph Wrappers
  • src/lemon/maps.h

    r1164 r1172  
    591591  ///
    592592  ///For the sake of convenience it also works as a ususal map, i.e
    593   ///<tt>operator[]</tt> and the \c Key and \c Valu typedefs also exist.
     593  ///<tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
    595595  template<class M>
  • src/lemon/max_matching.h

    r1166 r1172  
    162162    ///have the property that if \c g.oppositeNode(u,map[u])==v then
    163163    ///\c \c g.oppositeNode(v,map[v])==u holds, and now some edge
    164     ///joining \c u to \v will be an edge of the matching.
     164    ///joining \c u to \c v will be an edge of the matching.
    165165    template<typename NMapE>
    166166    void readNMapEdge(NMapE& map) {
Note: See TracChangeset for help on using the changeset viewer.