Changeset 2042:bdc953f2a449 in lemon-0.x for lemon/fredman_tarjan.h
- Timestamp:
- 04/07/06 11:54:35 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2681
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/fredman_tarjan.h
r1993 r2042 45 45 ///Default traits class of FredmanTarjan class. 46 46 ///\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> 49 49 struct FredmanTarjanDefaultTraits{ 50 50 ///The graph type the algorithm runs on. … … 54 54 ///The type of the map that stores the edge costs. 55 55 ///It must meet the \ref concept::ReadMap "ReadMap" concept. 56 typedef LM CostMap;56 typedef CM CostMap; 57 57 //The type of the cost of the edges. 58 typedef typename LM::Value Value;58 typedef typename CM::Value Value; 59 59 ///The type of the map that stores whether an edge is in the 60 60 ///spanning tree or not. … … 77 77 ///%FredmanTarjan algorithm class to find a minimum spanning tree. 78 78 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. 95 96 /// 96 97 ///\param GR The graph type the algorithm runs on. The default value 97 98 ///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 101 103 ///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. 114 115 /// 115 116 ///\author Balazs Attila Mihaly … … 117 118 #ifdef DOXYGEN 118 119 template <typename GR, 119 typename LM,120 typename CM, 120 121 typename TR> 121 122 #else 122 123 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> > 125 126 #endif 126 127 class FredmanTarjan { 127 128 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. 134 133 class UninitializedParameter : public lemon::UninitializedParameter { 135 134 public:
Note: See TracChangeset
for help on using the changeset viewer.