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

Ignore:
Timestamp:
04/07/06 11:54:35 (14 years ago)
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 ///Default traits class of FredmanTarjan class. ///\param GR Graph type. ///\param LM Type of cost map. template ///\param CM Type of cost map. template struct FredmanTarjanDefaultTraits{ ///The graph type the algorithm runs on. ///The type of the map that stores the edge costs. ///It must meet the \ref concept::ReadMap "ReadMap" concept. typedef LM CostMap; typedef CM CostMap; //The type of the cost of the edges. typedef typename LM::Value Value; typedef typename CM::Value Value; ///The type of the map that stores whether an edge is in the ///spanning tree or not. ///%FredmanTarjan algorithm class to find a minimum spanning tree. /// \ingroup spantree ///This class provides an efficient implementation of %FredmanTarjan algorithm ///whitch is sometimes a bit quicker than the Prim algorithm on larger graphs. ///Due to the structure of the algorithm, it has less controll functions than ///Prim. /// ///The running time is O(e*B(e,n)) where e is the number of edges, n is the ///number of nodes in the graph and B(e,n) is min { i | log^(i) n <= e/n} ///( log^(i+1) n = log(log^(i)) n ) /// ///The edge costs are passed to the algorithm using a ///\ref concept::ReadMap "ReadMap", ///so it is easy to change it to any kind of cost. /// ///The type of the cost is determined by the ///\ref concept::ReadMap::Value "Value" of the cost map. /// \ingroup spantree /// ///This class provides an efficient implementation of %FredmanTarjan ///algorithm whitch is sometimes a bit quicker than the Prim ///algorithm on larger graphs. Due to the structure of the ///algorithm, it has less controll functions than Prim. /// /// The running time is \f$ O(e\beta(e,n)) \f$where /// \f$ \beta(e,n) = \min\{ i | \log^{i}(n) \le e/n\} \f$and /// \f$ \log^{i+1}(n)=\log(\log^{i}(n)) \f\$ /// ///The edge costs are passed to the algorithm using a \ref ///concept::ReadMap "ReadMap", so it is easy to change it to any ///kind of cost. /// ///The type of the cost is determined by the \ref ///concept::ReadMap::Value "Value" of the cost map. /// ///\param GR The graph type the algorithm runs on. The default value ///is \ref ListUGraph. The value of GR is not used directly by ///FredmanTarjan, it is only passed to \ref FredmanTarjanDefaultTraits. /// ///\param LM This read-only UEdgeMap determines the costs of the ///FredmanTarjan, it is only passed to \ref ///FredmanTarjanDefaultTraits. /// ///\param CM This read-only UEdgeMap determines the costs of the ///edges. It is read once for each edge, so the map may involve in ///relatively time consuming process to compute the edge cost if ///it is necessary. The default map type is \ref ///concept::UGraph::UEdgeMap "UGraph::UEdgeMap". The value ///of LM is not used directly by FredmanTarjan, it is only passed to \ref ///FredmanTarjanDefaultTraits. /// ///\param TR Traits class to set ///various data types used by the algorithm.  The default traits ///class is \ref FredmanTarjanDefaultTraits ///"FredmanTarjanDefaultTraits".  See \ref ///FredmanTarjanDefaultTraits for the documentation of a FredmanTarjan traits ///class. ///relatively time consuming process to compute the edge cost if it ///is necessary. The default map type is \ref ///concept::UGraph::UEdgeMap "UGraph::UEdgeMap". The value of ///CM is not used directly by FredmanTarjan, it is only passed to ///\ref FredmanTarjanDefaultTraits. /// ///\param TR Traits class to set various data types used by the ///algorithm.  The default traits class is \ref ///FredmanTarjanDefaultTraits "FredmanTarjanDefaultTraits". ///See \ref FredmanTarjanDefaultTraits for the documentation of a ///FredmanTarjan traits class. /// ///\author Balazs Attila Mihaly #ifdef DOXYGEN template #else template , typename TR=FredmanTarjanDefaultTraits > typename CM=typename GR::template UEdgeMap, typename TR=FredmanTarjanDefaultTraits > #endif class FredmanTarjan { public: /** * \brief \ref Exception for uninitialized parameters. * * This error represents problems in the initialization * of the parameters of the algorithms. */ ///\brief \ref Exception for uninitialized parameters. /// ///This error represents problems in the initialization ///of the parameters of the algorithms. class UninitializedParameter : public lemon::UninitializedParameter { public:
Note: See TracChangeset for help on using the changeset viewer.