42 |
42 |
43 ///Default traits class of FredmanTarjan class. |
43 ///Default traits class of FredmanTarjan class. |
44 |
44 |
45 ///Default traits class of FredmanTarjan class. |
45 ///Default traits class of FredmanTarjan class. |
46 ///\param GR Graph type. |
46 ///\param GR Graph type. |
47 ///\param LM Type of cost map. |
47 ///\param CM Type of cost map. |
48 template<class GR, class LM> |
48 template<class GR, class CM> |
49 struct FredmanTarjanDefaultTraits{ |
49 struct FredmanTarjanDefaultTraits{ |
50 ///The graph type the algorithm runs on. |
50 ///The graph type the algorithm runs on. |
51 typedef GR UGraph; |
51 typedef GR UGraph; |
52 ///The type of the map that stores the edge costs. |
52 ///The type of the map that stores the edge costs. |
53 |
53 |
54 ///The type of the map that stores the edge costs. |
54 ///The type of the map that stores the edge costs. |
55 ///It must meet the \ref concept::ReadMap "ReadMap" concept. |
55 ///It must meet the \ref concept::ReadMap "ReadMap" concept. |
56 typedef LM CostMap; |
56 typedef CM CostMap; |
57 //The type of the cost of the edges. |
57 //The type of the cost of the edges. |
58 typedef typename LM::Value Value; |
58 typedef typename CM::Value Value; |
59 ///The type of the map that stores whether an edge is in the |
59 ///The type of the map that stores whether an edge is in the |
60 ///spanning tree or not. |
60 ///spanning tree or not. |
61 |
61 |
62 ///The type of the map that stores whether an edge is in the |
62 ///The type of the map that stores whether an edge is in the |
63 ///spanning tree or not. |
63 ///spanning tree or not. |
74 } |
74 } |
75 }; |
75 }; |
76 |
76 |
77 ///%FredmanTarjan algorithm class to find a minimum spanning tree. |
77 ///%FredmanTarjan algorithm class to find a minimum spanning tree. |
78 |
78 |
79 /// \ingroup spantree |
79 /// \ingroup spantree |
80 ///This class provides an efficient implementation of %FredmanTarjan algorithm |
80 /// |
81 ///whitch is sometimes a bit quicker than the Prim algorithm on larger graphs. |
81 ///This class provides an efficient implementation of %FredmanTarjan |
82 ///Due to the structure of the algorithm, it has less controll functions than |
82 ///algorithm whitch is sometimes a bit quicker than the Prim |
83 ///Prim. |
83 ///algorithm on larger graphs. Due to the structure of the |
84 /// |
84 ///algorithm, it has less controll functions than Prim. |
85 ///The running time is O(e*B(e,n)) where e is the number of edges, n is the |
85 /// |
86 ///number of nodes in the graph and B(e,n) is min { i | log^(i) n <= e/n} |
86 /// The running time is \f$ O(e\beta(e,n)) \f$ where |
87 ///( log^(i+1) n = log(log^(i)) n ) |
87 /// \f$ \beta(e,n) = \min\{ i | \log^{i}(n) \le e/n\} \f$ and |
88 /// |
88 /// \f$ \log^{i+1}(n)=\log(\log^{i}(n)) \f$ |
89 ///The edge costs are passed to the algorithm using a |
89 /// |
90 ///\ref concept::ReadMap "ReadMap", |
90 ///The edge costs are passed to the algorithm using a \ref |
91 ///so it is easy to change it to any kind of cost. |
91 ///concept::ReadMap "ReadMap", so it is easy to change it to any |
92 /// |
92 ///kind of cost. |
93 ///The type of the cost is determined by the |
93 /// |
94 ///\ref concept::ReadMap::Value "Value" of the cost map. |
94 ///The type of the cost is determined by the \ref |
|
95 ///concept::ReadMap::Value "Value" of the cost map. |
95 /// |
96 /// |
96 ///\param GR The graph type the algorithm runs on. The default value |
97 ///\param GR The graph type the algorithm runs on. The default value |
97 ///is \ref ListUGraph. The value of GR is not used directly by |
98 ///is \ref ListUGraph. The value of GR is not used directly by |
98 ///FredmanTarjan, it is only passed to \ref FredmanTarjanDefaultTraits. |
99 ///FredmanTarjan, it is only passed to \ref |
99 /// |
100 ///FredmanTarjanDefaultTraits. |
100 ///\param LM This read-only UEdgeMap determines the costs of the |
101 /// |
|
102 ///\param CM This read-only UEdgeMap determines the costs of the |
101 ///edges. It is read once for each edge, so the map may involve in |
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 |
104 ///relatively time consuming process to compute the edge cost if it |
103 ///it is necessary. The default map type is \ref |
105 ///is necessary. The default map type is \ref |
104 ///concept::UGraph::UEdgeMap "UGraph::UEdgeMap<int>". The value |
106 ///concept::UGraph::UEdgeMap "UGraph::UEdgeMap<int>". The value of |
105 ///of LM is not used directly by FredmanTarjan, it is only passed to \ref |
107 ///CM is not used directly by FredmanTarjan, it is only passed to |
106 ///FredmanTarjanDefaultTraits. |
108 ///\ref FredmanTarjanDefaultTraits. |
107 /// |
109 /// |
108 ///\param TR Traits class to set |
110 ///\param TR Traits class to set various data types used by the |
109 ///various data types used by the algorithm. The default traits |
111 ///algorithm. The default traits class is \ref |
110 ///class is \ref FredmanTarjanDefaultTraits |
112 ///FredmanTarjanDefaultTraits "FredmanTarjanDefaultTraits<GR,CM>". |
111 ///"FredmanTarjanDefaultTraits<GR,LM>". See \ref |
113 ///See \ref FredmanTarjanDefaultTraits for the documentation of a |
112 ///FredmanTarjanDefaultTraits for the documentation of a FredmanTarjan traits |
114 ///FredmanTarjan traits class. |
113 ///class. |
|
114 /// |
115 /// |
115 ///\author Balazs Attila Mihaly |
116 ///\author Balazs Attila Mihaly |
116 |
117 |
117 #ifdef DOXYGEN |
118 #ifdef DOXYGEN |
118 template <typename GR, |
119 template <typename GR, |
119 typename LM, |
120 typename CM, |
120 typename TR> |
121 typename TR> |
121 #else |
122 #else |
122 template <typename GR=ListUGraph, |
123 template <typename GR=ListUGraph, |
123 typename LM=typename GR::template UEdgeMap<int>, |
124 typename CM=typename GR::template UEdgeMap<int>, |
124 typename TR=FredmanTarjanDefaultTraits<GR,LM> > |
125 typename TR=FredmanTarjanDefaultTraits<GR,CM> > |
125 #endif |
126 #endif |
126 class FredmanTarjan { |
127 class FredmanTarjan { |
127 public: |
128 public: |
128 /** |
129 ///\brief \ref Exception for uninitialized parameters. |
129 * \brief \ref Exception for uninitialized parameters. |
130 /// |
130 * |
131 ///This error represents problems in the initialization |
131 * This error represents problems in the initialization |
132 ///of the parameters of the algorithms. |
132 * of the parameters of the algorithms. |
|
133 */ |
|
134 class UninitializedParameter : public lemon::UninitializedParameter { |
133 class UninitializedParameter : public lemon::UninitializedParameter { |
135 public: |
134 public: |
136 virtual const char* exceptionName() const { |
135 virtual const char* exceptionName() const { |
137 return "lemon::FredmanTarjan::UninitializedParameter"; |
136 return "lemon::FredmanTarjan::UninitializedParameter"; |
138 } |
137 } |