COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 2042:bdc953f2a449 in lemon-0.x for lemon/fredman_tarjan.h


Ignore:
Timestamp:
04/07/06 11:54:35 (18 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2681
Message:

New Algorithm group for matchings

LaTeX formulas
Bug fix => /\f$ will cause parsing error in doxygen

File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/fredman_tarjan.h

    r1993 r2042  
    4545  ///Default traits class of FredmanTarjan class.
    4646  ///\param GR Graph type.
    47   ///\param LM Type of cost map.
    48   template<class GR, class LM>
     47  ///\param CM Type of cost map.
     48  template<class GR, class CM>
    4949  struct FredmanTarjanDefaultTraits{
    5050    ///The graph type the algorithm runs on.
    … …  
    5454    ///The type of the map that stores the edge costs.
    5555    ///It must meet the \ref concept::ReadMap "ReadMap" concept.
    56     typedef LM CostMap;
     56    typedef CM CostMap;
    5757    //The type of the cost of the edges.
    58     typedef typename LM::Value Value;
     58    typedef typename CM::Value Value;
    5959    ///The type of the map that stores whether an edge is in the
    6060    ///spanning tree or not.
    … …  
    7777  ///%FredmanTarjan algorithm class to find a minimum spanning tree.
    7878 
    79   /// \ingroup spantree
    80   ///This class provides an efficient implementation of %FredmanTarjan algorithm
    81   ///whitch is sometimes a bit quicker than the Prim algorithm on larger graphs.
    82   ///Due to the structure of the algorithm, it has less controll functions than
    83   ///Prim.
    84   ///
    85   ///The running time is O(e*B(e,n)) where e is the number of edges, n is the
    86   ///number of nodes in the graph and B(e,n) is min { i | log^(i) n <= e/n}
    87   ///( log^(i+1) n = log(log^(i)) n )
    88   ///
    89   ///The edge costs are passed to the algorithm using a
    90   ///\ref concept::ReadMap "ReadMap",
    91   ///so it is easy to change it to any kind of cost.
    92   ///
    93   ///The type of the cost is determined by the
    94   ///\ref concept::ReadMap::Value "Value" of the cost map.
     79  /// \ingroup spantree
     80  ///
     81  ///This class provides an efficient implementation of %FredmanTarjan
     82  ///algorithm whitch is sometimes a bit quicker than the Prim
     83  ///algorithm on larger graphs.  Due to the structure of the
     84  ///algorithm, it has less controll functions than Prim.
     85  ///
     86  /// The running time is \f$ O(e\beta(e,n)) \f$ where
     87  /// \f$ \beta(e,n) = \min\{ i | \log^{i}(n) \le e/n\} \f$ and
     88  /// \f$ \log^{i+1}(n)=\log(\log^{i}(n)) \f$
     89  ///
     90  ///The edge costs are passed to the algorithm using a \ref
     91  ///concept::ReadMap "ReadMap", so it is easy to change it to any
     92  ///kind of cost.
     93  ///
     94  ///The type of the cost is determined by the \ref
     95  ///concept::ReadMap::Value "Value" of the cost map.
    9596  ///
    9697  ///\param GR The graph type the algorithm runs on. The default value
    9798  ///is \ref ListUGraph. The value of GR is not used directly by
    98   ///FredmanTarjan, it is only passed to \ref FredmanTarjanDefaultTraits.
    99   ///
    100   ///\param LM This read-only UEdgeMap determines the costs of the
     99  ///FredmanTarjan, it is only passed to \ref
     100  ///FredmanTarjanDefaultTraits.
     101  ///
     102  ///\param CM This read-only UEdgeMap determines the costs of the
    101103  ///edges. It is read once for each edge, so the map may involve in
    102   ///relatively time consuming process to compute the edge cost if
    103   ///it is necessary. The default map type is \ref
    104   ///concept::UGraph::UEdgeMap "UGraph::UEdgeMap<int>". The value
    105   ///of LM is not used directly by FredmanTarjan, it is only passed to \ref
    106   ///FredmanTarjanDefaultTraits.
    107   ///
    108   ///\param TR Traits class to set
    109   ///various data types used by the algorithm.  The default traits
    110   ///class is \ref FredmanTarjanDefaultTraits
    111   ///"FredmanTarjanDefaultTraits<GR,LM>".  See \ref
    112   ///FredmanTarjanDefaultTraits for the documentation of a FredmanTarjan traits
    113   ///class.
     104  ///relatively time consuming process to compute the edge cost if it
     105  ///is necessary. The default map type is \ref
     106  ///concept::UGraph::UEdgeMap "UGraph::UEdgeMap<int>". The value of
     107  ///CM is not used directly by FredmanTarjan, it is only passed to
     108  ///\ref FredmanTarjanDefaultTraits.
     109  ///
     110  ///\param TR Traits class to set various data types used by the
     111  ///algorithm.  The default traits class is \ref
     112  ///FredmanTarjanDefaultTraits "FredmanTarjanDefaultTraits<GR,CM>".
     113  ///See \ref FredmanTarjanDefaultTraits for the documentation of a
     114  ///FredmanTarjan traits class.
    114115  ///
    115116  ///\author Balazs Attila Mihaly
    … …  
    117118#ifdef DOXYGEN
    118119  template <typename GR,
    119             typename LM,
     120            typename CM,
    120121            typename TR>
    121122#else
    122123  template <typename GR=ListUGraph,
    123             typename LM=typename GR::template UEdgeMap<int>,
    124             typename TR=FredmanTarjanDefaultTraits<GR,LM> >
     124            typename CM=typename GR::template UEdgeMap<int>,
     125            typename TR=FredmanTarjanDefaultTraits<GR,CM> >
    125126#endif
    126127  class FredmanTarjan {
    127128  public:
    128     /**
    129      * \brief \ref Exception for uninitialized parameters.
    130      *
    131      * This error represents problems in the initialization
    132      * of the parameters of the algorithms.
    133      */
     129    ///\brief \ref Exception for uninitialized parameters.
     130    ///
     131    ///This error represents problems in the initialization
     132    ///of the parameters of the algorithms.
    134133    class UninitializedParameter : public lemon::UninitializedParameter {
    135134    public:
Note: See TracChangeset for help on using the changeset viewer.