Changeset 209:765619b7cbb2 in lemon for lemon/kruskal.h
 Timestamp:
 07/13/08 20:51:02 (13 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/kruskal.h
r194 r209 1 /* * C++*2 * 3 * This file is a part of LEMON, a generic C++ optimization library 1 /* * mode: C++; indenttabsmode: nil; * 2 * 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 5 * Copyright (C) 20032008 … … 46 46 template <typename Digraph, typename In, typename Out> 47 47 typename disable_if<lemon::UndirectedTagIndicator<Digraph>, 48 48 typename In::value_type::second_type >::type 49 49 kruskal(const Digraph& digraph, const In& in, Out& out,dummy<0> = 0) { 50 50 typedef typename In::value_type::second_type Value; 51 51 typedef typename Digraph::template NodeMap<int> IndexMap; 52 52 typedef typename Digraph::Node Node; 53 53 54 54 IndexMap index(digraph); 55 55 UnionFind<IndexMap> uf(index); … … 57 57 uf.insert(it); 58 58 } 59 59 60 60 Value tree_value = 0; 61 61 for (typename In::const_iterator it = in.begin(); it != in.end(); ++it) { … … 75 75 template <typename Graph, typename In, typename Out> 76 76 typename enable_if<lemon::UndirectedTagIndicator<Graph>, 77 77 typename In::value_type::second_type >::type 78 78 kruskal(const Graph& graph, const In& in, Out& out,dummy<1> = 1) { 79 79 typedef typename In::value_type::second_type Value; 80 80 typedef typename Graph::template NodeMap<int> IndexMap; 81 81 typedef typename Graph::Node Node; 82 82 83 83 IndexMap index(graph); 84 84 UnionFind<IndexMap> uf(index); … … 86 86 uf.insert(it); 87 87 } 88 88 89 89 Value tree_value = 0; 90 90 for (typename In::const_iterator it = in.begin(); it != in.end(); ++it) { … … 105 105 typedef typename Sequence::value_type Value; 106 106 bool operator()(const Value& left, const Value& right) { 107 107 return left.second < right.second; 108 108 } 109 109 }; … … 115 115 116 116 template <typename In> 117 struct SequenceInputIndicator<In, 117 struct SequenceInputIndicator<In, 118 118 typename exists<typename In::value_type::first_type>::type> { 119 119 static const bool value = true; … … 126 126 127 127 template <typename In> 128 struct MapInputIndicator<In, 128 struct MapInputIndicator<In, 129 129 typename exists<typename In::Value>::type> { 130 130 static const bool value = true; … … 135 135 static const bool value = false; 136 136 }; 137 137 138 138 template <typename Out> 139 struct SequenceOutputIndicator<Out, 139 struct SequenceOutputIndicator<Out, 140 140 typename exists<typename Out::value_type>::type> { 141 141 static const bool value = true; … … 148 148 149 149 template <typename Out> 150 struct MapOutputIndicator<Out, 150 struct MapOutputIndicator<Out, 151 151 typename exists<typename Out::Value>::type> { 152 152 static const bool value = true; … … 158 158 template <typename In> 159 159 struct KruskalValueSelector<In, 160 typename enable_if<SequenceInputIndicator<In>, void>::type> 161 { 162 typedef typename In::value_type::second_type Value; 163 }; 160 typename enable_if<SequenceInputIndicator<In>, void>::type> 161 { 162 typedef typename In::value_type::second_type Value; 163 }; 164 164 165 165 template <typename In> 166 166 struct KruskalValueSelector<In, 167 typename enable_if<MapInputIndicator<In>, void>::type> 167 typename enable_if<MapInputIndicator<In>, void>::type> 168 168 { 169 169 typedef typename In::Value Value; 170 }; 171 170 }; 171 172 172 template <typename Graph, typename In, typename Out, 173 173 typename InEnable = void> … … 177 177 typename InEnable = void> 178 178 struct KruskalOutputSelector {}; 179 179 180 180 template <typename Graph, typename In, typename Out> 181 181 struct KruskalInputSelector<Graph, In, Out, 182 typename enable_if<SequenceInputIndicator<In>, void>::type > 182 typename enable_if<SequenceInputIndicator<In>, void>::type > 183 183 { 184 184 typedef typename In::value_type::second_type Value; … … 193 193 template <typename Graph, typename In, typename Out> 194 194 struct KruskalInputSelector<Graph, In, Out, 195 typename enable_if<MapInputIndicator<In>, void>::type > 195 typename enable_if<MapInputIndicator<In>, void>::type > 196 196 { 197 197 typedef typename In::Value Value; … … 202 202 typedef std::vector<std::pair<MapArc, Value> > Sequence; 203 203 Sequence seq; 204 204 205 205 for (MapArcIt it(graph); it != INVALID; ++it) { 206 206 seq.push_back(std::make_pair(it, in[it])); … … 225 225 template <typename Graph, typename In, typename Out> 226 226 struct KruskalOutputSelector<Graph, In, Out, 227 typename enable_if<SequenceOutputIndicator<Out>, void>::type > 227 typename enable_if<SequenceOutputIndicator<Out>, void>::type > 228 228 { 229 229 typedef typename In::value_type::second_type Value; … … 239 239 template <typename Graph, typename In, typename Out> 240 240 struct KruskalOutputSelector<Graph, In, Out, 241 typename enable_if<MapOutputIndicator<Out>, void>::type > 241 typename enable_if<MapOutputIndicator<Out>, void>::type > 242 242 { 243 243 typedef typename In::value_type::second_type Value; … … 255 255 /// a graph. 256 256 /// 257 /// This function runs Kruskal's algorithm to find a minimum cost 257 /// This function runs Kruskal's algorithm to find a minimum cost 258 258 /// spanning tree. 259 259 /// Due to some C++ hacking, it accepts various input and output types. 260 260 /// 261 261 /// \param g The graph the algorithm runs on. 262 /// It can be either \ref concepts::Digraph "directed" or 262 /// It can be either \ref concepts::Digraph "directed" or 263 263 /// \ref concepts::Graph "undirected". 264 /// If the graph is directed, the algorithm consider it to be 264 /// If the graph is directed, the algorithm consider it to be 265 265 /// undirected by disregarding the direction of the arcs. 266 266 /// 267 /// \param in This object is used to describe the arc/edge costs. 267 /// \param in This object is used to describe the arc/edge costs. 268 268 /// It can be one of the following choices. 269 269 ///  An STL compatible 'Forward Container' with … … 273 273 /// along with the assigned cost. <em>They must be in a 274 274 /// costascending order.</em> 275 ///  Any readable arc/edge map. The values of the map indicate the 275 ///  Any readable arc/edge map. The values of the map indicate the 276 276 /// arc/edge costs. 277 277 /// … … 293 293 ///\endcode 294 294 /// Or if we don't know in advance the size of the tree, we can 295 /// write this. 295 /// write this. 296 296 ///\code 297 297 /// std::vector<Arc> tree; 298 /// kruskal(g,cost,std::back_inserter(tree)); 298 /// kruskal(g,cost,std::back_inserter(tree)); 299 299 ///\endcode 300 300 /// … … 308 308 template <class Graph, class In, class Out> 309 309 Value kruskal(GR const& g, const In& in, Out& out) 310 #else 310 #else 311 311 template <class Graph, class In, class Out> 312 inline typename _kruskal_bits::KruskalValueSelector<In>::Value 313 kruskal(const Graph& graph, const In& in, Out& out) 312 inline typename _kruskal_bits::KruskalValueSelector<In>::Value 313 kruskal(const Graph& graph, const In& in, Out& out) 314 314 #endif 315 315 { … … 318 318 } 319 319 320 321 320 321 322 322 323 323 template <class Graph, class In, class Out> … … 327 327 return _kruskal_bits::KruskalInputSelector<Graph, In, const Out>:: 328 328 kruskal(graph, in, out); 329 } 329 } 330 330 331 331 } //namespace lemon
Note: See TracChangeset
for help on using the changeset viewer.