34 #include <lemon/error.h> |
34 #include <lemon/error.h> |
35 #include <lemon/maps.h> |
35 #include <lemon/maps.h> |
36 #include <lemon/bits/traits.h> |
36 #include <lemon/bits/traits.h> |
37 #include <lemon/graph_utils.h> |
37 #include <lemon/graph_utils.h> |
38 |
38 |
39 #include <lemon/concept/ugraph.h> |
39 #include <lemon/concepts/ugraph.h> |
40 |
40 |
41 namespace lemon { |
41 namespace lemon { |
42 |
42 |
43 ///Default traits class of FredmanTarjan class. |
43 ///Default traits class of FredmanTarjan class. |
44 |
44 |
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 concepts::ReadMap "ReadMap" concept. |
56 typedef CM 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 CM::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. |
64 ///It must meet the \ref concept::ReadWriteMap "ReadWriteMap" concept. |
64 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
65 ///By default it is a BoolEdgeMap. |
65 ///By default it is a BoolEdgeMap. |
66 typedef typename UGraph::template UEdgeMap<bool> TreeMap; |
66 typedef typename UGraph::template UEdgeMap<bool> TreeMap; |
67 ///Instantiates a TreeMap. |
67 ///Instantiates a TreeMap. |
68 |
68 |
69 ///This function instantiates a \ref TreeMap. |
69 ///This function instantiates a \ref TreeMap. |
86 /// The running time is \f$ O(e\beta(e,n)) \f$ where |
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 |
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$ |
88 /// \f$ \log^{i+1}(n)=\log(\log^{i}(n)) \f$ |
89 /// |
89 /// |
90 ///The edge costs are passed to the algorithm using a \ref |
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 |
91 ///concepts::ReadMap "ReadMap", so it is easy to change it to any |
92 ///kind of cost. |
92 ///kind of cost. |
93 /// |
93 /// |
94 ///The type of the cost is determined by the \ref |
94 ///The type of the cost is determined by the \ref |
95 ///concept::ReadMap::Value "Value" of the cost map. |
95 ///concepts::ReadMap::Value "Value" of the cost map. |
96 /// |
96 /// |
97 ///\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 |
98 ///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 |
99 ///FredmanTarjan, it is only passed to \ref |
99 ///FredmanTarjan, it is only passed to \ref |
100 ///FredmanTarjanDefaultTraits. |
100 ///FredmanTarjanDefaultTraits. |
101 /// |
101 /// |
102 ///\param CM This read-only UEdgeMap determines the costs of the |
102 ///\param CM This read-only UEdgeMap determines the costs of the |
103 ///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 |
104 ///relatively time consuming process to compute the edge cost if it |
104 ///relatively time consuming process to compute the edge cost if it |
105 ///is necessary. The default map type is \ref |
105 ///is necessary. The default map type is \ref |
106 ///concept::UGraph::UEdgeMap "UGraph::UEdgeMap<int>". The value of |
106 ///concepts::UGraph::UEdgeMap "UGraph::UEdgeMap<int>". The value of |
107 ///CM is not used directly by FredmanTarjan, it is only passed to |
107 ///CM is not used directly by FredmanTarjan, it is only passed to |
108 ///\ref FredmanTarjanDefaultTraits. |
108 ///\ref FredmanTarjanDefaultTraits. |
109 /// |
109 /// |
110 ///\param TR Traits class to set various data types used by the |
110 ///\param TR Traits class to set various data types used by the |
111 ///algorithm. The default traits class is \ref |
111 ///algorithm. The default traits class is \ref |
363 ///\param _cost the cost map used by the algorithm. |
363 ///\param _cost the cost map used by the algorithm. |
364 FredmanTarjan(const UGraph& _graph, const CostMap& _cost) : |
364 FredmanTarjan(const UGraph& _graph, const CostMap& _cost) : |
365 graph(&_graph), cost(&_cost), |
365 graph(&_graph), cost(&_cost), |
366 _tree(0), local_tree(false) |
366 _tree(0), local_tree(false) |
367 { |
367 { |
368 checkConcept<concept::UGraph, UGraph>(); |
368 checkConcept<concepts::UGraph, UGraph>(); |
369 } |
369 } |
370 |
370 |
371 ///Destructor. |
371 ///Destructor. |
372 ~FredmanTarjan(){ |
372 ~FredmanTarjan(){ |
373 if(local_tree) delete _tree; |
373 if(local_tree) delete _tree; |