alpar@906: /* -*- C++ -*- alpar@906: * alpar@1956: * This file is a part of LEMON, a generic C++ optimization library alpar@1956: * alpar@2391: * Copyright (C) 2003-2007 alpar@1956: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@1359: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@906: * alpar@906: * Permission to use, modify and distribute this software is granted alpar@906: * provided that this copyright notice appears in all copies. For alpar@906: * precise terms see the accompanying LICENSE file. alpar@906: * alpar@906: * This software is provided "AS IS" with no warranty of any kind, alpar@906: * express or implied, and with no claim as to its suitability for any alpar@906: * purpose. alpar@906: * alpar@906: */ alpar@906: alpar@921: #ifndef LEMON_KRUSKAL_H alpar@921: #define LEMON_KRUSKAL_H alpar@810: alpar@810: #include klao@1942: #include alpar@921: #include deba@2424: #include deba@2424: #include deba@2424: deba@2424: #include deba@2424: deba@1993: #include deba@1993: #include alpar@810: alpar@810: ///\ingroup spantree alpar@810: ///\file alpar@810: ///\brief Kruskal's algorithm to compute a minimum cost tree alpar@810: /// alpar@810: ///Kruskal's algorithm to compute a minimum cost tree. alpar@1557: /// alpar@810: alpar@921: namespace lemon { alpar@810: deba@2424: namespace _kruskal_bits { alpar@810: deba@2424: template deba@2424: struct MappedComp { alpar@810: deba@2424: typedef typename Map::Key Key; deba@2424: deba@2424: const Map& map; deba@2424: Comp comp; deba@2424: deba@2424: MappedComp(const Map& _map) deba@2424: : map(_map), comp() {} deba@2424: deba@2424: bool operator()(const Key& left, const Key& right) { deba@2424: return comp(map[left], map[right]); deba@2424: } deba@2424: deba@2424: }; deba@2424: deba@2424: } deba@2424: deba@2424: /// \brief Default traits class of Kruskal class. deba@2424: /// deba@2424: /// Default traits class of Kruskal class. deba@2424: /// \param _UGraph Undirected graph type. deba@2424: /// \param _CostMap Type of cost map. deba@2424: template deba@2424: struct KruskalDefaultTraits{ deba@2424: deba@2424: /// \brief The graph type the algorithm runs on. deba@2424: typedef _UGraph UGraph; deba@2424: deba@2424: /// \brief The type of the map that stores the edge costs. deba@2424: /// deba@2424: /// The type of the map that stores the edge costs. deba@2424: /// It must meet the \ref concepts::ReadMap "ReadMap" concept. deba@2424: typedef _CostMap CostMap; deba@2424: deba@2424: /// \brief The type of the cost of the edges. deba@2424: typedef typename _CostMap::Value Value; deba@2424: deba@2424: /// \brief The type of the map that stores whether an edge is in the deba@2424: /// spanning tree or not. deba@2424: /// deba@2424: /// The type of the map that stores whether an edge is in the deba@2424: /// spanning tree or not. deba@2424: typedef typename _UGraph::template UEdgeMap TreeMap; deba@2424: deba@2424: /// \brief Instantiates a TreeMap. deba@2424: /// deba@2424: /// This function instantiates a \ref TreeMap. deba@2424: /// deba@2424: /// The first parameter is the graph, to which deba@2424: /// we would like to define the \ref TreeMap deba@2424: static TreeMap *createTreeMap(const _UGraph& graph){ deba@2424: return new TreeMap(graph); deba@2424: } deba@2424: deba@2424: template deba@2424: static void sort(Iterator begin, Iterator end, const CostMap& cost) { deba@2424: _kruskal_bits::MappedComp > comp(cost); deba@2424: std::sort(begin, end, comp); deba@2424: } deba@2424: deba@2424: }; deba@2424: deba@2428: ///\ingroup spantree deba@2428: /// deba@2424: /// \brief Kruskal's algorithm to find a minimum cost tree of a graph. deba@2424: /// deba@2424: /// This class implements Kruskal's algorithm to find a minimum cost deba@2424: /// spanning tree. The deba@2424: /// deba@2424: /// \param _UGraph Undirected graph type. deba@2424: /// \param _CostMap Type of cost map. deba@2424: template > deba@2424: class Kruskal { deba@2424: public: deba@2424: deba@2424: typedef _Traits Traits; deba@2424: deba@2424: typedef typename _Traits::UGraph UGraph; deba@2424: typedef typename _Traits::CostMap CostMap; deba@2424: deba@2424: typedef typename _Traits::TreeMap TreeMap; deba@2424: deba@2424: typedef typename _Traits::Value Value; deba@2424: deba@2424: template deba@2424: struct DefSortCompareTraits : public Traits { deba@2424: template deba@2424: static void sort(Iterator begin, Iterator end, const CostMap& cost) { deba@2424: _kruskal_bits::MappedComp comp(cost, Comp()); deba@2424: std::sort(begin, end, comp); deba@2424: } deba@2424: }; deba@2424: deba@2424: /// \brief \ref named-templ-param "Named parameter" for setting the deba@2424: /// comparator object of the standard sort deba@2424: /// deba@2424: /// \ref named-templ-param "Named parameter" for setting the deba@2424: /// comparator object of the standard sort deba@2424: template deba@2424: struct DefSortCompare deba@2424: : public Kruskal > { deba@2424: typedef Kruskal > Create; deba@2424: }; deba@2424: deba@2424: struct DefRadixSortTraits : public Traits { deba@2424: template deba@2424: static void sort(Iterator begin, Iterator end, const CostMap& cost) { deba@2424: radixSort(begin, end, cost); deba@2424: } deba@2424: }; deba@2424: deba@2424: /// \brief \ref named-templ-param "Named parameter" for setting the deba@2424: /// sort function to radix sort deba@2424: /// deba@2424: /// \brief \ref named-templ-param "Named parameter" for setting the deba@2424: /// sort function to radix sort. The value type of the cost map should deba@2424: /// be integral, of course. deba@2424: struct DefRadixSort deba@2424: : public Kruskal { deba@2424: typedef Kruskal Create; deba@2424: }; deba@2424: deba@2424: template deba@2424: struct DefTreeMapTraits : public Traits { deba@2424: typedef TM TreeMap; deba@2424: static TreeMap *createTreeMap(const UGraph &) { deba@2424: throw UninitializedParameter(); deba@2424: } deba@2424: }; deba@2424: deba@2424: /// \brief \ref named-templ-param "Named parameter" for setting deba@2424: /// TreeMap deba@2424: /// deba@2424: /// \ref named-templ-param "Named parameter" for setting TreeMap deba@2424: /// deba@2424: template deba@2424: struct DefTreeMap deba@2424: : public Kruskal< UGraph, CostMap, DefTreeMapTraits > { deba@2424: typedef Kruskal< UGraph, CostMap, DefTreeMapTraits > Create; deba@2424: }; deba@2424: deba@2424: deba@2424: private: deba@2424: deba@2424: typedef typename UGraph::Node Node; deba@2424: typedef typename UGraph::NodeIt NodeIt; deba@2424: deba@2424: typedef typename UGraph::UEdge UEdge; deba@2424: typedef typename UGraph::UEdgeIt UEdgeIt; deba@2424: deba@2424: const UGraph& graph; deba@2424: const CostMap& cost; deba@2424: deba@2424: std::vector edges; deba@2424: deba@2424: typedef typename UGraph::template NodeMap UfIndex; deba@2424: typedef UnionFind Uf; deba@2424: UfIndex *ufi; deba@2424: Uf *uf; deba@2424: deba@2424: int index; deba@2424: deba@2424: void initStructures() { deba@2424: if (!_tree) { deba@2424: _tree = Traits::createTreeMap(graph); deba@2424: local_tree = true; deba@2424: } deba@2424: if (!uf) { deba@2424: ufi = new typename UGraph::template NodeMap(graph); deba@2424: uf = new UnionFind >(*ufi); deba@2424: } deba@2424: } deba@2424: deba@2424: void initUnionFind() { deba@2424: uf->clear(); deba@2424: for (NodeIt it(graph); it != INVALID; ++it) { deba@2424: uf->insert(it); deba@2424: } deba@2424: } deba@2424: deba@2424: bool local_tree; deba@2424: TreeMap* _tree; deba@2424: deba@2424: public: deba@2424: deba@2424: /// \brief Constructor deba@2424: /// deba@2424: /// Constructor of the algorithm. deba@2424: Kruskal(const UGraph& _graph, const CostMap& _cost) deba@2424: : graph(_graph), cost(_cost), deba@2424: ufi(0), uf(0), local_tree(false), _tree(0) {} deba@2424: deba@2424: /// \brief Destructor deba@2424: /// deba@2424: /// Destructor deba@2424: ~Kruskal() { deba@2424: if (local_tree) { deba@2424: delete _tree; deba@2424: } deba@2424: if (uf) { deba@2424: delete uf; deba@2424: delete ufi; deba@2424: } deba@2424: } deba@2424: deba@2424: /// \brief Sets the map storing the tree edges. deba@2424: /// deba@2424: /// Sets the map storing the tree edges. deba@2424: /// If you don't use this function before calling \ref run(), deba@2424: /// it will allocate one. The destuctor deallocates this deba@2424: /// automatically allocated map, of course. deba@2424: /// \return \c *this deba@2424: Kruskal& treeMap(TreeMap &m){ deba@2424: if (local_tree) { deba@2424: delete _tree; deba@2424: local_tree = false; deba@2424: } deba@2424: _tree = &m; deba@2424: return *this; deba@2424: } deba@2424: deba@2424: /// \brief Initialize the algorithm deba@2424: /// deba@2424: /// This member function initializes the unionfind data structure deba@2424: /// and sorts the edges into ascending order deba@2424: void init() { deba@2424: initStructures(); deba@2424: initUnionFind(); deba@2424: for (UEdgeIt e(graph); e != INVALID; ++e) { deba@2424: edges.push_back(e); deba@2424: _tree->set(e, false); deba@2424: } deba@2424: Traits::sort(edges.begin(), edges.end(), cost); deba@2424: index = 0; deba@2424: } deba@2424: deba@2424: deba@2424: /// \brief Initialize the algorithm deba@2424: /// deba@2424: /// This member function initializes the unionfind data structure deba@2424: /// and sets the edge order to the given sequence. The given deba@2424: /// sequence should be a valid STL range of undirected edges. deba@2424: template deba@2424: void initPresorted(Iterator begin, Iterator end) { deba@2424: initStructures(); deba@2424: initUnionFind(); deba@2424: edges.clear(); deba@2424: std::copy(begin, end, std::back_inserter(edges)); deba@2424: index = 0; deba@2424: } deba@2424: deba@2424: /// \brief Initialize the algorithm deba@2424: /// deba@2424: /// This member function initializes the unionfind data structure deba@2428: /// and sets the tree to empty. It does not change the order of deba@2428: /// the edges, it uses the order of the previous running. deba@2424: void reinit() { deba@2424: initStructures(); deba@2424: initUnionFind(); deba@2424: for (UEdgeIt e(graph); e != INVALID; ++e) { deba@2424: _tree->set(e, false); deba@2424: } deba@2424: index = 0; deba@2424: } deba@2424: deba@2424: deba@2424: /// \brief Executes the algorithm. deba@2424: /// deba@2424: /// Executes the algorithm. deba@2424: /// deba@2424: /// \pre init() must be called before using this function. deba@2424: /// deba@2424: /// This method runs the %Kruskal algorithm. deba@2424: void start() { deba@2424: while (index < int(edges.size())) { deba@2424: if (uf->join(graph.target(edges[index]), graph.source(edges[index]))) { deba@2424: _tree->set(edges[index], true); deba@2424: } deba@2424: ++index; deba@2424: } deba@2424: } deba@2424: deba@2424: /// \brief Runs the prim algorithm until it find a new tree edge deba@2424: /// deba@2424: /// Runs the prim algorithm until it find a new tree edge. If it deba@2424: /// does not next tree edge in the sequence it gives back \c INVALID. deba@2424: UEdge findNextTreeEdge() { deba@2424: while (index < int(edges.size())) { deba@2424: if (uf->join(graph.target(edges[index]), graph.source(edges[index]))) { deba@2424: _tree->set(edges[index], true); deba@2424: return edges[index++]; deba@2424: } deba@2424: ++index; deba@2424: } deba@2424: return INVALID; deba@2424: } deba@2424: deba@2424: /// \brief Processes the next edge in the sequence deba@2424: /// deba@2424: /// Processes the next edge in the sequence. deba@2424: /// deba@2424: /// \return The prcocessed edge. deba@2424: /// deba@2424: /// \warning The sequence must not be empty! deba@2424: UEdge processNextEdge() { deba@2424: UEdge edge = edges[index++]; deba@2424: processEdge(edge); deba@2424: return edge; deba@2424: } deba@2424: deba@2424: /// \brief Processes an arbitrary edge deba@2424: /// deba@2424: /// Processes the next edge in the sequence. deba@2424: /// deba@2424: /// \return True when the edge is a tree edge. deba@2424: bool processEdge(const UEdge& edge) { deba@2424: if (uf->join(graph.target(edge), graph.source(edge))) { deba@2424: _tree->set(edge, true); deba@2424: return true; deba@2424: } else { deba@2424: return false; deba@2424: } deba@2424: } deba@2424: deba@2424: /// \brief Returns \c false if there are edge to be processed in deba@2424: /// sequence deba@2424: /// deba@2424: /// Returns \c false if there are nodes to be processed in the deba@2424: /// sequence deba@2424: bool emptyQueue() { deba@2424: return index == int(edges.size()); deba@2424: } deba@2424: deba@2424: /// \brief Returns the next edge to be processed deba@2424: /// deba@2424: /// Returns the next edge to be processed deba@2424: /// deba@2424: UEdge nextEdge() const { deba@2424: return edges[index]; deba@2424: } deba@2424: deba@2424: /// \brief Runs %Kruskal algorithm. deba@2424: /// deba@2424: /// This method runs the %Kruskal algorithm in order to compute the deba@2424: /// minimum spanning tree (or minimum spanning forest). The deba@2424: /// method also works on graphs that has more than one components. deba@2424: /// In this case it computes the minimum spanning forest. deba@2424: void run() { deba@2424: init(); deba@2424: start(); deba@2424: } deba@2424: deba@2424: /// \brief Returns a reference to the tree edges map deba@2424: /// deba@2424: /// Returns a reference to the TreeEdgeMap of the edges of the deba@2424: /// minimum spanning tree. The value of the map is \c true only if deba@2424: /// the edge is in the minimum spanning tree. deba@2424: /// deba@2424: const TreeMap &treeMap() const { return *_tree;} deba@2424: deba@2424: /// \brief Returns the total cost of the tree deba@2424: /// deba@2424: /// Returns the total cost of the tree deba@2424: Value treeValue() const { deba@2424: Value value = 0; deba@2424: for (UEdgeIt it(graph); it != INVALID; ++it) { deba@2424: if ((*_tree)[it]) { deba@2424: value += cost[it]; deba@2424: } deba@2424: } deba@2424: return value; deba@2424: } deba@2424: deba@2424: /// \brief Returns true when the given edge is tree edge deba@2424: /// deba@2424: /// Returns true when the given edge is tree edge deba@2424: bool tree(UEdge e) const { deba@2424: return (*_tree)[e]; deba@2424: } deba@2424: deba@2424: deba@2424: }; deba@2424: deba@2424: deba@2424: namespace _kruskal_bits { deba@2424: deba@2424: template deba@2424: typename In::value_type::second_type deba@2424: kruskal(const Graph& graph, const In& in, Out& out) { deba@2424: typedef typename In::value_type::second_type Value; deba@2424: typedef typename Graph::template NodeMap IndexMap; deba@2424: typedef typename Graph::Node Node; deba@2424: deba@2424: IndexMap index(graph); deba@2424: UnionFind uf(index); deba@2424: for (typename Graph::NodeIt it(graph); it != INVALID; ++it) { deba@2424: uf.insert(it); deba@2424: } deba@2424: deba@2424: Value tree_value = 0; deba@2424: for (typename In::const_iterator it = in.begin(); it != in.end(); ++it) { deba@2424: if (uf.join(graph.target(it->first),graph.source(it->first))) { deba@2424: out.set(it->first, true); deba@2424: tree_value += it->second; deba@2424: } deba@2424: else { deba@2424: out.set(it->first, false); deba@2424: } deba@2424: } deba@2424: return tree_value; deba@2424: } deba@2424: deba@2424: deba@2424: template deba@2424: struct PairComp { deba@2424: typedef typename Sequence::value_type Value; deba@2424: bool operator()(const Value& left, const Value& right) { deba@2424: return left.second < right.second; deba@2424: } deba@2424: }; deba@2424: deba@2424: template deba@2424: struct SequenceInputIndicator { deba@2424: static const bool value = false; deba@2424: }; deba@2424: deba@2424: template deba@2424: struct SequenceInputIndicator::type> { deba@2424: static const bool value = true; deba@2424: }; deba@2424: deba@2424: template deba@2424: struct MapInputIndicator { deba@2424: static const bool value = false; deba@2424: }; deba@2424: deba@2424: template deba@2424: struct MapInputIndicator::type> { deba@2424: static const bool value = true; deba@2424: }; deba@2424: deba@2424: template deba@2424: struct SequenceOutputIndicator { deba@2424: static const bool value = false; deba@2424: }; deba@2424: deba@2424: template deba@2424: struct SequenceOutputIndicator::type> { deba@2424: static const bool value = true; deba@2424: }; deba@2424: deba@2424: template deba@2424: struct MapOutputIndicator { deba@2424: static const bool value = false; deba@2424: }; deba@2424: deba@2424: template deba@2424: struct MapOutputIndicator::type> { deba@2424: static const bool value = true; deba@2424: }; deba@2424: deba@2424: template deba@2424: struct KruskalValueSelector {}; deba@2424: deba@2424: template deba@2424: struct KruskalValueSelector, void>::type> deba@2424: { deba@2424: typedef typename In::value_type::second_type Value; deba@2424: }; deba@2424: deba@2424: template deba@2424: struct KruskalValueSelector, void>::type> deba@2424: { deba@2424: typedef typename In::Value Value; deba@2424: }; deba@2424: deba@2424: template deba@2424: struct KruskalInputSelector {}; deba@2424: deba@2424: template deba@2424: struct KruskalOutputSelector {}; deba@2424: deba@2424: template deba@2424: struct KruskalInputSelector, void>::type > deba@2424: { deba@2424: typedef typename In::value_type::second_type Value; deba@2424: deba@2424: static Value kruskal(const Graph& graph, const In& in, Out& out) { deba@2424: return KruskalOutputSelector:: deba@2424: kruskal(graph, in, out); deba@2424: } deba@2424: deba@2424: }; deba@2424: deba@2424: template deba@2424: struct KruskalInputSelector, void>::type > deba@2424: { deba@2424: typedef typename In::Value Value; deba@2424: static Value kruskal(const Graph& graph, const In& in, Out& out) { deba@2424: typedef typename In::Key MapEdge; deba@2424: typedef typename In::Value Value; deba@2424: typedef typename ItemSetTraits::ItemIt MapEdgeIt; deba@2424: typedef std::vector > Sequence; deba@2424: Sequence seq; deba@2424: deba@2424: for (MapEdgeIt it(graph); it != INVALID; ++it) { ladanyi@2431: seq.push_back(std::make_pair(it, in[it])); deba@2424: } deba@2424: deba@2424: std::sort(seq.begin(), seq.end(), PairComp()); deba@2424: return KruskalOutputSelector:: deba@2424: kruskal(graph, seq, out); deba@2424: } deba@2424: }; deba@2424: deba@2424: template deba@2424: struct KruskalOutputSelector, void>::type > deba@2424: { deba@2424: typedef typename In::value_type::second_type Value; deba@2424: deba@2424: static Value kruskal(const Graph& graph, const In& in, Out& out) { deba@2424: typedef StoreBoolMap Map; deba@2424: Map map(out); deba@2424: return _kruskal_bits::kruskal(graph, in, map); deba@2424: } deba@2424: deba@2424: }; deba@2424: deba@2424: template deba@2424: struct KruskalOutputSelector, void>::type > deba@2424: { deba@2424: typedef typename In::value_type::second_type Value; deba@2424: deba@2424: static Value kruskal(const Graph& graph, const In& in, Out& out) { deba@2424: return _kruskal_bits::kruskal(graph, in, out); deba@2424: } deba@2424: }; deba@2424: deba@2424: } deba@2424: deba@2424: /// \ingroup spantree deba@2424: /// deba@2424: /// \brief Kruskal's algorithm to find a minimum cost tree of a graph. deba@2424: /// alpar@810: /// This function runs Kruskal's algorithm to find a minimum cost tree. alpar@1557: /// Due to hard C++ hacking, it accepts various input and output types. alpar@1557: /// alpar@1555: /// \param g The graph the algorithm runs on. alpar@2260: /// It can be either \ref concepts::Graph "directed" or alpar@2260: /// \ref concepts::UGraph "undirected". alpar@1555: /// If the graph is directed, the algorithm consider it to be alpar@1555: /// undirected by disregarding the direction of the edges. alpar@810: /// alpar@1557: /// \param in This object is used to describe the edge costs. It can be one alpar@1557: /// of the following choices. deba@2424: /// deba@2424: /// - An STL compatible 'Forward Container' with deba@2424: /// std::pair or deba@2424: /// std::pair as its value_type, where deba@2424: /// \c X is the type of the costs. The pairs indicates the edges deba@2424: /// along with the assigned cost. They must be in a alpar@1557: /// cost-ascending order. alpar@1557: /// - Any readable Edge map. The values of the map indicate the edge costs. alpar@810: /// alpar@1557: /// \retval out Here we also have a choise. deba@2424: /// - It can be a writable \c bool edge map. After running the deba@2424: /// algorithm this will contain the found minimum cost spanning deba@2424: /// tree: the value of an edge will be set to \c true if it belongs deba@2424: /// to the tree, otherwise it will be set to \c false. The value of deba@2424: /// each edge will be set exactly once. alpar@1557: /// - It can also be an iteraror of an STL Container with deba@2424: /// GR::UEdge or GR::Edge as its deba@2424: /// value_type. The algorithm copies the elements of the deba@2424: /// found tree into this sequence. For example, if we know that the deba@2424: /// spanning tree of the graph \c g has say 53 edges, then we can deba@2424: /// put its edges into an STL vector \c tree with a code like this. alpar@1946: ///\code alpar@1557: /// std::vector tree(53); alpar@1557: /// kruskal(g,cost,tree.begin()); alpar@1946: ///\endcode deba@2424: /// Or if we don't know in advance the size of the tree, we can deba@2424: /// write this. deba@2424: ///\code std::vector tree; deba@2424: /// kruskal(g,cost,std::back_inserter(tree)); alpar@1946: ///\endcode alpar@810: /// deba@2424: /// \return The total cost of the found tree. alpar@1449: /// deba@2424: /// \warning If kruskal runs on an be consistent of using the same deba@2424: /// Edge type for input and output. alpar@1603: /// alpar@810: alpar@1557: #ifdef DOXYGEN deba@2424: template deba@2424: Value kruskal(GR const& g, const In& in, Out& out) deba@2424: #else deba@2424: template deba@2424: inline typename _kruskal_bits::KruskalValueSelector::Value deba@2424: kruskal(const Graph& graph, const In& in, Out& out) alpar@1557: #endif alpar@810: { deba@2424: return _kruskal_bits::KruskalInputSelector:: deba@2424: kruskal(graph, in, out); alpar@810: } alpar@810: alpar@1557: alpar@810: klao@885: deba@2424: template deba@2424: inline typename _kruskal_bits::KruskalValueSelector::Value deba@2424: kruskal(const Graph& graph, const In& in, const Out& out) alpar@1557: { deba@2424: return _kruskal_bits::KruskalInputSelector:: deba@2424: kruskal(graph, in, out); deba@2424: } alpar@810: alpar@921: } //namespace lemon alpar@810: alpar@921: #endif //LEMON_KRUSKAL_H