Changeset - r194:74cd0c58b348
« 193:65cba1
196:420013 »
gravatar
kpeter (Peter Kovacs)
kpeter@inf.elte.hu
Doc improvements for kruskal()
0 1 0
default
1 file changed with 23 insertions and 19 deletions:
lemon/kruskal.h
23
19
↑ Collapse diff ↑
lemon/kruskal.h
Ignore white space 6 line context
... ... 
@@ -32,9 +32,9 @@
32 32 

			




	33
	33
	
		
///\ingroup spantree


			




	34
	34
	
		
///\file


			




	35
	
	
		
///\brief Kruskal's algorithm to compute a minimum cost tree


			




	
	35
	
		
///\brief Kruskal's algorithm to compute a minimum cost spanning tree


			




	36
	36
	
		
///


			




	37
	
	
		
///Kruskal's algorithm to compute a minimum cost tree.


			




	
	37
	
		
///Kruskal's algorithm to compute a minimum cost spanning tree.


			




	38
	38
	
		
///


			




	39
	39
	
		

			




	40
	40
	
		
namespace lemon {


			




	...
	...
	
		
@@ -251,9 +251,11 @@


			




	251
	251
	
		

			




	252
	252
	
		
  /// \ingroup spantree


			




	253
	253
	
		
  ///


			




	254
	
	
		
  /// \brief Kruskal's algorithm to find a minimum cost tree of a graph.


			




	
	254
	
		
  /// \brief Kruskal algorithm to find a minimum cost spanning tree of


			




	
	255
	
		
  /// a graph.


			




	255
	256
	
		
  ///


			




	256
	
	
		
  /// This function runs Kruskal's algorithm to find a minimum cost tree.


			




	
	257
	
		
  /// This function runs Kruskal's algorithm to find a minimum cost 


			




	
	258
	
		
  /// spanning tree.


			




	257
	259
	
		
  /// Due to some C++ hacking, it accepts various input and output types.


			




	258
	260
	
		
  ///


			




	259
	261
	
		
  /// \param g The graph the algorithm runs on.


			




	...
	...
	
		
@@ -262,24 +264,25 @@


			




	262
	264
	
		
  /// If the graph is directed, the algorithm consider it to be 


			




	263
	265
	
		
  /// undirected by disregarding the direction of the arcs.


			




	264
	266
	
		
  ///


			




	265
	
	
		
  /// \param in This object is used to describe the arc costs. It can be one


			




	266
	
	
		
  /// of the following choices.


			




	
	267
	
		
  /// \param in This object is used to describe the arc/edge costs. 


			




	
	268
	
		
  /// It can be one of the following choices.


			




	267
	269
	
		
  /// - An STL compatible 'Forward Container' with


			




	268
	
	
		
  /// <tt>std::pair<GR::Edge,X></tt> or


			




	269
	
	
		
  /// <tt>std::pair<GR::Arc,X></tt> as its <tt>value_type</tt>, where


			




	270
	
	
		
  /// \c X is the type of the costs. The pairs indicates the arcs


			




	
	270
	
		
  /// <tt>std::pair<GR::Arc,X></tt> or


			




	
	271
	
		
  /// <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>, where


			




	
	272
	
		
  /// \c X is the type of the costs. The pairs indicates the arcs/edges


			




	271
	273
	
		
  /// along with the assigned cost. <em>They must be in a


			




	272
	274
	
		
  /// cost-ascending order.</em>


			




	273
	
	
		
  /// - Any readable Arc map. The values of the map indicate the arc costs.


			




	
	275
	
		
  /// - Any readable arc/edge map. The values of the map indicate the 


			




	
	276
	
		
  /// arc/edge costs.


			




	274
	277
	
		
  ///


			




	275
	
	
		
  /// \retval out Here we also have a choise.


			




	276
	
	
		
  /// - It can be a writable \c bool arc map.  After running the


			




	277
	
	
		
  /// algorithm this will contain the found minimum cost spanning


			




	278
	
	
		
  /// tree: the value of an arc will be set to \c true if it belongs


			




	
	278
	
		
  /// \retval out Here we also have a choice.


			




	
	279
	
		
  /// - It can be a writable \c bool arc/edge map. After running the


			




	
	280
	
		
  /// algorithm it will contain the found minimum cost spanning


			




	
	281
	
		
  /// tree: the value of an arc/edge will be set to \c true if it belongs


			




	279
	282
	
		
  /// to the tree, otherwise it will be set to \c false. The value of


			




	280
	
	
		
  /// each arc will be set exactly once.


			




	
	283
	
		
  /// each arc/edge will be set exactly once.


			




	281
	284
	
		
  /// - It can also be an iteraror of an STL Container with


			




	282
	
	
		
  /// <tt>GR::Edge</tt> or <tt>GR::Arc</tt> as its


			




	
	285
	
		
  /// <tt>GR::Arc</tt> or <tt>GR::Edge</tt> as its


			




	283
	286
	
		
  /// <tt>value_type</tt>.  The algorithm copies the elements of the


			




	284
	287
	
		
  /// found tree into this sequence.  For example, if we know that the


			




	285
	288
	
		
  /// spanning tree of the graph \c g has say 53 arcs, then we can


			




	...
	...
	
		
@@ -290,13 +293,14 @@


			




	290
	293
	
		
  ///\endcode


			




	291
	294
	
		
  /// Or if we don't know in advance the size of the tree, we can


			




	292
	295
	
		
  /// write this.  


			




	293
	
	
		
  ///\code std::vector<Arc> tree;


			




	
	296
	
		
  ///\code


			




	
	297
	
		
  /// std::vector<Arc> tree;


			




	294
	298
	
		
  /// kruskal(g,cost,std::back_inserter(tree)); 


			




	295
	299
	
		
  ///\endcode


			




	296
	300
	
		
  ///


			




	297
	
	
		
  /// \return The total cost of the found tree.


			




	
	301
	
		
  /// \return The total cost of the found spanning tree.


			




	298
	302
	
		
  ///


			




	299
	
	
		
  /// \warning If kruskal runs on an be consistent of using the same


			




	
	303
	
		
  /// \warning If Kruskal runs on an be consistent of using the same


			




	300
	304
	
		
  /// Arc type for input and output.


			




	301
	305
	
		
  ///


			




	302
	306
	
		

			




        

    






    
    



    


    

     
    
0 comments (0 inline)