1.1 --- a/src/hugo/kruskal.h Sun Sep 19 13:39:25 2004 +0000
1.2 +++ b/src/hugo/kruskal.h Sun Sep 19 15:24:56 2004 +0000
1.3 @@ -81,8 +81,18 @@
1.4
1.5 /* A work-around for running Kruskal with const-reference bool maps... */
1.6
1.7 - ///\bug What is this? Or why doesn't it work?
1.8 + /// Helper class for calling kruskal with "constant" output map.
1.9 +
1.10 + /// Helper class for calling kruskal with output maps constructed
1.11 + /// on-the-fly.
1.12 ///
1.13 + /// A typical examle is the following call:
1.14 + /// <tt>kruskal(G, some_input, makeSequenceOutput(iterator))</tt>.
1.15 + /// Here, the third argument is a temporary object (which wraps around an
1.16 + /// iterator with a writable bool map interface), and thus by rules of C++
1.17 + /// is a \c const object. To enable call like this exist this class and
1.18 + /// the prototype of the \ref kruskal() function with <tt>const& OUT</tt>
1.19 + /// third argument.
1.20 template<class Map>
1.21 class NonConstMapWr {
1.22 const Map &m;
1.23 @@ -97,9 +107,8 @@
1.24
1.25 template <class GR, class IN, class OUT>
1.26 inline
1.27 - typename IN::ValueType
1.28 - kruskal(GR const& G, IN const& edges,
1.29 - OUT const& out_map)
1.30 + typename IN::value_type::second_type
1.31 + kruskal(GR const& G, IN const& edges, OUT const& out_map)
1.32 {
1.33 NonConstMapWr<OUT> map_wr(out_map);
1.34 return kruskal(G, edges, map_wr);
1.35 @@ -151,8 +160,7 @@
1.36 KruskalMapInput(GR const& G, Map const& m) {
1.37 typedef typename GR::EdgeIt EdgeIt;
1.38
1.39 - this->clear();
1.40 - for(EdgeIt e(G);e!=INVALID;++e) push_back(make_pair(e, m[e]));
1.41 + for(EdgeIt e(G);e!=INVALID;++e) push_back(value_type(e, m[e]));
1.42 sort();
1.43 }
1.44 };
1.45 @@ -184,24 +192,44 @@
1.46 }
1.47
1.48
1.49 - /* ** ** Output-objects: simple writable bool maps** ** */
1.50 +
1.51 + /* ** ** Output-objects: simple writable bool maps ** ** */
1.52
1.53 +
1.54 +
1.55 /// A writable bool-map that makes a sequence of "true" keys
1.56
1.57 /// A writable bool-map that creates a sequence out of keys that receives
1.58 /// the value "true".
1.59 + ///
1.60 + /// \sa makeKruskalSequenceOutput()
1.61 + ///
1.62 + /// Very often, when looking for a min cost spanning tree, we want as
1.63 + /// output a container containing the edges of the found tree. For this
1.64 + /// purpose exist this class that wraps around an STL iterator with a
1.65 + /// writable bool map interface. When a key gets value "true" this key
1.66 + /// is added to sequence pointed by the iterator.
1.67 + ///
1.68 + /// A typical usage:
1.69 + /// \code
1.70 + /// std::vector<Graph::Edge> v;
1.71 + /// kruskal(g, input, makeKruskalSequenceOutput(back_inserter(v)));
1.72 + /// \endcode
1.73 + ///
1.74 + /// For the most common case, when the input is given by a simple edge
1.75 + /// map and the output is a sequence of the tree edges, a special
1.76 + /// wrapper function exists: \ref kruskalEdgeMap_IteratorOut().
1.77 + ///
1.78 /// \warning Not a regular property map, as it doesn't know its KeyType
1.79 - /// \bug Missing documentation.
1.80 - /// \todo This class may be of wider usage, therefore it could move to
1.81 - /// <tt>maps.h</tt>
1.82 +
1.83 template<class Iterator>
1.84 - class SequenceOutput {
1.85 + class KruskalSequenceOutput {
1.86 mutable Iterator it;
1.87
1.88 public:
1.89 typedef bool ValueType;
1.90
1.91 - SequenceOutput(Iterator const &_it) : it(_it) {}
1.92 + KruskalSequenceOutput(Iterator const &_it) : it(_it) {}
1.93
1.94 template<typename KeyType>
1.95 void set(KeyType const& k, bool v) const { if(v) {*it=k; ++it;} }
1.96 @@ -209,14 +237,17 @@
1.97
1.98 template<class Iterator>
1.99 inline
1.100 - SequenceOutput<Iterator>
1.101 - makeSequenceOutput(Iterator it) {
1.102 - return SequenceOutput<Iterator>(it);
1.103 + KruskalSequenceOutput<Iterator>
1.104 + makeKruskalSequenceOutput(Iterator it) {
1.105 + return KruskalSequenceOutput<Iterator>(it);
1.106 }
1.107
1.108 +
1.109 +
1.110 /* ** ** Wrapper funtions ** ** */
1.111
1.112
1.113 +
1.114 /// \brief Wrapper function to kruskal().
1.115 /// Input is from an edge map, output is a plain bool map.
1.116 ///
1.117 @@ -239,7 +270,6 @@
1.118 ///
1.119 /// \return The cost of the found tree.
1.120
1.121 -
1.122 template <class GR, class IN, class RET>
1.123 inline
1.124 typename IN::ValueType
1.125 @@ -284,6 +314,7 @@
1.126 /// \return The cost of the found tree.
1.127 ///
1.128 /// \bug its name does not follow the coding style.
1.129 +
1.130 template <class GR, class IN, class RET>
1.131 inline
1.132 typename IN::ValueType
1.133 @@ -291,10 +322,8 @@
1.134 const IN& in,
1.135 RET out)
1.136 {
1.137 - SequenceOutput<RET> _out(out);
1.138 - return kruskal(G,
1.139 - KruskalMapInput<GR,IN>(G, in),
1.140 - _out);
1.141 + KruskalSequenceOutput<RET> _out(out);
1.142 + return kruskal(G, KruskalMapInput<GR,IN>(G, in), _out);
1.143 }
1.144
1.145 /// @}
2.1 --- a/src/test/kruskal_test.cc Sun Sep 19 13:39:25 2004 +0000
2.2 +++ b/src/test/kruskal_test.cc Sun Sep 19 15:24:56 2004 +0000
2.3 @@ -81,6 +81,15 @@
2.4 ==-31,
2.5 "Total cost should be -31.");
2.6
2.7 + tree_edge_vec.clear();
2.8 +
2.9 + //The above test could also be coded like this:
2.10 + check(kruskal(G,
2.11 + makeKruskalMapInput(G, edge_cost_map),
2.12 + makeKruskalSequenceOutput(back_inserter(tree_edge_vec)))
2.13 + ==-31,
2.14 + "Total cost should be -31.");
2.15 +
2.16 check(tree_edge_vec.size()==5,"The tree should have 5 edges.");
2.17
2.18 check(tree_edge_vec[0]==e1 &&