1.1 --- a/lemon/kruskal.h Thu Apr 19 15:09:08 2007 +0000
1.2 +++ b/lemon/kruskal.h Thu Apr 19 15:11:58 2007 +0000
1.3 @@ -22,6 +22,11 @@
1.4 #include <algorithm>
1.5 #include <vector>
1.6 #include <lemon/unionfind.h>
1.7 +#include <lemon/graph_utils.h>
1.8 +#include <lemon/maps.h>
1.9 +
1.10 +#include <lemon/radix_sort.h>
1.11 +
1.12 #include <lemon/bits/utility.h>
1.13 #include <lemon/bits/traits.h>
1.14
1.15 @@ -34,11 +39,567 @@
1.16
1.17 namespace lemon {
1.18
1.19 - /// \addtogroup spantree
1.20 - /// @{
1.21 + namespace _kruskal_bits {
1.22
1.23 - /// Kruskal's algorithm to find a minimum cost tree of a graph.
1.24 + template <typename Map, typename Comp>
1.25 + struct MappedComp {
1.26
1.27 + typedef typename Map::Key Key;
1.28 +
1.29 + const Map& map;
1.30 + Comp comp;
1.31 +
1.32 + MappedComp(const Map& _map)
1.33 + : map(_map), comp() {}
1.34 +
1.35 + bool operator()(const Key& left, const Key& right) {
1.36 + return comp(map[left], map[right]);
1.37 + }
1.38 +
1.39 + };
1.40 +
1.41 + }
1.42 +
1.43 + /// \ingroup spantree
1.44 + ///
1.45 + /// \brief Default traits class of Kruskal class.
1.46 + ///
1.47 + /// Default traits class of Kruskal class.
1.48 + /// \param _UGraph Undirected graph type.
1.49 + /// \param _CostMap Type of cost map.
1.50 + template <typename _UGraph, typename _CostMap>
1.51 + struct KruskalDefaultTraits{
1.52 +
1.53 + /// \brief The graph type the algorithm runs on.
1.54 + typedef _UGraph UGraph;
1.55 +
1.56 + /// \brief The type of the map that stores the edge costs.
1.57 + ///
1.58 + /// The type of the map that stores the edge costs.
1.59 + /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
1.60 + typedef _CostMap CostMap;
1.61 +
1.62 + /// \brief The type of the cost of the edges.
1.63 + typedef typename _CostMap::Value Value;
1.64 +
1.65 + /// \brief The type of the map that stores whether an edge is in the
1.66 + /// spanning tree or not.
1.67 + ///
1.68 + /// The type of the map that stores whether an edge is in the
1.69 + /// spanning tree or not.
1.70 + typedef typename _UGraph::template UEdgeMap<bool> TreeMap;
1.71 +
1.72 + /// \brief Instantiates a TreeMap.
1.73 + ///
1.74 + /// This function instantiates a \ref TreeMap.
1.75 + ///
1.76 + /// The first parameter is the graph, to which
1.77 + /// we would like to define the \ref TreeMap
1.78 + static TreeMap *createTreeMap(const _UGraph& graph){
1.79 + return new TreeMap(graph);
1.80 + }
1.81 +
1.82 + template <typename Iterator>
1.83 + static void sort(Iterator begin, Iterator end, const CostMap& cost) {
1.84 + _kruskal_bits::MappedComp<CostMap, std::less<Value> > comp(cost);
1.85 + std::sort(begin, end, comp);
1.86 + }
1.87 +
1.88 + };
1.89 +
1.90 + /// \brief Kruskal's algorithm to find a minimum cost tree of a graph.
1.91 + ///
1.92 + /// This class implements Kruskal's algorithm to find a minimum cost
1.93 + /// spanning tree. The
1.94 + ///
1.95 + /// \param _UGraph Undirected graph type.
1.96 + /// \param _CostMap Type of cost map.
1.97 + template <typename _UGraph, typename _CostMap,
1.98 + typename _Traits = KruskalDefaultTraits<_UGraph, _CostMap> >
1.99 + class Kruskal {
1.100 + public:
1.101 +
1.102 + typedef _Traits Traits;
1.103 +
1.104 + typedef typename _Traits::UGraph UGraph;
1.105 + typedef typename _Traits::CostMap CostMap;
1.106 +
1.107 + typedef typename _Traits::TreeMap TreeMap;
1.108 +
1.109 + typedef typename _Traits::Value Value;
1.110 +
1.111 + template <typename Comp>
1.112 + struct DefSortCompareTraits : public Traits {
1.113 + template <typename Iterator>
1.114 + static void sort(Iterator begin, Iterator end, const CostMap& cost) {
1.115 + _kruskal_bits::MappedComp<CostMap, Comp> comp(cost, Comp());
1.116 + std::sort(begin, end, comp);
1.117 + }
1.118 + };
1.119 +
1.120 + /// \brief \ref named-templ-param "Named parameter" for setting the
1.121 + /// comparator object of the standard sort
1.122 + ///
1.123 + /// \ref named-templ-param "Named parameter" for setting the
1.124 + /// comparator object of the standard sort
1.125 + template <typename Comp>
1.126 + struct DefSortCompare
1.127 + : public Kruskal<UGraph, CostMap, DefSortCompareTraits<Comp> > {
1.128 + typedef Kruskal<UGraph, CostMap, DefSortCompareTraits<Comp> > Create;
1.129 + };
1.130 +
1.131 + struct DefRadixSortTraits : public Traits {
1.132 + template <typename Iterator>
1.133 + static void sort(Iterator begin, Iterator end, const CostMap& cost) {
1.134 + radixSort(begin, end, cost);
1.135 + }
1.136 + };
1.137 +
1.138 + /// \brief \ref named-templ-param "Named parameter" for setting the
1.139 + /// sort function to radix sort
1.140 + ///
1.141 + /// \brief \ref named-templ-param "Named parameter" for setting the
1.142 + /// sort function to radix sort. The value type of the cost map should
1.143 + /// be integral, of course.
1.144 + struct DefRadixSort
1.145 + : public Kruskal<UGraph, CostMap, DefRadixSortTraits> {
1.146 + typedef Kruskal<UGraph, CostMap, DefRadixSortTraits> Create;
1.147 + };
1.148 +
1.149 + template <class TM>
1.150 + struct DefTreeMapTraits : public Traits {
1.151 + typedef TM TreeMap;
1.152 + static TreeMap *createTreeMap(const UGraph &) {
1.153 + throw UninitializedParameter();
1.154 + }
1.155 + };
1.156 +
1.157 + /// \brief \ref named-templ-param "Named parameter" for setting
1.158 + /// TreeMap
1.159 + ///
1.160 + /// \ref named-templ-param "Named parameter" for setting TreeMap
1.161 + ///
1.162 + template <class TM>
1.163 + struct DefTreeMap
1.164 + : public Kruskal< UGraph, CostMap, DefTreeMapTraits<TM> > {
1.165 + typedef Kruskal< UGraph, CostMap, DefTreeMapTraits<TM> > Create;
1.166 + };
1.167 +
1.168 +
1.169 + private:
1.170 +
1.171 + typedef typename UGraph::Node Node;
1.172 + typedef typename UGraph::NodeIt NodeIt;
1.173 +
1.174 + typedef typename UGraph::UEdge UEdge;
1.175 + typedef typename UGraph::UEdgeIt UEdgeIt;
1.176 +
1.177 + const UGraph& graph;
1.178 + const CostMap& cost;
1.179 +
1.180 + std::vector<UEdge> edges;
1.181 +
1.182 + typedef typename UGraph::template NodeMap<int> UfIndex;
1.183 + typedef UnionFind<UfIndex> Uf;
1.184 + UfIndex *ufi;
1.185 + Uf *uf;
1.186 +
1.187 + int index;
1.188 +
1.189 + void initStructures() {
1.190 + if (!_tree) {
1.191 + _tree = Traits::createTreeMap(graph);
1.192 + local_tree = true;
1.193 + }
1.194 + if (!uf) {
1.195 + ufi = new typename UGraph::template NodeMap<int>(graph);
1.196 + uf = new UnionFind<typename UGraph::template NodeMap<int> >(*ufi);
1.197 + }
1.198 + }
1.199 +
1.200 + void initUnionFind() {
1.201 + uf->clear();
1.202 + for (NodeIt it(graph); it != INVALID; ++it) {
1.203 + uf->insert(it);
1.204 + }
1.205 + }
1.206 +
1.207 + bool local_tree;
1.208 + TreeMap* _tree;
1.209 +
1.210 + public:
1.211 +
1.212 + /// \brief Constructor
1.213 + ///
1.214 + /// Constructor of the algorithm.
1.215 + Kruskal(const UGraph& _graph, const CostMap& _cost)
1.216 + : graph(_graph), cost(_cost),
1.217 + ufi(0), uf(0), local_tree(false), _tree(0) {}
1.218 +
1.219 + /// \brief Destructor
1.220 + ///
1.221 + /// Destructor
1.222 + ~Kruskal() {
1.223 + if (local_tree) {
1.224 + delete _tree;
1.225 + }
1.226 + if (uf) {
1.227 + delete uf;
1.228 + delete ufi;
1.229 + }
1.230 + }
1.231 +
1.232 + /// \brief Sets the map storing the tree edges.
1.233 + ///
1.234 + /// Sets the map storing the tree edges.
1.235 + /// If you don't use this function before calling \ref run(),
1.236 + /// it will allocate one. The destuctor deallocates this
1.237 + /// automatically allocated map, of course.
1.238 + /// \return \c *this </tt>
1.239 + Kruskal& treeMap(TreeMap &m){
1.240 + if (local_tree) {
1.241 + delete _tree;
1.242 + local_tree = false;
1.243 + }
1.244 + _tree = &m;
1.245 + return *this;
1.246 + }
1.247 +
1.248 + /// \brief Initialize the algorithm
1.249 + ///
1.250 + /// This member function initializes the unionfind data structure
1.251 + /// and sorts the edges into ascending order
1.252 + void init() {
1.253 + initStructures();
1.254 + initUnionFind();
1.255 + for (UEdgeIt e(graph); e != INVALID; ++e) {
1.256 + edges.push_back(e);
1.257 + _tree->set(e, false);
1.258 + }
1.259 + Traits::sort(edges.begin(), edges.end(), cost);
1.260 + index = 0;
1.261 + }
1.262 +
1.263 +
1.264 + /// \brief Initialize the algorithm
1.265 + ///
1.266 + /// This member function initializes the unionfind data structure
1.267 + /// and sets the edge order to the given sequence. The given
1.268 + /// sequence should be a valid STL range of undirected edges.
1.269 + template <typename Iterator>
1.270 + void initPresorted(Iterator begin, Iterator end) {
1.271 + initStructures();
1.272 + initUnionFind();
1.273 + edges.clear();
1.274 + std::copy(begin, end, std::back_inserter(edges));
1.275 + index = 0;
1.276 + }
1.277 +
1.278 + /// \brief Initialize the algorithm
1.279 + ///
1.280 + /// This member function initializes the unionfind data structure
1.281 + /// and sets the edge order to the given sequence. The given
1.282 + /// sequence should be a valid STL range of undirected edges.
1.283 + void reinit() {
1.284 + initStructures();
1.285 + initUnionFind();
1.286 + for (UEdgeIt e(graph); e != INVALID; ++e) {
1.287 + _tree->set(e, false);
1.288 + }
1.289 + index = 0;
1.290 + }
1.291 +
1.292 +
1.293 + /// \brief Executes the algorithm.
1.294 + ///
1.295 + /// Executes the algorithm.
1.296 + ///
1.297 + /// \pre init() must be called before using this function.
1.298 + ///
1.299 + /// This method runs the %Kruskal algorithm.
1.300 + void start() {
1.301 + while (index < int(edges.size())) {
1.302 + if (uf->join(graph.target(edges[index]), graph.source(edges[index]))) {
1.303 + _tree->set(edges[index], true);
1.304 + }
1.305 + ++index;
1.306 + }
1.307 + }
1.308 +
1.309 + /// \brief Runs the prim algorithm until it find a new tree edge
1.310 + ///
1.311 + /// Runs the prim algorithm until it find a new tree edge. If it
1.312 + /// does not next tree edge in the sequence it gives back \c INVALID.
1.313 + UEdge findNextTreeEdge() {
1.314 + while (index < int(edges.size())) {
1.315 + if (uf->join(graph.target(edges[index]), graph.source(edges[index]))) {
1.316 + _tree->set(edges[index], true);
1.317 + return edges[index++];
1.318 + }
1.319 + ++index;
1.320 + }
1.321 + return INVALID;
1.322 + }
1.323 +
1.324 + /// \brief Processes the next edge in the sequence
1.325 + ///
1.326 + /// Processes the next edge in the sequence.
1.327 + ///
1.328 + /// \return The prcocessed edge.
1.329 + ///
1.330 + /// \warning The sequence must not be empty!
1.331 + UEdge processNextEdge() {
1.332 + UEdge edge = edges[index++];
1.333 + processEdge(edge);
1.334 + return edge;
1.335 + }
1.336 +
1.337 + /// \brief Processes an arbitrary edge
1.338 + ///
1.339 + /// Processes the next edge in the sequence.
1.340 + ///
1.341 + /// \return True when the edge is a tree edge.
1.342 + bool processEdge(const UEdge& edge) {
1.343 + if (uf->join(graph.target(edge), graph.source(edge))) {
1.344 + _tree->set(edge, true);
1.345 + return true;
1.346 + } else {
1.347 + return false;
1.348 + }
1.349 + }
1.350 +
1.351 + /// \brief Returns \c false if there are edge to be processed in
1.352 + /// sequence
1.353 + ///
1.354 + /// Returns \c false if there are nodes to be processed in the
1.355 + /// sequence
1.356 + bool emptyQueue() {
1.357 + return index == int(edges.size());
1.358 + }
1.359 +
1.360 + /// \brief Returns the next edge to be processed
1.361 + ///
1.362 + /// Returns the next edge to be processed
1.363 + ///
1.364 + UEdge nextEdge() const {
1.365 + return edges[index];
1.366 + }
1.367 +
1.368 + /// \brief Runs %Kruskal algorithm.
1.369 + ///
1.370 + /// This method runs the %Kruskal algorithm in order to compute the
1.371 + /// minimum spanning tree (or minimum spanning forest). The
1.372 + /// method also works on graphs that has more than one components.
1.373 + /// In this case it computes the minimum spanning forest.
1.374 + void run() {
1.375 + init();
1.376 + start();
1.377 + }
1.378 +
1.379 + /// \brief Returns a reference to the tree edges map
1.380 + ///
1.381 + /// Returns a reference to the TreeEdgeMap of the edges of the
1.382 + /// minimum spanning tree. The value of the map is \c true only if
1.383 + /// the edge is in the minimum spanning tree.
1.384 + ///
1.385 + const TreeMap &treeMap() const { return *_tree;}
1.386 +
1.387 + /// \brief Returns the total cost of the tree
1.388 + ///
1.389 + /// Returns the total cost of the tree
1.390 + Value treeValue() const {
1.391 + Value value = 0;
1.392 + for (UEdgeIt it(graph); it != INVALID; ++it) {
1.393 + if ((*_tree)[it]) {
1.394 + value += cost[it];
1.395 + }
1.396 + }
1.397 + return value;
1.398 + }
1.399 +
1.400 + /// \brief Returns true when the given edge is tree edge
1.401 + ///
1.402 + /// Returns true when the given edge is tree edge
1.403 + bool tree(UEdge e) const {
1.404 + return (*_tree)[e];
1.405 + }
1.406 +
1.407 +
1.408 + };
1.409 +
1.410 +
1.411 + namespace _kruskal_bits {
1.412 +
1.413 + template <typename Graph, typename In, typename Out>
1.414 + typename In::value_type::second_type
1.415 + kruskal(const Graph& graph, const In& in, Out& out) {
1.416 + typedef typename In::value_type::second_type Value;
1.417 + typedef typename Graph::template NodeMap<int> IndexMap;
1.418 + typedef typename Graph::Node Node;
1.419 +
1.420 + IndexMap index(graph);
1.421 + UnionFind<IndexMap> uf(index);
1.422 + for (typename Graph::NodeIt it(graph); it != INVALID; ++it) {
1.423 + uf.insert(it);
1.424 + }
1.425 +
1.426 + Value tree_value = 0;
1.427 + for (typename In::const_iterator it = in.begin(); it != in.end(); ++it) {
1.428 + if (uf.join(graph.target(it->first),graph.source(it->first))) {
1.429 + out.set(it->first, true);
1.430 + tree_value += it->second;
1.431 + }
1.432 + else {
1.433 + out.set(it->first, false);
1.434 + }
1.435 + }
1.436 + return tree_value;
1.437 + }
1.438 +
1.439 +
1.440 + template <typename Sequence>
1.441 + struct PairComp {
1.442 + typedef typename Sequence::value_type Value;
1.443 + bool operator()(const Value& left, const Value& right) {
1.444 + return left.second < right.second;
1.445 + }
1.446 + };
1.447 +
1.448 + template <typename In, typename Enable = void>
1.449 + struct SequenceInputIndicator {
1.450 + static const bool value = false;
1.451 + };
1.452 +
1.453 + template <typename In>
1.454 + struct SequenceInputIndicator<In,
1.455 + typename exists<typename In::value_type::first_type>::type> {
1.456 + static const bool value = true;
1.457 + };
1.458 +
1.459 + template <typename In, typename Enable = void>
1.460 + struct MapInputIndicator {
1.461 + static const bool value = false;
1.462 + };
1.463 +
1.464 + template <typename In>
1.465 + struct MapInputIndicator<In,
1.466 + typename exists<typename In::Value>::type> {
1.467 + static const bool value = true;
1.468 + };
1.469 +
1.470 + template <typename In, typename Enable = void>
1.471 + struct SequenceOutputIndicator {
1.472 + static const bool value = false;
1.473 + };
1.474 +
1.475 + template <typename Out>
1.476 + struct SequenceOutputIndicator<Out,
1.477 + typename exists<typename Out::value_type>::type> {
1.478 + static const bool value = true;
1.479 + };
1.480 +
1.481 + template <typename Out, typename Enable = void>
1.482 + struct MapOutputIndicator {
1.483 + static const bool value = false;
1.484 + };
1.485 +
1.486 + template <typename Out>
1.487 + struct MapOutputIndicator<Out,
1.488 + typename exists<typename Out::Value>::type> {
1.489 + static const bool value = true;
1.490 + };
1.491 +
1.492 + template <typename In, typename InEnable = void>
1.493 + struct KruskalValueSelector {};
1.494 +
1.495 + template <typename In>
1.496 + struct KruskalValueSelector<In,
1.497 + typename enable_if<SequenceInputIndicator<In>, void>::type>
1.498 + {
1.499 + typedef typename In::value_type::second_type Value;
1.500 + };
1.501 +
1.502 + template <typename In>
1.503 + struct KruskalValueSelector<In,
1.504 + typename enable_if<MapInputIndicator<In>, void>::type>
1.505 + {
1.506 + typedef typename In::Value Value;
1.507 + };
1.508 +
1.509 + template <typename Graph, typename In, typename Out,
1.510 + typename InEnable = void>
1.511 + struct KruskalInputSelector {};
1.512 +
1.513 + template <typename Graph, typename In, typename Out,
1.514 + typename InEnable = void>
1.515 + struct KruskalOutputSelector {};
1.516 +
1.517 + template <typename Graph, typename In, typename Out>
1.518 + struct KruskalInputSelector<Graph, In, Out,
1.519 + typename enable_if<SequenceInputIndicator<In>, void>::type >
1.520 + {
1.521 + typedef typename In::value_type::second_type Value;
1.522 +
1.523 + static Value kruskal(const Graph& graph, const In& in, Out& out) {
1.524 + return KruskalOutputSelector<Graph, In, Out>::
1.525 + kruskal(graph, in, out);
1.526 + }
1.527 +
1.528 + };
1.529 +
1.530 + template <typename Graph, typename In, typename Out>
1.531 + struct KruskalInputSelector<Graph, In, Out,
1.532 + typename enable_if<MapInputIndicator<In>, void>::type >
1.533 + {
1.534 + typedef typename In::Value Value;
1.535 + static Value kruskal(const Graph& graph, const In& in, Out& out) {
1.536 + typedef typename In::Key MapEdge;
1.537 + typedef typename In::Value Value;
1.538 + typedef typename ItemSetTraits<Graph, MapEdge>::ItemIt MapEdgeIt;
1.539 + typedef std::vector<std::pair<MapEdge, Value> > Sequence;
1.540 + Sequence seq;
1.541 +
1.542 + for (MapEdgeIt it(graph); it != INVALID; ++it) {
1.543 + seq.push_back(make_pair(it, in[it]));
1.544 + }
1.545 +
1.546 + std::sort(seq.begin(), seq.end(), PairComp<Sequence>());
1.547 + return KruskalOutputSelector<Graph, Sequence, Out>::
1.548 + kruskal(graph, seq, out);
1.549 + }
1.550 + };
1.551 +
1.552 + template <typename Graph, typename In, typename Out>
1.553 + struct KruskalOutputSelector<Graph, In, Out,
1.554 + typename enable_if<SequenceOutputIndicator<Out>, void>::type >
1.555 + {
1.556 + typedef typename In::value_type::second_type Value;
1.557 +
1.558 + static Value kruskal(const Graph& graph, const In& in, Out& out) {
1.559 + typedef StoreBoolMap<Out> Map;
1.560 + Map map(out);
1.561 + return _kruskal_bits::kruskal(graph, in, map);
1.562 + }
1.563 +
1.564 + };
1.565 +
1.566 + template <typename Graph, typename In, typename Out>
1.567 + struct KruskalOutputSelector<Graph, In, Out,
1.568 + typename enable_if<MapOutputIndicator<Out>, void>::type >
1.569 + {
1.570 + typedef typename In::value_type::second_type Value;
1.571 +
1.572 + static Value kruskal(const Graph& graph, const In& in, Out& out) {
1.573 + return _kruskal_bits::kruskal(graph, in, out);
1.574 + }
1.575 + };
1.576 +
1.577 + }
1.578 +
1.579 + /// \ingroup spantree
1.580 + ///
1.581 + /// \brief Kruskal's algorithm to find a minimum cost tree of a graph.
1.582 + ///
1.583 /// This function runs Kruskal's algorithm to find a minimum cost tree.
1.584 /// Due to hard C++ hacking, it accepts various input and output types.
1.585 ///
1.586 @@ -50,387 +611,66 @@
1.587 ///
1.588 /// \param in This object is used to describe the edge costs. It can be one
1.589 /// of the following choices.
1.590 - /// - An STL compatible 'Forward Container'
1.591 - /// with <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>,
1.592 - /// where \c X is the type of the costs. The pairs indicates the edges along
1.593 - /// with the assigned cost. <em>They must be in a
1.594 + ///
1.595 + /// - An STL compatible 'Forward Container' with
1.596 + /// <tt>std::pair<GR::UEdge,X></tt> or
1.597 + /// <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>, where
1.598 + /// \c X is the type of the costs. The pairs indicates the edges
1.599 + /// along with the assigned cost. <em>They must be in a
1.600 /// cost-ascending order.</em>
1.601 /// - Any readable Edge map. The values of the map indicate the edge costs.
1.602 ///
1.603 /// \retval out Here we also have a choise.
1.604 - /// - It can be a writable \c bool edge map.
1.605 - /// After running the algorithm
1.606 - /// this will contain the found minimum cost spanning tree: the value of an
1.607 - /// edge will be set to \c true if it belongs to the tree, otherwise it will
1.608 - /// be set to \c false. The value of each edge will be set exactly once.
1.609 + /// - It can be a writable \c bool edge map. After running the
1.610 + /// algorithm this will contain the found minimum cost spanning
1.611 + /// tree: the value of an edge will be set to \c true if it belongs
1.612 + /// to the tree, otherwise it will be set to \c false. The value of
1.613 + /// each edge will be set exactly once.
1.614 /// - It can also be an iteraror of an STL Container with
1.615 - /// <tt>GR::Edge</tt> as its <tt>value_type</tt>.
1.616 - /// The algorithm copies the elements of the found tree into this sequence.
1.617 - /// For example, if we know that the spanning tree of the graph \c g has
1.618 - /// say 53 edges, then
1.619 - /// we can put its edges into an STL vector \c tree with a code like this.
1.620 + /// <tt>GR::UEdge</tt> or <tt>GR::Edge</tt> as its
1.621 + /// <tt>value_type</tt>. The algorithm copies the elements of the
1.622 + /// found tree into this sequence. For example, if we know that the
1.623 + /// spanning tree of the graph \c g has say 53 edges, then we can
1.624 + /// put its edges into an STL vector \c tree with a code like this.
1.625 ///\code
1.626 /// std::vector<Edge> tree(53);
1.627 /// kruskal(g,cost,tree.begin());
1.628 ///\endcode
1.629 - /// Or if we don't know in advance the size of the tree, we can write this.
1.630 - ///\code
1.631 - /// std::vector<Edge> tree;
1.632 - /// kruskal(g,cost,std::back_inserter(tree));
1.633 + /// Or if we don't know in advance the size of the tree, we can
1.634 + /// write this.
1.635 + ///\code std::vector<Edge> tree;
1.636 + /// kruskal(g,cost,std::back_inserter(tree));
1.637 ///\endcode
1.638 ///
1.639 - /// \return The cost of the found tree.
1.640 + /// \return The total cost of the found tree.
1.641 ///
1.642 - /// \warning If kruskal runs on an
1.643 - /// \ref lemon::concepts::UGraph "undirected graph", be sure that the
1.644 - /// map storing the tree is also undirected
1.645 - /// (e.g. ListUGraph::UEdgeMap<bool>, otherwise the values of the
1.646 - /// half of the edges will not be set.
1.647 + /// \warning If kruskal runs on an be consistent of using the same
1.648 + /// Edge type for input and output.
1.649 ///
1.650
1.651 #ifdef DOXYGEN
1.652 - template <class GR, class IN, class OUT>
1.653 - CostType
1.654 - kruskal(GR const& g, IN const& in,
1.655 - OUT& out)
1.656 -#else
1.657 - template <class GR, class IN, class OUT>
1.658 - typename IN::value_type::second_type
1.659 - kruskal(GR const& g, IN const& in,
1.660 - OUT& out,
1.661 -// typename IN::value_type::first_type = typename GR::Edge()
1.662 -// ,typename OUT::Key = OUT::Key()
1.663 -// //,typename OUT::Key = typename GR::Edge()
1.664 - const typename IN::value_type::first_type * =
1.665 - reinterpret_cast<const typename IN::value_type::first_type*>(0),
1.666 - const typename OUT::Key * =
1.667 - reinterpret_cast<const typename OUT::Key*>(0)
1.668 - )
1.669 + template <class Graph, class In, class Out>
1.670 + Value kruskal(GR const& g, const In& in, Out& out)
1.671 +#else
1.672 + template <class Graph, class In, class Out>
1.673 + inline typename _kruskal_bits::KruskalValueSelector<In>::Value
1.674 + kruskal(const Graph& graph, const In& in, Out& out)
1.675 #endif
1.676 {
1.677 - typedef typename IN::value_type::second_type EdgeCost;
1.678 - typedef typename GR::template NodeMap<int> NodeIntMap;
1.679 - typedef typename GR::Node Node;
1.680 -
1.681 - NodeIntMap comp(g);
1.682 - UnionFind<NodeIntMap> uf(comp);
1.683 - for (typename GR::NodeIt it(g); it != INVALID; ++it) {
1.684 - uf.insert(it);
1.685 - }
1.686 -
1.687 - EdgeCost tot_cost = 0;
1.688 - for (typename IN::const_iterator p = in.begin();
1.689 - p!=in.end(); ++p ) {
1.690 - if ( uf.join(g.target((*p).first),
1.691 - g.source((*p).first)) ) {
1.692 - out.set((*p).first, true);
1.693 - tot_cost += (*p).second;
1.694 - }
1.695 - else {
1.696 - out.set((*p).first, false);
1.697 - }
1.698 - }
1.699 - return tot_cost;
1.700 + return _kruskal_bits::KruskalInputSelector<Graph, In, Out>::
1.701 + kruskal(graph, in, out);
1.702 }
1.703
1.704
1.705 - /// @}
1.706 -
1.707 -
1.708 - /* A work-around for running Kruskal with const-reference bool maps... */
1.709 -
1.710 - /// Helper class for calling kruskal with "constant" output map.
1.711 -
1.712 - /// Helper class for calling kruskal with output maps constructed
1.713 - /// on-the-fly.
1.714 - ///
1.715 - /// A typical examle is the following call:
1.716 - /// <tt>kruskal(g, some_input, makeSequenceOutput(iterator))</tt>.
1.717 - /// Here, the third argument is a temporary object (which wraps around an
1.718 - /// iterator with a writable bool map interface), and thus by rules of C++
1.719 - /// is a \c const object. To enable call like this exist this class and
1.720 - /// the prototype of the \ref kruskal() function with <tt>const& OUT</tt>
1.721 - /// third argument.
1.722 - template<class Map>
1.723 - class NonConstMapWr {
1.724 - const Map &m;
1.725 - public:
1.726 - typedef typename Map::Key Key;
1.727 - typedef typename Map::Value Value;
1.728 -
1.729 - NonConstMapWr(const Map &_m) : m(_m) {}
1.730 -
1.731 - template<class Key>
1.732 - void set(Key const& k, Value const &v) const { m.set(k,v); }
1.733 - };
1.734 -
1.735 - template <class GR, class IN, class OUT>
1.736 - inline
1.737 - typename IN::value_type::second_type
1.738 - kruskal(GR const& g, IN const& edges, OUT const& out_map,
1.739 -// typename IN::value_type::first_type = typename GR::Edge(),
1.740 -// typename OUT::Key = GR::Edge()
1.741 - const typename IN::value_type::first_type * =
1.742 - reinterpret_cast<const typename IN::value_type::first_type*>(0),
1.743 - const typename OUT::Key * =
1.744 - reinterpret_cast<const typename OUT::Key*>(0)
1.745 - )
1.746 - {
1.747 - NonConstMapWr<OUT> map_wr(out_map);
1.748 - return kruskal(g, edges, map_wr);
1.749 - }
1.750 -
1.751 - /* ** ** Input-objects ** ** */
1.752 -
1.753 - /// Kruskal's input source.
1.754 -
1.755 - /// Kruskal's input source.
1.756 - ///
1.757 - /// In most cases you possibly want to use the \ref kruskal() instead.
1.758 - ///
1.759 - /// \sa makeKruskalMapInput()
1.760 - ///
1.761 - ///\param GR The type of the graph the algorithm runs on.
1.762 - ///\param Map An edge map containing the cost of the edges.
1.763 - ///\par
1.764 - ///The cost type can be any type satisfying
1.765 - ///the STL 'LessThan comparable'
1.766 - ///concept if it also has an operator+() implemented. (It is necessary for
1.767 - ///computing the total cost of the tree).
1.768 - ///
1.769 - template<class GR, class Map>
1.770 - class KruskalMapInput
1.771 - : public std::vector< std::pair<typename GR::Edge,
1.772 - typename Map::Value> > {
1.773 -
1.774 - public:
1.775 - typedef std::vector< std::pair<typename GR::Edge,
1.776 - typename Map::Value> > Parent;
1.777 - typedef typename Parent::value_type value_type;
1.778 -
1.779 - private:
1.780 - class comparePair {
1.781 - public:
1.782 - bool operator()(const value_type& a,
1.783 - const value_type& b) {
1.784 - return a.second < b.second;
1.785 - }
1.786 - };
1.787 -
1.788 - template<class _GR>
1.789 - typename enable_if<UndirectedTagIndicator<_GR>,void>::type
1.790 - fillWithEdges(const _GR& g, const Map& m,dummy<0> = 0)
1.791 - {
1.792 - for(typename GR::UEdgeIt e(g);e!=INVALID;++e)
1.793 - push_back(value_type(g.direct(e, true), m[e]));
1.794 - }
1.795 -
1.796 - template<class _GR>
1.797 - typename disable_if<UndirectedTagIndicator<_GR>,void>::type
1.798 - fillWithEdges(const _GR& g, const Map& m,dummy<1> = 1)
1.799 - {
1.800 - for(typename GR::EdgeIt e(g);e!=INVALID;++e)
1.801 - push_back(value_type(e, m[e]));
1.802 - }
1.803 -
1.804 -
1.805 - public:
1.806 -
1.807 - void sort() {
1.808 - std::sort(this->begin(), this->end(), comparePair());
1.809 - }
1.810 -
1.811 - KruskalMapInput(GR const& g, Map const& m) {
1.812 - fillWithEdges(g,m);
1.813 - sort();
1.814 - }
1.815 - };
1.816 -
1.817 - /// Creates a KruskalMapInput object for \ref kruskal()
1.818 -
1.819 - /// It makes easier to use
1.820 - /// \ref KruskalMapInput by making it unnecessary
1.821 - /// to explicitly give the type of the parameters.
1.822 - ///
1.823 - /// In most cases you possibly
1.824 - /// want to use \ref kruskal() instead.
1.825 - ///
1.826 - ///\param g The type of the graph the algorithm runs on.
1.827 - ///\param m An edge map containing the cost of the edges.
1.828 - ///\par
1.829 - ///The cost type can be any type satisfying the
1.830 - ///STL 'LessThan Comparable'
1.831 - ///concept if it also has an operator+() implemented. (It is necessary for
1.832 - ///computing the total cost of the tree).
1.833 - ///
1.834 - ///\return An appropriate input source for \ref kruskal().
1.835 - ///
1.836 - template<class GR, class Map>
1.837 - inline
1.838 - KruskalMapInput<GR,Map> makeKruskalMapInput(const GR &g,const Map &m)
1.839 - {
1.840 - return KruskalMapInput<GR,Map>(g,m);
1.841 - }
1.842 -
1.843
1.844
1.845 - /* ** ** Output-objects: simple writable bool maps ** ** */
1.846 -
1.847 -
1.848 -
1.849 - /// A writable bool-map that makes a sequence of "true" keys
1.850 -
1.851 - /// A writable bool-map that creates a sequence out of keys that receives
1.852 - /// the value "true".
1.853 - ///
1.854 - /// \sa makeKruskalSequenceOutput()
1.855 - ///
1.856 - /// Very often, when looking for a min cost spanning tree, we want as
1.857 - /// output a container containing the edges of the found tree. For this
1.858 - /// purpose exist this class that wraps around an STL iterator with a
1.859 - /// writable bool map interface. When a key gets value "true" this key
1.860 - /// is added to sequence pointed by the iterator.
1.861 - ///
1.862 - /// A typical usage:
1.863 - ///\code
1.864 - /// std::vector<Graph::Edge> v;
1.865 - /// kruskal(g, input, makeKruskalSequenceOutput(back_inserter(v)));
1.866 - ///\endcode
1.867 - ///
1.868 - /// For the most common case, when the input is given by a simple edge
1.869 - /// map and the output is a sequence of the tree edges, a special
1.870 - /// wrapper function exists: \ref kruskalEdgeMap_IteratorOut().
1.871 - ///
1.872 - /// \warning Not a regular property map, as it doesn't know its Key
1.873 -
1.874 - template<class Iterator>
1.875 - class KruskalSequenceOutput {
1.876 - mutable Iterator it;
1.877 -
1.878 - public:
1.879 - typedef typename std::iterator_traits<Iterator>::value_type Key;
1.880 - typedef bool Value;
1.881 -
1.882 - KruskalSequenceOutput(Iterator const &_it) : it(_it) {}
1.883 -
1.884 - template<typename Key>
1.885 - void set(Key const& k, bool v) const { if(v) {*it=k; ++it;} }
1.886 - };
1.887 -
1.888 - template<class Iterator>
1.889 - inline
1.890 - KruskalSequenceOutput<Iterator>
1.891 - makeKruskalSequenceOutput(Iterator it) {
1.892 - return KruskalSequenceOutput<Iterator>(it);
1.893 - }
1.894 -
1.895 -
1.896 -
1.897 - /* ** ** Wrapper funtions ** ** */
1.898 -
1.899 -// \brief Wrapper function to kruskal().
1.900 -// Input is from an edge map, output is a plain bool map.
1.901 -//
1.902 -// Wrapper function to kruskal().
1.903 -// Input is from an edge map, output is a plain bool map.
1.904 -//
1.905 -// \param g The type of the graph the algorithm runs on.
1.906 -// \param in An edge map containing the cost of the edges.
1.907 -// \par
1.908 -// The cost type can be any type satisfying the
1.909 -// STL 'LessThan Comparable'
1.910 -// concept if it also has an operator+() implemented. (It is necessary for
1.911 -// computing the total cost of the tree).
1.912 -//
1.913 -// \retval out This must be a writable \c bool edge map.
1.914 -// After running the algorithm
1.915 -// this will contain the found minimum cost spanning tree: the value of an
1.916 -// edge will be set to \c true if it belongs to the tree, otherwise it will
1.917 -// be set to \c false. The value of each edge will be set exactly once.
1.918 -//
1.919 -// \return The cost of the found tree.
1.920 -
1.921 - template <class GR, class IN, class RET>
1.922 - inline
1.923 - typename IN::Value
1.924 - kruskal(GR const& g,
1.925 - IN const& in,
1.926 - RET &out,
1.927 - // typename IN::Key = typename GR::Edge(),
1.928 - //typename IN::Key = typename IN::Key (),
1.929 - // typename RET::Key = typename GR::Edge()
1.930 - const typename IN::Key * =
1.931 - reinterpret_cast<const typename IN::Key*>(0),
1.932 - const typename RET::Key * =
1.933 - reinterpret_cast<const typename RET::Key*>(0)
1.934 - )
1.935 + template <class Graph, class In, class Out>
1.936 + inline typename _kruskal_bits::KruskalValueSelector<In>::Value
1.937 + kruskal(const Graph& graph, const In& in, const Out& out)
1.938 {
1.939 - return kruskal(g,
1.940 - KruskalMapInput<GR,IN>(g,in),
1.941 - out);
1.942 - }
1.943 -
1.944 -// \brief Wrapper function to kruskal().
1.945 -// Input is from an edge map, output is an STL Sequence.
1.946 -//
1.947 -// Wrapper function to kruskal().
1.948 -// Input is from an edge map, output is an STL Sequence.
1.949 -//
1.950 -// \param g The type of the graph the algorithm runs on.
1.951 -// \param in An edge map containing the cost of the edges.
1.952 -// \par
1.953 -// The cost type can be any type satisfying the
1.954 -// STL 'LessThan Comparable'
1.955 -// concept if it also has an operator+() implemented. (It is necessary for
1.956 -// computing the total cost of the tree).
1.957 -//
1.958 -// \retval out This must be an iteraror of an STL Container with
1.959 -// <tt>GR::Edge</tt> as its <tt>value_type</tt>.
1.960 -// The algorithm copies the elements of the found tree into this sequence.
1.961 -// For example, if we know that the spanning tree of the graph \c g has
1.962 -// say 53 edges, then
1.963 -// we can put its edges into an STL vector \c tree with a code like this.
1.964 -//\code
1.965 -// std::vector<Edge> tree(53);
1.966 -// kruskal(g,cost,tree.begin());
1.967 -//\endcode
1.968 -// Or if we don't know in advance the size of the tree, we can write this.
1.969 -//\code
1.970 -// std::vector<Edge> tree;
1.971 -// kruskal(g,cost,std::back_inserter(tree));
1.972 -//\endcode
1.973 -//
1.974 -// \return The cost of the found tree.
1.975 -//
1.976 -// \bug its name does not follow the coding style.
1.977 -
1.978 - template <class GR, class IN, class RET>
1.979 - inline
1.980 - typename IN::Value
1.981 - kruskal(const GR& g,
1.982 - const IN& in,
1.983 - RET out,
1.984 - const typename RET::value_type * =
1.985 - reinterpret_cast<const typename RET::value_type*>(0)
1.986 - )
1.987 - {
1.988 - KruskalSequenceOutput<RET> _out(out);
1.989 - return kruskal(g, KruskalMapInput<GR,IN>(g, in), _out);
1.990 - }
1.991 -
1.992 - template <class GR, class IN, class RET>
1.993 - inline
1.994 - typename IN::Value
1.995 - kruskal(const GR& g,
1.996 - const IN& in,
1.997 - RET *out
1.998 - )
1.999 - {
1.1000 - KruskalSequenceOutput<RET*> _out(out);
1.1001 - return kruskal(g, KruskalMapInput<GR,IN>(g, in), _out);
1.1002 - }
1.1003 -
1.1004 - /// @}
1.1005 + return _kruskal_bits::KruskalInputSelector<Graph, In, const Out>::
1.1006 + kruskal(graph, in, out);
1.1007 + }
1.1008
1.1009 } //namespace lemon
1.1010
2.1 --- a/test/kruskal_test.cc Thu Apr 19 15:09:08 2007 +0000
2.2 +++ b/test/kruskal_test.cc Thu Apr 19 15:11:58 2007 +0000
2.3 @@ -23,8 +23,10 @@
2.4 #include <lemon/maps.h>
2.5 #include <lemon/kruskal.h>
2.6 #include <lemon/list_graph.h>
2.7 +
2.8 #include <lemon/concepts/maps.h>
2.9 #include <lemon/concepts/graph.h>
2.10 +#include <lemon/concepts/ugraph.h>
2.11
2.12
2.13 using namespace std;
2.14 @@ -33,21 +35,56 @@
2.15 void checkCompileKruskal()
2.16 {
2.17 concepts::WriteMap<concepts::Graph::Edge,bool> w;
2.18 + concepts::WriteMap<concepts::UGraph::UEdge,bool> uw;
2.19 +
2.20 + concepts::ReadMap<concepts::Graph::Edge,int> r;
2.21 + concepts::ReadMap<concepts::UGraph::UEdge,int> ur;
2.22
2.23 concepts::Graph g;
2.24 - kruskal(g,
2.25 - concepts::ReadMap<concepts::Graph::Edge,int>(),
2.26 - w);
2.27 + concepts::UGraph ug;
2.28 +
2.29 + kruskal(g, r, w);
2.30 + kruskal(ug, ur, uw);
2.31 +
2.32 + std::vector<std::pair<concepts::Graph::Edge, int> > rs;
2.33 + std::vector<std::pair<concepts::UGraph::UEdge, int> > urs;
2.34 +
2.35 + kruskal(g, rs, w);
2.36 + kruskal(ug, urs, uw);
2.37 +
2.38 + std::vector<concepts::Graph::Edge> ws;
2.39 + std::vector<concepts::UGraph::UEdge> uws;
2.40 +
2.41 + kruskal(g, r, ws.begin());
2.42 + kruskal(ug, ur, uws.begin());
2.43 +
2.44 + Kruskal<concepts::UGraph,concepts::ReadMap<concepts::UGraph::UEdge,int> >
2.45 + alg(ug, ur);
2.46 +
2.47 + alg.init();
2.48 + alg.initPresorted(uws.begin(), uws.end());
2.49 + alg.reinit();
2.50 +
2.51 + alg.emptyQueue();
2.52 +
2.53 + alg.nextEdge();
2.54 + alg.processNextEdge();
2.55 + alg.processEdge(concepts::UGraph::UEdge());
2.56 +
2.57 + alg.run();
2.58 +
2.59 + alg.treeMap();
2.60 + alg.tree(concepts::UGraph::UEdge());
2.61 }
2.62
2.63 int main() {
2.64
2.65 - typedef ListGraph::Node Node;
2.66 - typedef ListGraph::Edge Edge;
2.67 - typedef ListGraph::NodeIt NodeIt;
2.68 - typedef ListGraph::EdgeIt EdgeIt;
2.69 + typedef ListUGraph::Node Node;
2.70 + typedef ListUGraph::UEdge UEdge;
2.71 + typedef ListUGraph::NodeIt NodeIt;
2.72 + typedef ListUGraph::EdgeIt EdgeIt;
2.73
2.74 - ListGraph G;
2.75 + ListUGraph G;
2.76
2.77 Node s=G.addNode();
2.78 Node v1=G.addNode();
2.79 @@ -56,26 +93,26 @@
2.80 Node v4=G.addNode();
2.81 Node t=G.addNode();
2.82
2.83 - Edge e1 = G.addEdge(s, v1);
2.84 - Edge e2 = G.addEdge(s, v2);
2.85 - Edge e3 = G.addEdge(v1, v2);
2.86 - Edge e4 = G.addEdge(v2, v1);
2.87 - Edge e5 = G.addEdge(v1, v3);
2.88 - Edge e6 = G.addEdge(v3, v2);
2.89 - Edge e7 = G.addEdge(v2, v4);
2.90 - Edge e8 = G.addEdge(v4, v3);
2.91 - Edge e9 = G.addEdge(v3, t);
2.92 - Edge e10 = G.addEdge(v4, t);
2.93 + UEdge e1 = G.addEdge(s, v1);
2.94 + UEdge e2 = G.addEdge(s, v2);
2.95 + UEdge e3 = G.addEdge(v1, v2);
2.96 + UEdge e4 = G.addEdge(v2, v1);
2.97 + UEdge e5 = G.addEdge(v1, v3);
2.98 + UEdge e6 = G.addEdge(v3, v2);
2.99 + UEdge e7 = G.addEdge(v2, v4);
2.100 + UEdge e8 = G.addEdge(v4, v3);
2.101 + UEdge e9 = G.addEdge(v3, t);
2.102 + UEdge e10 = G.addEdge(v4, t);
2.103
2.104 - typedef ListGraph::EdgeMap<int> ECostMap;
2.105 - typedef ListGraph::EdgeMap<bool> EBoolMap;
2.106 + typedef ListUGraph::UEdgeMap<int> ECostMap;
2.107 + typedef ListUGraph::UEdgeMap<bool> EBoolMap;
2.108
2.109 ECostMap edge_cost_map(G, 2);
2.110 EBoolMap tree_map(G);
2.111
2.112
2.113 //Test with const map.
2.114 - check(kruskal(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10,
2.115 + check(kruskal(G, ConstMap<ListUGraph::UEdge,int>(2), tree_map)==10,
2.116 "Total cost should be 10");
2.117 //Test with a edge map (filled with uniform costs).
2.118 check(kruskal(G, edge_cost_map, tree_map)==10,
2.119 @@ -92,7 +129,7 @@
2.120 edge_cost_map.set(e9, -2);
2.121 edge_cost_map.set(e10, -1);
2.122
2.123 - vector<Edge> tree_edge_vec(5);
2.124 + vector<UEdge> tree_edge_vec(5);
2.125
2.126 //Test with a edge map and inserter.
2.127 check(kruskal(G, edge_cost_map,
2.128 @@ -107,14 +144,14 @@
2.129 ==-31,
2.130 "Total cost should be -31.");
2.131
2.132 - tree_edge_vec.clear();
2.133 +// tree_edge_vec.clear();
2.134
2.135 - //The above test could also be coded like this:
2.136 - check(kruskal(G,
2.137 - makeKruskalMapInput(G, edge_cost_map),
2.138 - makeKruskalSequenceOutput(back_inserter(tree_edge_vec)))
2.139 - ==-31,
2.140 - "Total cost should be -31.");
2.141 +// //The above test could also be coded like this:
2.142 +// check(kruskal(G,
2.143 +// makeKruskalMapInput(G, edge_cost_map),
2.144 +// makeKruskalSequenceOutput(back_inserter(tree_edge_vec)))
2.145 +// ==-31,
2.146 +// "Total cost should be -31.");
2.147
2.148 check(tree_edge_vec.size()==5,"The tree should have 5 edges.");
2.149
2.150 @@ -125,5 +162,19 @@
2.151 tree_edge_vec[4]==e9,
2.152 "Wrong tree.");
2.153
2.154 + Kruskal<ListUGraph, ECostMap> ka(G, edge_cost_map);
2.155 +
2.156 + ka.run();
2.157 +
2.158 + check(ka.tree(e1) &&
2.159 + ka.tree(e2) &&
2.160 + ka.tree(e5) &&
2.161 + ka.tree(e7) &&
2.162 + ka.tree(e9),
2.163 + "Wrong tree.");
2.164 +
2.165 + check(ka.treeValue() == -31,
2.166 + "Total cost should be -31.");
2.167 +
2.168 return 0;
2.169 }