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
Show white space 12 line context
... ... 
@@ -29,15 +29,15 @@
29 29 

			




	30
	30
	
		
#include <lemon/bits/utility.h>


			




	31
	31
	
		
#include <lemon/bits/traits.h>


			




	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 {


			




	41
	41
	
		

			




	42
	42
	
		
  namespace _kruskal_bits {


			




	43
	43
	
		

			




	...
	...
	
		
@@ -248,58 +248,62 @@


			




	248
	248
	
		
    };


			




	249
	249
	
		

			




	250
	250
	
		
  }


			




	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.


			




	260
	262
	
		
  /// It can be either \ref concepts::Digraph "directed" or 


			




	261
	263
	
		
  /// \ref concepts::Graph "undirected".


			




	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


			




	286
	289
	
		
  /// put its arcs into an STL vector \c tree with a code like this.


			




	287
	290
	
		
  ///\code


			




	288
	291
	
		
  /// std::vector<Arc> tree(53);


			




	289
	292
	
		
  /// kruskal(g,cost,tree.begin());


			




	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
	
		

			




	303
	307
	
		
#ifdef DOXYGEN


			




	304
	308
	
		
  template <class Graph, class In, class Out>


			




	305
	309
	
		
  Value kruskal(GR const& g, const In& in, Out& out)


			




        

    






    
    



    


    

     
    
0 comments (0 inline)