# Changeset 1557:3e8d928e283d in lemon-0.x

Ignore:
Timestamp:
07/14/05 14:23:15 (15 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2053
Message:

Each version of Kruskal is called the same ( kruskal(g,in,out) ) independently
from the input source and the output type.

Files:
2 edited

Unmodified
Removed
• ## lemon/kruskal.h

 r1555 /// ///Kruskal's algorithm to compute a minimum cost tree. /// ///\todo The file still needs some clean-up. namespace lemon { /// 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 /// 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. /// (\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; } /// @} /* A work-around for running Kruskal with const-reference bool maps... */ const Map &m; public: typedef typename Map::Key Key; typedef typename Map::Value Value; 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); /// Kruskal's input source. /// Kruskal's input source. /// public: typedef typename Iterator::value_type Key; typedef bool Value; /* ** ** 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), } /// \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); } /// @}
• ## test/kruskal_test.cc

 r1435 concept::WriteMap w; kruskalEdgeMap(concept::StaticGraph(), concept::ReadMap(), w); kruskal(concept::StaticGraph(), concept::ReadMap(), w); } //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(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,
Note: See TracChangeset for help on using the changeset viewer.