1.1 --- a/lemon/kruskal.h Wed Jul 13 20:02:29 2005 +0000
1.2 +++ b/lemon/kruskal.h Thu Jul 14 12:23:15 2005 +0000
1.3 @@ -36,6 +36,8 @@
1.4 ///\brief Kruskal's algorithm to compute a minimum cost tree
1.5 ///
1.6 ///Kruskal's algorithm to compute a minimum cost tree.
1.7 +///
1.8 +///\todo The file still needs some clean-up.
1.9
1.10 namespace lemon {
1.11
1.12 @@ -45,29 +47,44 @@
1.13 /// Kruskal's algorithm to find a minimum cost tree of a graph.
1.14
1.15 /// This function runs Kruskal's algorithm to find a minimum cost tree.
1.16 + /// Due to hard C++ hacking, it accepts various input and output types.
1.17 + ///
1.18 /// \param g The graph the algorithm runs on.
1.19 /// It can be either \ref concept::StaticGraph "directed" or
1.20 /// \ref concept::UndirStaticGraph "undirected".
1.21 /// If the graph is directed, the algorithm consider it to be
1.22 /// undirected by disregarding the direction of the edges.
1.23 ///
1.24 - /// \param in This object is used to describe the edge costs. It must
1.25 - /// be an STL compatible 'Forward Container'
1.26 + /// \param in This object is used to describe the edge costs. It can be one
1.27 + /// of the following choices.
1.28 + /// - An STL compatible 'Forward Container'
1.29 /// with <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>,
1.30 - /// where X is the type of the costs. It must contain every edge in
1.31 - /// cost-ascending order.
1.32 - ///\par
1.33 - /// For the sake of simplicity, there is a helper class KruskalMapInput,
1.34 - /// which converts a
1.35 - /// simple edge map to an input of this form. Alternatively, you can use
1.36 - /// the function \ref kruskalEdgeMap to compute the minimum cost tree if
1.37 - /// the edge costs are given by an edge map.
1.38 + /// where \c X is the type of the costs. The pairs indicates the edges along
1.39 + /// with the assigned cost. <em>They must be in a
1.40 + /// cost-ascending order.</em>
1.41 + /// - Any readable Edge map. The values of the map indicate the edge costs.
1.42 ///
1.43 - /// \retval out This must be a writable \c bool edge map.
1.44 + /// \retval out Here we also have a choise.
1.45 + /// - Is can be a writable \c bool edge map.
1.46 /// After running the algorithm
1.47 /// this will contain the found minimum cost spanning tree: the value of an
1.48 /// edge will be set to \c true if it belongs to the tree, otherwise it will
1.49 /// be set to \c false. The value of each edge will be set exactly once.
1.50 + /// - It can also be an iteraror of an STL Container with
1.51 + /// <tt>GR::Edge</tt> as its <tt>value_type</tt>.
1.52 + /// The algorithm copies the elements of the found tree into this sequence.
1.53 + /// For example, if we know that the spanning tree of the graph \c g has
1.54 + /// say 53 edges then
1.55 + /// we can put its edges into a STL vector \c tree with a code like this.
1.56 + /// \code
1.57 + /// std::vector<Edge> tree(53);
1.58 + /// kruskal(g,cost,tree.begin());
1.59 + /// \endcode
1.60 + /// Or if we don't know in advance the size of the tree, we can write this.
1.61 + /// \code
1.62 + /// std::vector<Edge> tree;
1.63 + /// kruskal(g,cost,std::back_inserter(tree));
1.64 + /// \endcode
1.65 ///
1.66 /// \return The cost of the found tree.
1.67 ///
1.68 @@ -77,10 +94,24 @@
1.69 /// <tt>Edge</tt>s belonging to a certain <tt>UndirEdge</tt>.
1.70 /// (\ref kruskalEdgeMap() and \ref KruskalMapInput are kind enough to do so.)
1.71
1.72 +#ifdef DOXYGEN
1.73 template <class GR, class IN, class OUT>
1.74 typename IN::value_type::second_type
1.75 kruskal(GR const& g, IN const& in,
1.76 - OUT& out)
1.77 + OUT& out)
1.78 +#else
1.79 + template <class GR, class IN, class OUT>
1.80 + typename IN::value_type::second_type
1.81 + kruskal(GR const& g, IN const& in,
1.82 + OUT& out,
1.83 +// typename IN::value_type::first_type = typename GR::Edge()
1.84 +// ,typename OUT::Key = OUT::Key()
1.85 +// //,typename OUT::Key = typename GR::Edge()
1.86 + const typename IN::value_type::first_type * =
1.87 + (const typename IN::value_type::first_type *)(0),
1.88 + const typename OUT::Key * = (const typename OUT::Key *)(0)
1.89 + )
1.90 +#endif
1.91 {
1.92 typedef typename IN::value_type::second_type EdgeCost;
1.93 typedef typename GR::template NodeMap<int> NodeIntMap;
1.94 @@ -104,6 +135,10 @@
1.95 return tot_cost;
1.96 }
1.97
1.98 +
1.99 + /// @}
1.100 +
1.101 +
1.102 /* A work-around for running Kruskal with const-reference bool maps... */
1.103
1.104 /// Helper class for calling kruskal with "constant" output map.
1.105 @@ -122,6 +157,7 @@
1.106 class NonConstMapWr {
1.107 const Map &m;
1.108 public:
1.109 + typedef typename Map::Key Key;
1.110 typedef typename Map::Value Value;
1.111
1.112 NonConstMapWr(const Map &_m) : m(_m) {}
1.113 @@ -133,7 +169,13 @@
1.114 template <class GR, class IN, class OUT>
1.115 inline
1.116 typename IN::value_type::second_type
1.117 - kruskal(GR const& g, IN const& edges, OUT const& out_map)
1.118 + kruskal(GR const& g, IN const& edges, OUT const& out_map,
1.119 +// typename IN::value_type::first_type = typename GR::Edge(),
1.120 +// typename OUT::Key = GR::Edge()
1.121 + const typename IN::value_type::first_type * =
1.122 + (const typename IN::value_type::first_type *)(0),
1.123 + const typename OUT::Key * = (const typename OUT::Key *)(0)
1.124 + )
1.125 {
1.126 NonConstMapWr<OUT> map_wr(out_map);
1.127 return kruskal(g, edges, map_wr);
1.128 @@ -142,7 +184,7 @@
1.129 /* ** ** Input-objects ** ** */
1.130
1.131 /// Kruskal's input source.
1.132 -
1.133 +
1.134 /// Kruskal's input source.
1.135 ///
1.136 /// In most cases you possibly want to use the \ref kruskalEdgeMap() instead.
1.137 @@ -267,6 +309,7 @@
1.138 mutable Iterator it;
1.139
1.140 public:
1.141 + typedef typename Iterator::value_type Key;
1.142 typedef bool Value;
1.143
1.144 KruskalSequenceOutput(Iterator const &_it) : it(_it) {}
1.145 @@ -286,86 +329,96 @@
1.146
1.147 /* ** ** Wrapper funtions ** ** */
1.148
1.149 -
1.150 -
1.151 - /// \brief Wrapper function to kruskal().
1.152 - /// Input is from an edge map, output is a plain bool map.
1.153 - ///
1.154 - /// Wrapper function to kruskal().
1.155 - /// Input is from an edge map, output is a plain bool map.
1.156 - ///
1.157 - ///\param g The type of the graph the algorithm runs on.
1.158 - ///\param in An edge map containing the cost of the edges.
1.159 - ///\par
1.160 - ///The cost type can be any type satisfying the
1.161 - ///STL 'LessThan Comparable'
1.162 - ///concept if it also has an operator+() implemented. (It is necessary for
1.163 - ///computing the total cost of the tree).
1.164 - ///
1.165 - /// \retval out This must be a writable \c bool edge map.
1.166 - /// After running the algorithm
1.167 - /// this will contain the found minimum cost spanning tree: the value of an
1.168 - /// edge will be set to \c true if it belongs to the tree, otherwise it will
1.169 - /// be set to \c false. The value of each edge will be set exactly once.
1.170 - ///
1.171 - /// \return The cost of the found tree.
1.172 +// \brief Wrapper function to kruskal().
1.173 +// Input is from an edge map, output is a plain bool map.
1.174 +//
1.175 +// Wrapper function to kruskal().
1.176 +// Input is from an edge map, output is a plain bool map.
1.177 +//
1.178 +// \param g The type of the graph the algorithm runs on.
1.179 +// \param in An edge map containing the cost of the edges.
1.180 +// \par
1.181 +// The cost type can be any type satisfying the
1.182 +// STL 'LessThan Comparable'
1.183 +// concept if it also has an operator+() implemented. (It is necessary for
1.184 +// computing the total cost of the tree).
1.185 +//
1.186 +// \retval out This must be a writable \c bool edge map.
1.187 +// After running the algorithm
1.188 +// this will contain the found minimum cost spanning tree: the value of an
1.189 +// edge will be set to \c true if it belongs to the tree, otherwise it will
1.190 +// be set to \c false. The value of each edge will be set exactly once.
1.191 +//
1.192 +// \return The cost of the found tree.
1.193
1.194 template <class GR, class IN, class RET>
1.195 inline
1.196 typename IN::Value
1.197 - kruskalEdgeMap(GR const& g,
1.198 - IN const& in,
1.199 - RET &out) {
1.200 + kruskal(GR const& g,
1.201 + IN const& in,
1.202 + RET &out,
1.203 + // typename IN::Key = typename GR::Edge(),
1.204 + //typename IN::Key = typename IN::Key (),
1.205 + // typename RET::Key = typename GR::Edge()
1.206 + const typename IN::Key * = (const typename IN::Key *)(0),
1.207 + const typename RET::Key * = (const typename RET::Key *)(0)
1.208 + )
1.209 + {
1.210 return kruskal(g,
1.211 KruskalMapInput<GR,IN>(g,in),
1.212 out);
1.213 }
1.214
1.215 - /// \brief Wrapper function to kruskal().
1.216 - /// Input is from an edge map, output is an STL Sequence.
1.217 - ///
1.218 - /// Wrapper function to kruskal().
1.219 - /// Input is from an edge map, output is an STL Sequence.
1.220 - ///
1.221 - ///\param g The type of the graph the algorithm runs on.
1.222 - ///\param in An edge map containing the cost of the edges.
1.223 - ///\par
1.224 - ///The cost type can be any type satisfying the
1.225 - ///STL 'LessThan Comparable'
1.226 - ///concept if it also has an operator+() implemented. (It is necessary for
1.227 - ///computing the total cost of the tree).
1.228 - ///
1.229 - /// \retval out This must be an iteraror of an STL Container with
1.230 - /// <tt>GR::Edge</tt> as its <tt>value_type</tt>.
1.231 - /// The algorithm copies the elements of the found tree into this sequence.
1.232 - /// For example, if we know that the spanning tree of the graph \c g has
1.233 - /// say 53 edges then
1.234 - /// we can put its edges into a STL vector \c tree with a code like this.
1.235 - /// \code
1.236 - /// std::vector<Edge> tree(53);
1.237 - /// kruskalEdgeMap_IteratorOut(g,cost,tree.begin());
1.238 - /// \endcode
1.239 - /// Or if we don't know in advance the size of the tree, we can write this.
1.240 - /// \code
1.241 - /// std::vector<Edge> tree;
1.242 - /// kruskalEdgeMap_IteratorOut(g,cost,std::back_inserter(tree));
1.243 - /// \endcode
1.244 - ///
1.245 - /// \return The cost of the found tree.
1.246 - ///
1.247 - /// \bug its name does not follow the coding style.
1.248 +// \brief Wrapper function to kruskal().
1.249 +// Input is from an edge map, output is an STL Sequence.
1.250 +//
1.251 +// Wrapper function to kruskal().
1.252 +// Input is from an edge map, output is an STL Sequence.
1.253 +//
1.254 +// \param g The type of the graph the algorithm runs on.
1.255 +// \param in An edge map containing the cost of the edges.
1.256 +// \par
1.257 +// The cost type can be any type satisfying the
1.258 +// STL 'LessThan Comparable'
1.259 +// concept if it also has an operator+() implemented. (It is necessary for
1.260 +// computing the total cost of the tree).
1.261 +//
1.262 +// \retval out This must be an iteraror of an STL Container with
1.263 +// <tt>GR::Edge</tt> as its <tt>value_type</tt>.
1.264 +// The algorithm copies the elements of the found tree into this sequence.
1.265 +// For example, if we know that the spanning tree of the graph \c g has
1.266 +// say 53 edges then
1.267 +// we can put its edges into a STL vector \c tree with a code like this.
1.268 +// \code
1.269 +// std::vector<Edge> tree(53);
1.270 +// kruskalEdgeMap_IteratorOut(g,cost,tree.begin());
1.271 +// \endcode
1.272 +// Or if we don't know in advance the size of the tree, we can write this.
1.273 +// \code
1.274 +// std::vector<Edge> tree;
1.275 +// kruskalEdgeMap_IteratorOut(g,cost,std::back_inserter(tree));
1.276 +// \endcode
1.277 +//
1.278 +// \return The cost of the found tree.
1.279 +//
1.280 +// \bug its name does not follow the coding style.
1.281
1.282 template <class GR, class IN, class RET>
1.283 inline
1.284 typename IN::Value
1.285 - kruskalEdgeMap_IteratorOut(const GR& g,
1.286 - const IN& in,
1.287 - RET out)
1.288 + kruskal(const GR& g,
1.289 + const IN& in,
1.290 + RET out,
1.291 + //,typename RET::value_type = typename GR::Edge()
1.292 + //,typename RET::value_type = typename RET::value_type()
1.293 + const typename RET::value_type * =
1.294 + (const typename RET::value_type *)(0)
1.295 + )
1.296 {
1.297 KruskalSequenceOutput<RET> _out(out);
1.298 return kruskal(g, KruskalMapInput<GR,IN>(g, in), _out);
1.299 }
1.300 -
1.301 +
1.302 /// @}
1.303
1.304 } //namespace lemon
2.1 --- a/test/kruskal_test.cc Wed Jul 13 20:02:29 2005 +0000
2.2 +++ b/test/kruskal_test.cc Thu Jul 14 12:23:15 2005 +0000
2.3 @@ -32,9 +32,9 @@
2.4 {
2.5 concept::WriteMap<concept::StaticGraph::Edge,bool> w;
2.6
2.7 - kruskalEdgeMap(concept::StaticGraph(),
2.8 - concept::ReadMap<concept::StaticGraph::Edge,int>(),
2.9 - w);
2.10 + kruskal(concept::StaticGraph(),
2.11 + concept::ReadMap<concept::StaticGraph::Edge,int>(),
2.12 + w);
2.13 }
2.14
2.15 int main() {
2.16 @@ -72,10 +72,10 @@
2.17
2.18
2.19 //Test with const map.
2.20 - check(kruskalEdgeMap(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10,
2.21 + check(kruskal(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10,
2.22 "Total cost should be 10");
2.23 //Test with a edge map (filled with uniform costs).
2.24 - check(kruskalEdgeMap(G, edge_cost_map, tree_map)==10,
2.25 + check(kruskal(G, edge_cost_map, tree_map)==10,
2.26 "Total cost should be 10");
2.27
2.28 edge_cost_map.set(e1, -10);
2.29 @@ -89,16 +89,23 @@
2.30 edge_cost_map.set(e9, -2);
2.31 edge_cost_map.set(e10, -1);
2.32
2.33 - vector<Edge> tree_edge_vec;
2.34 + vector<Edge> tree_edge_vec(5);
2.35
2.36 //Test with a edge map and inserter.
2.37 - check(kruskalEdgeMap_IteratorOut(G, edge_cost_map,
2.38 - back_inserter(tree_edge_vec))
2.39 + check(kruskal(G, edge_cost_map,
2.40 + tree_edge_vec.begin())
2.41 ==-31,
2.42 "Total cost should be -31.");
2.43 -
2.44 +
2.45 tree_edge_vec.clear();
2.46
2.47 + check(kruskal(G, edge_cost_map,
2.48 + back_inserter(tree_edge_vec))
2.49 + ==-31,
2.50 + "Total cost should be -31.");
2.51 +
2.52 + tree_edge_vec.clear();
2.53 +
2.54 //The above test could also be coded like this:
2.55 check(kruskal(G,
2.56 makeKruskalMapInput(G, edge_cost_map),