Changeset 1547:dd57a540ff5f in lemon0.x for lemon/kruskal.h
 Timestamp:
 07/12/05 18:16:19 (14 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2043
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/kruskal.h
r1449 r1547 46 46 47 47 /// This function runs Kruskal's algorithm to find a minimum cost tree. 48 /// \param GThe graph the algorithm runs on. The algorithm considers the48 /// \param g The graph the algorithm runs on. The algorithm considers the 49 49 /// graph to be undirected, the direction of the edges are not used. 50 50 /// … … 77 77 template <class GR, class IN, class OUT> 78 78 typename IN::value_type::second_type 79 kruskal(GR const& G, IN const& in,79 kruskal(GR const& g, IN const& in, 80 80 OUT& out) 81 81 { … … 84 84 typedef typename GR::Node Node; 85 85 86 NodeIntMap comp( G, 1);86 NodeIntMap comp(g, 1); 87 87 UnionFind<Node,NodeIntMap> uf(comp); 88 88 … … 90 90 for (typename IN::const_iterator p = in.begin(); 91 91 p!=in.end(); ++p ) { 92 if ( uf.join( G.target((*p).first),93 G.source((*p).first)) ) {92 if ( uf.join(g.target((*p).first), 93 g.source((*p).first)) ) { 94 94 out.set((*p).first, true); 95 95 tot_cost += (*p).second; … … 110 110 /// 111 111 /// A typical examle is the following call: 112 /// <tt>kruskal( G, some_input, makeSequenceOutput(iterator))</tt>.112 /// <tt>kruskal(g, some_input, makeSequenceOutput(iterator))</tt>. 113 113 /// Here, the third argument is a temporary object (which wraps around an 114 114 /// iterator with a writable bool map interface), and thus by rules of C++ … … 131 131 inline 132 132 typename IN::value_type::second_type 133 kruskal(GR const& G, IN const& edges, OUT const& out_map)133 kruskal(GR const& g, IN const& edges, OUT const& out_map) 134 134 { 135 135 NonConstMapWr<OUT> map_wr(out_map); 136 return kruskal( G, edges, map_wr);136 return kruskal(g, edges, map_wr); 137 137 } 138 138 … … 176 176 template<class _GR> 177 177 typename enable_if<typename _GR::UndirTag,void>::type 178 fillWithEdges(const _GR& G, const Map& m,dummy<0> = 0)178 fillWithEdges(const _GR& g, const Map& m,dummy<0> = 0) 179 179 { 180 for(typename GR::UndirEdgeIt e( G);e!=INVALID;++e)180 for(typename GR::UndirEdgeIt e(g);e!=INVALID;++e) 181 181 push_back(value_type(typename GR::Edge(e,true), m[e])); 182 182 } … … 184 184 template<class _GR> 185 185 typename disable_if<typename _GR::UndirTag,void>::type 186 fillWithEdges(const _GR& G, const Map& m,dummy<1> = 1)186 fillWithEdges(const _GR& g, const Map& m,dummy<1> = 1) 187 187 { 188 for(typename GR::EdgeIt e( G);e!=INVALID;++e)188 for(typename GR::EdgeIt e(g);e!=INVALID;++e) 189 189 push_back(value_type(e, m[e])); 190 190 } … … 197 197 } 198 198 199 KruskalMapInput(GR const& G, Map const& m) {200 fillWithEdges( G,m);199 KruskalMapInput(GR const& g, Map const& m) { 200 fillWithEdges(g,m); 201 201 sort(); 202 202 } … … 212 212 /// want to use the function kruskalEdgeMap() instead. 213 213 /// 214 ///\param GThe type of the graph the algorithm runs on.214 ///\param g The type of the graph the algorithm runs on. 215 215 ///\param m An edge map containing the cost of the edges. 216 216 ///\par … … 224 224 template<class GR, class Map> 225 225 inline 226 KruskalMapInput<GR,Map> makeKruskalMapInput(const GR & G,const Map &m)226 KruskalMapInput<GR,Map> makeKruskalMapInput(const GR &g,const Map &m) 227 227 { 228 return KruskalMapInput<GR,Map>( G,m);228 return KruskalMapInput<GR,Map>(g,m); 229 229 } 230 230 … … 292 292 /// Input is from an edge map, output is a plain bool map. 293 293 /// 294 ///\param GThe type of the graph the algorithm runs on.294 ///\param g The type of the graph the algorithm runs on. 295 295 ///\param in An edge map containing the cost of the edges. 296 296 ///\par … … 311 311 inline 312 312 typename IN::Value 313 kruskalEdgeMap(GR const& G,313 kruskalEdgeMap(GR const& g, 314 314 IN const& in, 315 315 RET &out) { 316 return kruskal( G,317 KruskalMapInput<GR,IN>( G,in),316 return kruskal(g, 317 KruskalMapInput<GR,IN>(g,in), 318 318 out); 319 319 } … … 325 325 /// Input is from an edge map, output is an STL Sequence. 326 326 /// 327 ///\param GThe type of the graph the algorithm runs on.327 ///\param g The type of the graph the algorithm runs on. 328 328 ///\param in An edge map containing the cost of the edges. 329 329 ///\par … … 336 336 /// <tt>GR::Edge</tt> as its <tt>value_type</tt>. 337 337 /// The algorithm copies the elements of the found tree into this sequence. 338 /// For example, if we know that the spanning tree of the graph \c Ghas338 /// For example, if we know that the spanning tree of the graph \c g has 339 339 /// say 53 edges then 340 340 /// we can put its edges into a STL vector \c tree with a code like this. 341 341 /// \code 342 342 /// std::vector<Edge> tree(53); 343 /// kruskalEdgeMap_IteratorOut( G,cost,tree.begin());343 /// kruskalEdgeMap_IteratorOut(g,cost,tree.begin()); 344 344 /// \endcode 345 345 /// Or if we don't know in advance the size of the tree, we can write this. 346 346 /// \code 347 347 /// std::vector<Edge> tree; 348 /// kruskalEdgeMap_IteratorOut( G,cost,std::back_inserter(tree));348 /// kruskalEdgeMap_IteratorOut(g,cost,std::back_inserter(tree)); 349 349 /// \endcode 350 350 /// … … 356 356 inline 357 357 typename IN::Value 358 kruskalEdgeMap_IteratorOut(const GR& G,358 kruskalEdgeMap_IteratorOut(const GR& g, 359 359 const IN& in, 360 360 RET out) 361 361 { 362 362 KruskalSequenceOutput<RET> _out(out); 363 return kruskal( G, KruskalMapInput<GR,IN>(G, in), _out);363 return kruskal(g, KruskalMapInput<GR,IN>(g, in), _out); 364 364 } 365 365
Note: See TracChangeset
for help on using the changeset viewer.