1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/hugo/kruskal.h Mon Sep 06 17:12:00 2004 +0000
1.3 @@ -0,0 +1,304 @@
1.4 +// -*- c++ -*- //
1.5 +#ifndef HUGO_KRUSKAL_H
1.6 +#define HUGO_KRUSKAL_H
1.7 +
1.8 +#include <algorithm>
1.9 +#include <hugo/unionfind.h>
1.10 +
1.11 +/**
1.12 +@defgroup spantree Minimum Cost Spanning Tree Algorithms
1.13 +@ingroup galgs
1.14 +\brief This group containes the algorithms for finding a minimum cost spanning
1.15 +tree in a graph
1.16 +
1.17 +This group containes the algorithms for finding a minimum cost spanning
1.18 +tree in a graph
1.19 +*/
1.20 +
1.21 +///\ingroup spantree
1.22 +///\file
1.23 +///\brief Kruskal's algorithm to compute a minimum cost tree
1.24 +///
1.25 +///Kruskal's algorithm to compute a minimum cost tree.
1.26 +
1.27 +namespace hugo {
1.28 +
1.29 + /// \addtogroup spantree
1.30 + /// @{
1.31 +
1.32 + /// Kruskal's algorithm to find a minimum cost tree of a graph.
1.33 +
1.34 + /// This function runs Kruskal's algorithm to find a minimum cost tree.
1.35 + /// \param G The graph the algorithm runs on. The algorithm considers the
1.36 + /// graph to be undirected, the direction of the edges are not used.
1.37 + ///
1.38 + /// \param in This object is used to describe the edge costs. It must
1.39 + /// be an STL compatible 'Forward Container'
1.40 + /// with <tt>std::pair<Graph::Edge,X></tt> as its <tt>value_type</tt>,
1.41 + /// where X is the type of the costs. It must contain every edge in
1.42 + /// cost-ascending order.
1.43 + ///\par
1.44 + /// For the sake of simplicity, there is a helper class KruskalMapInput,
1.45 + /// which converts a
1.46 + /// simple edge map to an input of this form. Alternatively, you can use
1.47 + /// the function \ref kruskalEdgeMap to compute the minimum cost tree if
1.48 + /// the edge costs are given by an edge map.
1.49 + ///
1.50 + /// \retval out This must be a writable \c bool edge map.
1.51 + /// After running the algorithm
1.52 + /// this will contain the found minimum cost spanning tree: the value of an
1.53 + /// edge will be set to \c true if it belongs to the tree, otherwise it will
1.54 + /// be set to \c false. The value of each edge will be set exactly once.
1.55 + ///
1.56 + /// \return The cost of the found tree.
1.57 +
1.58 + template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
1.59 + typename InputEdgeOrder::value_type::second_type
1.60 + kruskal(Graph const& G, InputEdgeOrder const& in,
1.61 + OutBoolMap& out)
1.62 + {
1.63 + typedef typename InputEdgeOrder::value_type::second_type EdgeCost;
1.64 + typedef typename Graph::template NodeMap<int> NodeIntMap;
1.65 + typedef typename Graph::Node Node;
1.66 +
1.67 + NodeIntMap comp(G, -1);
1.68 + UnionFind<Node,NodeIntMap> uf(comp);
1.69 +
1.70 + EdgeCost tot_cost = 0;
1.71 + for (typename InputEdgeOrder::const_iterator p = in.begin();
1.72 + p!=in.end(); ++p ) {
1.73 + if ( uf.join(G.head((*p).first),
1.74 + G.tail((*p).first)) ) {
1.75 + out.set((*p).first, true);
1.76 + tot_cost += (*p).second;
1.77 + }
1.78 + else {
1.79 + out.set((*p).first, false);
1.80 + }
1.81 + }
1.82 + return tot_cost;
1.83 + }
1.84 +
1.85 + /* A work-around for running Kruskal with const-reference bool maps... */
1.86 +
1.87 + ///\bug What is this? Or why doesn't it works?
1.88 + ///
1.89 + template<typename Map>
1.90 + class NonConstMapWr {
1.91 + const Map &m;
1.92 + public:
1.93 + typedef typename Map::ValueType ValueType;
1.94 +
1.95 + NonConstMapWr(const Map &_m) : m(_m) {}
1.96 +
1.97 + template<typename KeyType>
1.98 + void set(KeyType const& k, ValueType const &v) const { m.set(k,v); }
1.99 + };
1.100 +
1.101 + template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
1.102 + inline
1.103 + typename InputEdgeOrder::ValueType
1.104 + kruskal(Graph const& G, InputEdgeOrder const& edges,
1.105 + OutBoolMap const& out_map)
1.106 + {
1.107 + NonConstMapWr<OutBoolMap> map_wr(out_map);
1.108 + return kruskal(G, edges, map_wr);
1.109 + }
1.110 +
1.111 + /* ** ** Input-objects ** ** */
1.112 +
1.113 + /// Kruskal input source.
1.114 +
1.115 + /// Kruskal input source.
1.116 + ///
1.117 + /// In most cases you possibly want to use the \ref kruskalEdgeMap() instead.
1.118 + ///
1.119 + /// \sa makeKruskalMapInput()
1.120 + ///
1.121 + ///\param Graph The type of the graph the algorithm runs on.
1.122 + ///\param Map An edge map containing the cost of the edges.
1.123 + ///\par
1.124 + ///The cost type can be any type satisfying
1.125 + ///the STL 'LessThan comparable'
1.126 + ///concept if it also has an operator+() implemented. (It is necessary for
1.127 + ///computing the total cost of the tree).
1.128 + ///
1.129 + template<typename Graph, typename Map>
1.130 + class KruskalMapInput
1.131 + : public std::vector< std::pair<typename Graph::Edge,
1.132 + typename Map::ValueType> > {
1.133 +
1.134 + public:
1.135 + typedef std::vector< std::pair<typename Graph::Edge,
1.136 + typename Map::ValueType> > Parent;
1.137 + typedef typename Parent::value_type value_type;
1.138 +
1.139 + private:
1.140 + class comparePair {
1.141 + public:
1.142 + bool operator()(const value_type& a,
1.143 + const value_type& b) {
1.144 + return a.second < b.second;
1.145 + }
1.146 + };
1.147 +
1.148 + public:
1.149 +
1.150 + void sort() {
1.151 + std::sort(this->begin(), this->end(), comparePair());
1.152 + }
1.153 +
1.154 + KruskalMapInput(Graph const& G, Map const& m) {
1.155 + typedef typename Graph::EdgeIt EdgeIt;
1.156 +
1.157 + this->clear();
1.158 + for(EdgeIt e(G);e!=INVALID;++e) push_back(make_pair(e, m[e]));
1.159 + sort();
1.160 + }
1.161 + };
1.162 +
1.163 + /// Creates a KruskalMapInput object for \ref kruskal()
1.164 +
1.165 + /// It makes is easier to use
1.166 + /// \ref KruskalMapInput by making it unnecessary
1.167 + /// to explicitly give the type of the parameters.
1.168 + ///
1.169 + /// In most cases you possibly
1.170 + /// want to use the function kruskalEdgeMap() instead.
1.171 + ///
1.172 + ///\param G The type of the graph the algorithm runs on.
1.173 + ///\param m An edge map containing the cost of the edges.
1.174 + ///\par
1.175 + ///The cost type can be any type satisfying the
1.176 + ///STL 'LessThan Comparable'
1.177 + ///concept if it also has an operator+() implemented. (It is necessary for
1.178 + ///computing the total cost of the tree).
1.179 + ///
1.180 + ///\return An appropriate input source for \ref kruskal().
1.181 + ///
1.182 + template<typename Graph, typename Map>
1.183 + inline
1.184 + KruskalMapInput<Graph,Map> makeKruskalMapInput(const Graph &G,const Map &m)
1.185 + {
1.186 + return KruskalMapInput<Graph,Map>(G,m);
1.187 + }
1.188 +
1.189 +
1.190 + /* ** ** Output-objects: simple writable bool maps** ** */
1.191 +
1.192 + /// A writable bool-map that makes a sequence of "true" keys
1.193 +
1.194 + /// A writable bool-map that creates a sequence out of keys that receives
1.195 + /// the value "true".
1.196 + /// \warning Not a regular property map, as it doesn't know its KeyType
1.197 + /// \bug Missing documentation.
1.198 + /// \todo This class may be of wider usage, therefore it could move to
1.199 + /// <tt>maps.h</tt>
1.200 + template<typename Iterator>
1.201 + class SequenceOutput {
1.202 + mutable Iterator it;
1.203 +
1.204 + public:
1.205 + typedef bool ValueType;
1.206 +
1.207 + SequenceOutput(Iterator const &_it) : it(_it) {}
1.208 +
1.209 + template<typename KeyType>
1.210 + void set(KeyType const& k, bool v) const { if(v) {*it=k; ++it;} }
1.211 + };
1.212 +
1.213 + template<typename Iterator>
1.214 + inline
1.215 + SequenceOutput<Iterator>
1.216 + makeSequenceOutput(Iterator it) {
1.217 + return SequenceOutput<Iterator>(it);
1.218 + }
1.219 +
1.220 + /* ** ** Wrapper funtions ** ** */
1.221 +
1.222 +
1.223 + /// \brief Wrapper function to kruskal().
1.224 + /// Input is from an edge map, output is a plain bool map.
1.225 + ///
1.226 + /// Wrapper function to kruskal().
1.227 + /// Input is from an edge map, output is a plain bool map.
1.228 + ///
1.229 + ///\param G The type of the graph the algorithm runs on.
1.230 + ///\param in An edge map containing the cost of the edges.
1.231 + ///\par
1.232 + ///The cost type can be any type satisfying the
1.233 + ///STL 'LessThan Comparable'
1.234 + ///concept if it also has an operator+() implemented. (It is necessary for
1.235 + ///computing the total cost of the tree).
1.236 + ///
1.237 + /// \retval out This must be a writable \c bool edge map.
1.238 + /// After running the algorithm
1.239 + /// this will contain the found minimum cost spanning tree: the value of an
1.240 + /// edge will be set to \c true if it belongs to the tree, otherwise it will
1.241 + /// be set to \c false. The value of each edge will be set exactly once.
1.242 + ///
1.243 + /// \return The cost of the found tree.
1.244 +
1.245 +
1.246 + template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
1.247 + inline
1.248 + typename EdgeCostMap::ValueType
1.249 + kruskalEdgeMap(Graph const& G,
1.250 + EdgeCostMap const& in,
1.251 + RetEdgeBoolMap &out) {
1.252 + return kruskal(G,
1.253 + KruskalMapInput<Graph,EdgeCostMap>(G,in),
1.254 + out);
1.255 + }
1.256 +
1.257 + /// \brief Wrapper function to kruskal().
1.258 + /// Input is from an edge map, output is an STL Sequence.
1.259 + ///
1.260 + /// Wrapper function to kruskal().
1.261 + /// Input is from an edge map, output is an STL Sequence.
1.262 + ///
1.263 + ///\param G The type of the graph the algorithm runs on.
1.264 + ///\param in An edge map containing the cost of the edges.
1.265 + ///\par
1.266 + ///The cost type can be any type satisfying the
1.267 + ///STL 'LessThan Comparable'
1.268 + ///concept if it also has an operator+() implemented. (It is necessary for
1.269 + ///computing the total cost of the tree).
1.270 + ///
1.271 + /// \retval out This must be an iteraror of an STL Container with
1.272 + /// <tt>Graph::Edge</tt> as its <tt>value_type</tt>.
1.273 + /// The algorithm copies the elements of the found tree into this sequence.
1.274 + /// For example, if we know that the spanning tree of the graph \c G has
1.275 + /// say 53 edges then
1.276 + /// we can put its edges into a vector \c tree with a code like this.
1.277 + /// \code
1.278 + /// std::vector<Edge> tree(53);
1.279 + /// kruskalEdgeMap_IteratorOut(G,cost,tree.begin());
1.280 + /// \endcode
1.281 + /// Or if we don't know in advance the size of the tree, we can write this.
1.282 + /// \code
1.283 + /// std::vector<Edge> tree;
1.284 + /// kruskalEdgeMap_IteratorOut(G,cost,std::back_inserter(tree));
1.285 + /// \endcode
1.286 + ///
1.287 + /// \return The cost of the found tree.
1.288 + ///
1.289 + /// \bug its name does not follow the coding style.
1.290 + template <typename Graph, typename EdgeCostMap, typename RetIterator>
1.291 + inline
1.292 + typename EdgeCostMap::ValueType
1.293 + kruskalEdgeMap_IteratorOut(const Graph& G,
1.294 + const EdgeCostMap& in,
1.295 + RetIterator out)
1.296 + {
1.297 + SequenceOutput<RetIterator> _out(out);
1.298 + return kruskal(G,
1.299 + KruskalMapInput<Graph, EdgeCostMap>(G, in),
1.300 + _out);
1.301 + }
1.302 +
1.303 + /// @}
1.304 +
1.305 +} //namespace hugo
1.306 +
1.307 +#endif //HUGO_KRUSKAL_H