equal
deleted
inserted
replaced
72 /// be set to \c false. The value of each edge will be set exactly once. |
72 /// be set to \c false. The value of each edge will be set exactly once. |
73 /// - It can also be an iteraror of an STL Container with |
73 /// - It can also be an iteraror of an STL Container with |
74 /// <tt>GR::Edge</tt> as its <tt>value_type</tt>. |
74 /// <tt>GR::Edge</tt> as its <tt>value_type</tt>. |
75 /// The algorithm copies the elements of the found tree into this sequence. |
75 /// The algorithm copies the elements of the found tree into this sequence. |
76 /// For example, if we know that the spanning tree of the graph \c g has |
76 /// For example, if we know that the spanning tree of the graph \c g has |
77 /// say 53 edges then |
77 /// say 53 edges, then |
78 /// we can put its edges into a STL vector \c tree with a code like this. |
78 /// we can put its edges into a STL vector \c tree with a code like this. |
79 /// \code |
79 /// \code |
80 /// std::vector<Edge> tree(53); |
80 /// std::vector<Edge> tree(53); |
81 /// kruskal(g,cost,tree.begin()); |
81 /// kruskal(g,cost,tree.begin()); |
82 /// \endcode |
82 /// \endcode |
85 /// std::vector<Edge> tree; |
85 /// std::vector<Edge> tree; |
86 /// kruskal(g,cost,std::back_inserter(tree)); |
86 /// kruskal(g,cost,std::back_inserter(tree)); |
87 /// \endcode |
87 /// \endcode |
88 /// |
88 /// |
89 /// \return The cost of the found tree. |
89 /// \return The cost of the found tree. |
|
90 /// |
|
91 /// \warning If kruskal is run on an \ref undirected graph, be sure that the |
|
92 /// map storing the tree is also undirected |
|
93 /// (e.g. UndirListGraph::UndirEdgeMap<bool>, otherwise the values of the |
|
94 /// half of the edges will not be set. |
90 /// |
95 /// |
91 /// \todo Discuss the case of undirected graphs: In this case the algorithm |
96 /// \todo Discuss the case of undirected graphs: In this case the algorithm |
92 /// also require <tt>Edge</tt>s instead of <tt>UndirEdge</tt>s, as some |
97 /// also require <tt>Edge</tt>s instead of <tt>UndirEdge</tt>s, as some |
93 /// people would expect. So, one should be careful not to add both of the |
98 /// people would expect. So, one should be careful not to add both of the |
94 /// <tt>Edge</tt>s belonging to a certain <tt>UndirEdge</tt>. |
99 /// <tt>Edge</tt>s belonging to a certain <tt>UndirEdge</tt>. |
385 // |
390 // |
386 // \retval out This must be an iteraror of an STL Container with |
391 // \retval out This must be an iteraror of an STL Container with |
387 // <tt>GR::Edge</tt> as its <tt>value_type</tt>. |
392 // <tt>GR::Edge</tt> as its <tt>value_type</tt>. |
388 // The algorithm copies the elements of the found tree into this sequence. |
393 // The algorithm copies the elements of the found tree into this sequence. |
389 // For example, if we know that the spanning tree of the graph \c g has |
394 // For example, if we know that the spanning tree of the graph \c g has |
390 // say 53 edges then |
395 // say 53 edges, then |
391 // we can put its edges into a STL vector \c tree with a code like this. |
396 // we can put its edges into a STL vector \c tree with a code like this. |
392 // \code |
397 // \code |
393 // std::vector<Edge> tree(53); |
398 // std::vector<Edge> tree(53); |
394 // kruskal(g,cost,tree.begin()); |
399 // kruskal(g,cost,tree.begin()); |
395 // \endcode |
400 // \endcode |