# HG changeset patch
# User alpar
# Date 1121343795 0
# Node ID 3e8d928e283d21696638771ede9b879e39594561
# Parent caf0f91e16a7e32472850a8ea07ec0c82695eb99
Each version of Kruskal is called the same ( kruskal(g,in,out) ) independently
from the input source and the output type.
diff -r caf0f91e16a7 -r 3e8d928e283d lemon/kruskal.h
--- a/lemon/kruskal.h Wed Jul 13 20:02:29 2005 +0000
+++ b/lemon/kruskal.h Thu Jul 14 12:23:15 2005 +0000
@@ -36,6 +36,8 @@
///\brief Kruskal's algorithm to compute a minimum cost tree
///
///Kruskal's algorithm to compute a minimum cost tree.
+///
+///\todo The file still needs some clean-up.
namespace lemon {
@@ -45,29 +47,44 @@
/// Kruskal's algorithm to find a minimum cost tree of a graph.
/// 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
/// \ref concept::UndirStaticGraph "undirected".
/// If the graph is directed, the algorithm consider it to be
/// 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.
+ /// 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 This must be a writable \c bool edge map.
+ /// \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.
///
@@ -77,10 +94,24 @@
/// Edges belonging to a certain UndirEdge.
/// (\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;
typedef typename GR::template NodeMap NodeIntMap;
@@ -104,6 +135,10 @@
return tot_cost;
}
+
+ /// @}
+
+
/* A work-around for running Kruskal with const-reference bool maps... */
/// Helper class for calling kruskal with "constant" output map.
@@ -122,6 +157,7 @@
class NonConstMapWr {
const Map &m;
public:
+ typedef typename Map::Key Key;
typedef typename Map::Value Value;
NonConstMapWr(const Map &_m) : m(_m) {}
@@ -133,7 +169,13 @@
template
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);
return kruskal(g, edges, map_wr);
@@ -142,7 +184,7 @@
/* ** ** Input-objects ** ** */
/// Kruskal's input source.
-
+
/// Kruskal's input source.
///
/// In most cases you possibly want to use the \ref kruskalEdgeMap() instead.
@@ -267,6 +309,7 @@
mutable Iterator it;
public:
+ typedef typename Iterator::value_type Key;
typedef bool Value;
KruskalSequenceOutput(Iterator const &_it) : it(_it) {}
@@ -286,86 +329,96 @@
/* ** ** 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),
out);
}
- /// \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);
}
-
+
/// @}
} //namespace lemon
diff -r caf0f91e16a7 -r 3e8d928e283d test/kruskal_test.cc
--- a/test/kruskal_test.cc Wed Jul 13 20:02:29 2005 +0000
+++ b/test/kruskal_test.cc Thu Jul 14 12:23:15 2005 +0000
@@ -32,9 +32,9 @@
{
concept::WriteMap w;
- kruskalEdgeMap(concept::StaticGraph(),
- concept::ReadMap(),
- w);
+ kruskal(concept::StaticGraph(),
+ concept::ReadMap(),
+ w);
}
int main() {
@@ -72,10 +72,10 @@
//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");
edge_cost_map.set(e1, -10);
@@ -89,16 +89,23 @@
edge_cost_map.set(e9, -2);
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,
makeKruskalMapInput(G, edge_cost_map),