Changeset 1547:dd57a540ff5f in lemon-0.x
- Timestamp:
- 07/12/05 18:16:19 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2043
- Location:
- lemon
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/graph_utils.h
r1540 r1547 194 194 /// \brief Copy a map. 195 195 /// 196 /// Th sifunction copies the \c source map to the \c target map. It uses the196 /// This function copies the \c source map to the \c target map. It uses the 197 197 /// given iterator to iterate on the data structure and it uses the \c ref 198 198 /// mapping to convert the source's keys to the target's keys. -
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 -
lemon/maps.h
r1537 r1547 222 222 }; 223 223 224 ///Convert the \c Value of a map sto another type.224 ///Convert the \c Value of a map to another type. 225 225 226 226 ///This \ref concept::ReadMap "read only map" 227 227 ///converts the \c Value of a maps to type \c T. 228 ///Its \c Value is inherited from \c M. 229 /// 230 ///\bug wrong documentation 228 ///Its \c Key is inherited from \c M. 231 229 template<class M, class T> 232 230 class ConvertMap { … … 305 303 } 306 304 307 ///Shift a map swith a constant.305 ///Shift a map with a constant. 308 306 309 307 ///This \ref concept::ReadMap "read only map" returns the sum of the … … 315 313 /// ShiftMap<X> sh(x,v); 316 314 ///\endcode 317 ///i t is equivalent with315 ///is equivalent with 318 316 ///\code 319 317 /// ConstMap<X::Key, X::Value> c_tmp(v); … … 356 354 357 355 ///This \ref concept::ReadMap "read only map" returns the difference 358 ///of the values returned bythe two356 ///of the values of the two 359 357 ///given maps. Its \c Key and \c Value will be inherited from \c M1. 360 358 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1. … … 392 390 393 391 ///This \ref concept::ReadMap "read only map" returns the product of the 394 ///values returned bythe two392 ///values of the two 395 393 ///given 396 394 ///maps. Its \c Key and \c Value will be inherited from \c M1. … … 425 423 } 426 424 427 ///Scale a maps with a constant.425 ///Scales a maps with a constant. 428 426 429 427 ///This \ref concept::ReadMap "read only map" returns the value of the 430 ///given map multip ied with a constant value.428 ///given map multiplied with a constant value. 431 429 ///Its \c Key and \c Value is inherited from \c M. 432 430 /// … … 435 433 /// ScaleMap<X> sc(x,v); 436 434 ///\endcode 437 ///i t is equivalent with435 ///is equivalent with 438 436 ///\code 439 437 /// ConstMap<X::Key, X::Value> c_tmp(v); … … 476 474 477 475 ///This \ref concept::ReadMap "read only map" returns the quotient of the 478 ///values returned bythe two476 ///values of the two 479 477 ///given maps. Its \c Key and \c Value will be inherited from \c M1. 480 478 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1. … … 553 551 } 554 552 555 ///Combine of two maps using an STL (binary) functor.556 557 ///Combine of two maps using an STL (binary) functor.558 /// 559 /// 560 ///This \ref concept::ReadMap "read only map" takes t o maps and a553 ///Combines of two maps using an STL (binary) functor. 554 555 ///Combines of two maps using an STL (binary) functor. 556 /// 557 /// 558 ///This \ref concept::ReadMap "read only map" takes two maps and a 561 559 ///binary functor and returns the composition of 562 ///t wo560 ///the two 563 561 ///given maps unsing the functor. 564 562 ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2 … … 790 788 791 789 792 ///Appl yall map setting operations to two maps790 ///Applies all map setting operations to two maps 793 791 794 792 ///This map has two \ref concept::WriteMap "writable map"
Note: See TracChangeset
for help on using the changeset viewer.