Index: lemon/kruskal.h
===================================================================
--- lemon/kruskal.h (revision 1555)
+++ lemon/kruskal.h (revision 1557)
@@ -37,4 +37,6 @@
///
///Kruskal's algorithm to compute a minimum cost tree.
+///
+///\todo The file still needs some clean-up.
namespace lemon {
@@ -46,4 +48,6 @@
/// This function runs Kruskal's algorithm to find a minimum cost tree.
+ /// Due to hard C++ hacking, it accepts various input and output types.
+ ///
/// \param g The graph the algorithm runs on.
/// It can be either \ref concept::StaticGraph "directed" or
@@ -52,21 +56,34 @@
/// undirected by disregarding the direction of the edges.
///
- /// \param in This object is used to describe the edge costs. It must
- /// be an STL compatible 'Forward Container'
+ /// \param in This object is used to describe the edge costs. It can be one
+ /// of the following choices.
+ /// - An STL compatible 'Forward Container'
/// with std::pair as its value_type,
- /// where X is the type of the costs. It must contain every edge in
- /// cost-ascending order.
- ///\par
- /// For the sake of simplicity, there is a helper class KruskalMapInput,
- /// which converts a
- /// simple edge map to an input of this form. Alternatively, you can use
- /// the function \ref kruskalEdgeMap to compute the minimum cost tree if
- /// the edge costs are given by an edge map.
- ///
- /// \retval out This must be a writable \c bool edge map.
+ /// where \c X is the type of the costs. The pairs indicates the edges along
+ /// with the assigned cost. They must be in a
+ /// cost-ascending order.
+ /// - Any readable Edge map. The values of the map indicate the edge costs.
+ ///
+ /// \retval out Here we also have a choise.
+ /// - Is can be a writable \c bool edge map.
/// After running the algorithm
/// this will contain the found minimum cost spanning tree: the value of an
/// edge will be set to \c true if it belongs to the tree, otherwise it will
/// be set to \c false. The value of each edge will be set exactly once.
+ /// - It can also be an iteraror of an STL Container with
+ /// GR::Edge as its value_type.
+ /// The algorithm copies the elements of the found tree into this sequence.
+ /// For example, if we know that the spanning tree of the graph \c g has
+ /// say 53 edges then
+ /// we can put its edges into a STL vector \c tree with a code like this.
+ /// \code
+ /// std::vector tree(53);
+ /// kruskal(g,cost,tree.begin());
+ /// \endcode
+ /// Or if we don't know in advance the size of the tree, we can write this.
+ /// \code
+ /// std::vector tree;
+ /// kruskal(g,cost,std::back_inserter(tree));
+ /// \endcode
///
/// \return The cost of the found tree.
@@ -78,8 +95,22 @@
/// (\ref kruskalEdgeMap() and \ref KruskalMapInput are kind enough to do so.)
+#ifdef DOXYGEN
template
typename IN::value_type::second_type
kruskal(GR const& g, IN const& in,
- OUT& out)
+ OUT& out)
+#else
+ template
+ typename IN::value_type::second_type
+ kruskal(GR const& g, IN const& in,
+ OUT& out,
+// typename IN::value_type::first_type = typename GR::Edge()
+// ,typename OUT::Key = OUT::Key()
+// //,typename OUT::Key = typename GR::Edge()
+ const typename IN::value_type::first_type * =
+ (const typename IN::value_type::first_type *)(0),
+ const typename OUT::Key * = (const typename OUT::Key *)(0)
+ )
+#endif
{
typedef typename IN::value_type::second_type EdgeCost;
@@ -105,4 +136,8 @@
}
+
+ /// @}
+
+
/* A work-around for running Kruskal with const-reference bool maps... */
@@ -123,4 +158,5 @@
const Map &m;
public:
+ typedef typename Map::Key Key;
typedef typename Map::Value Value;
@@ -134,5 +170,11 @@
inline
typename IN::value_type::second_type
- kruskal(GR const& g, IN const& edges, OUT const& out_map)
+ kruskal(GR const& g, IN const& edges, OUT const& out_map,
+// typename IN::value_type::first_type = typename GR::Edge(),
+// typename OUT::Key = GR::Edge()
+ const typename IN::value_type::first_type * =
+ (const typename IN::value_type::first_type *)(0),
+ const typename OUT::Key * = (const typename OUT::Key *)(0)
+ )
{
NonConstMapWr map_wr(out_map);
@@ -143,5 +185,5 @@
/// Kruskal's input source.
-
+
/// Kruskal's input source.
///
@@ -268,4 +310,5 @@
public:
+ typedef typename Iterator::value_type Key;
typedef bool Value;
@@ -287,34 +330,39 @@
/* ** ** Wrapper funtions ** ** */
-
-
- /// \brief Wrapper function to kruskal().
- /// Input is from an edge map, output is a plain bool map.
- ///
- /// Wrapper function to kruskal().
- /// Input is from an edge map, output is a plain bool map.
- ///
- ///\param g The type of the graph the algorithm runs on.
- ///\param in An edge map containing the cost of the edges.
- ///\par
- ///The cost type can be any type satisfying the
- ///STL 'LessThan Comparable'
- ///concept if it also has an operator+() implemented. (It is necessary for
- ///computing the total cost of the tree).
- ///
- /// \retval out This must be a writable \c bool edge map.
- /// After running the algorithm
- /// this will contain the found minimum cost spanning tree: the value of an
- /// edge will be set to \c true if it belongs to the tree, otherwise it will
- /// be set to \c false. The value of each edge will be set exactly once.
- ///
- /// \return The cost of the found tree.
+// \brief Wrapper function to kruskal().
+// Input is from an edge map, output is a plain bool map.
+//
+// Wrapper function to kruskal().
+// Input is from an edge map, output is a plain bool map.
+//
+// \param g The type of the graph the algorithm runs on.
+// \param in An edge map containing the cost of the edges.
+// \par
+// The cost type can be any type satisfying the
+// STL 'LessThan Comparable'
+// concept if it also has an operator+() implemented. (It is necessary for
+// computing the total cost of the tree).
+//
+// \retval out This must be a writable \c bool edge map.
+// After running the algorithm
+// this will contain the found minimum cost spanning tree: the value of an
+// edge will be set to \c true if it belongs to the tree, otherwise it will
+// be set to \c false. The value of each edge will be set exactly once.
+//
+// \return The cost of the found tree.
template
inline
typename IN::Value
- kruskalEdgeMap(GR const& g,
- IN const& in,
- RET &out) {
+ kruskal(GR const& g,
+ IN const& in,
+ RET &out,
+ // typename IN::Key = typename GR::Edge(),
+ //typename IN::Key = typename IN::Key (),
+ // typename RET::Key = typename GR::Edge()
+ const typename IN::Key * = (const typename IN::Key *)(0),
+ const typename RET::Key * = (const typename RET::Key *)(0)
+ )
+ {
return kruskal(g,
KruskalMapInput(g,in),
@@ -322,49 +370,54 @@
}
- /// \brief Wrapper function to kruskal().
- /// Input is from an edge map, output is an STL Sequence.
- ///
- /// Wrapper function to kruskal().
- /// Input is from an edge map, output is an STL Sequence.
- ///
- ///\param g The type of the graph the algorithm runs on.
- ///\param in An edge map containing the cost of the edges.
- ///\par
- ///The cost type can be any type satisfying the
- ///STL 'LessThan Comparable'
- ///concept if it also has an operator+() implemented. (It is necessary for
- ///computing the total cost of the tree).
- ///
- /// \retval out This must be an iteraror of an STL Container with
- /// GR::Edge as its value_type.
- /// The algorithm copies the elements of the found tree into this sequence.
- /// For example, if we know that the spanning tree of the graph \c g has
- /// say 53 edges then
- /// we can put its edges into a STL vector \c tree with a code like this.
- /// \code
- /// std::vector tree(53);
- /// kruskalEdgeMap_IteratorOut(g,cost,tree.begin());
- /// \endcode
- /// Or if we don't know in advance the size of the tree, we can write this.
- /// \code
- /// std::vector tree;
- /// kruskalEdgeMap_IteratorOut(g,cost,std::back_inserter(tree));
- /// \endcode
- ///
- /// \return The cost of the found tree.
- ///
- /// \bug its name does not follow the coding style.
+// \brief Wrapper function to kruskal().
+// Input is from an edge map, output is an STL Sequence.
+//
+// Wrapper function to kruskal().
+// Input is from an edge map, output is an STL Sequence.
+//
+// \param g The type of the graph the algorithm runs on.
+// \param in An edge map containing the cost of the edges.
+// \par
+// The cost type can be any type satisfying the
+// STL 'LessThan Comparable'
+// concept if it also has an operator+() implemented. (It is necessary for
+// computing the total cost of the tree).
+//
+// \retval out This must be an iteraror of an STL Container with
+// GR::Edge as its value_type.
+// The algorithm copies the elements of the found tree into this sequence.
+// For example, if we know that the spanning tree of the graph \c g has
+// say 53 edges then
+// we can put its edges into a STL vector \c tree with a code like this.
+// \code
+// std::vector tree(53);
+// kruskalEdgeMap_IteratorOut(g,cost,tree.begin());
+// \endcode
+// Or if we don't know in advance the size of the tree, we can write this.
+// \code
+// std::vector tree;
+// kruskalEdgeMap_IteratorOut(g,cost,std::back_inserter(tree));
+// \endcode
+//
+// \return The cost of the found tree.
+//
+// \bug its name does not follow the coding style.
template
inline
typename IN::Value
- kruskalEdgeMap_IteratorOut(const GR& g,
- const IN& in,
- RET out)
+ kruskal(const GR& g,
+ const IN& in,
+ RET out,
+ //,typename RET::value_type = typename GR::Edge()
+ //,typename RET::value_type = typename RET::value_type()
+ const typename RET::value_type * =
+ (const typename RET::value_type *)(0)
+ )
{
KruskalSequenceOutput _out(out);
return kruskal(g, KruskalMapInput(g, in), _out);
}
-
+
/// @}
Index: test/kruskal_test.cc
===================================================================
--- test/kruskal_test.cc (revision 1435)
+++ test/kruskal_test.cc (revision 1557)
@@ -33,7 +33,7 @@
concept::WriteMap w;
- kruskalEdgeMap(concept::StaticGraph(),
- concept::ReadMap(),
- w);
+ kruskal(concept::StaticGraph(),
+ concept::ReadMap(),
+ w);
}
@@ -73,8 +73,8 @@
//Test with const map.
- check(kruskalEdgeMap(G, ConstMap(2), tree_map)==10,
+ check(kruskal(G, ConstMap(2), tree_map)==10,
"Total cost should be 10");
//Test with a edge map (filled with uniform costs).
- check(kruskalEdgeMap(G, edge_cost_map, tree_map)==10,
+ check(kruskal(G, edge_cost_map, tree_map)==10,
"Total cost should be 10");
@@ -90,14 +90,21 @@
edge_cost_map.set(e10, -1);
- vector tree_edge_vec;
+ vector tree_edge_vec(5);
//Test with a edge map and inserter.
- check(kruskalEdgeMap_IteratorOut(G, edge_cost_map,
- back_inserter(tree_edge_vec))
+ check(kruskal(G, edge_cost_map,
+ tree_edge_vec.begin())
==-31,
"Total cost should be -31.");
-
+
tree_edge_vec.clear();
+ check(kruskal(G, edge_cost_map,
+ back_inserter(tree_edge_vec))
+ ==-31,
+ "Total cost should be -31.");
+
+ tree_edge_vec.clear();
+
//The above test could also be coded like this:
check(kruskal(G,