beckerjc@150: // -*- c++ -*- // beckerjc@150: #ifndef HUGO_KRUSKAL_H beckerjc@150: #define HUGO_KRUSKAL_H beckerjc@150: beckerjc@150: #include beckerjc@349: #include beckerjc@349: #include beckerjc@150: beckerjc@150: namespace hugo { beckerjc@150: beckerjc@349: /// Kruskal's algorithm to compute a minimum cost tree beckerjc@150: beckerjc@349: template beckerjc@349: typename InputEdgeOrder::ValueType beckerjc@349: Kruskal(Graph const& G, InputEdgeOrder const& edges, beckerjc@349: OutBoolMap& out_map) beckerjc@349: { beckerjc@349: typedef typename InputEdgeOrder::ValueType EdgeCost; beckerjc@349: typedef typename Graph::NodeMap NodeIntMap; beckerjc@349: typedef typename Graph::Node Node; beckerjc@246: beckerjc@349: NodeIntMap comp_map(G, -1); beckerjc@349: UnionFind uf(comp_map); beckerjc@349: beckerjc@349: EdgeCost tot_cost = 0; beckerjc@349: for (typename InputEdgeOrder::const_iterator p = edges.begin(); beckerjc@349: p!=edges.end(); ++p ) { beckerjc@349: if ( uf.joinComponents(G.head(edges.first(p)), beckerjc@349: G.tail(edges.first(p))) ) { beckerjc@349: out_map.set(edges.first(p), true); beckerjc@349: tot_cost += edges.second(p); beckerjc@349: } beckerjc@349: else { beckerjc@349: out_map.set(edges.first(p), false); beckerjc@349: } beckerjc@349: } beckerjc@349: return tot_cost; beckerjc@349: } beckerjc@246: beckerjc@352: /* A work-around for running Kruskal with const-reference bool maps... */ beckerjc@352: beckerjc@352: template beckerjc@352: class NonConstMapWr { beckerjc@352: const Map &m; beckerjc@352: public: beckerjc@352: typedef typename Map::ValueType ValueType; beckerjc@352: beckerjc@352: NonConstMapWr(const Map &_m) : m(_m) {} beckerjc@352: beckerjc@352: template beckerjc@352: void set(KeyType const& k, ValueType const &v) const { m.set(k,v); } beckerjc@352: }; beckerjc@352: beckerjc@352: template beckerjc@352: inline beckerjc@352: typename InputEdgeOrder::ValueType beckerjc@352: Kruskal(Graph const& G, InputEdgeOrder const& edges, beckerjc@352: OutBoolMap const& out_map) beckerjc@352: { beckerjc@352: NonConstMapWr map_wr(out_map); beckerjc@352: return Kruskal(G, edges, map_wr); beckerjc@352: } beckerjc@246: beckerjc@349: beckerjc@349: /* ** ** Output-objektumok: egyszeruen extra bool mapek ** ** */ beckerjc@349: beckerjc@349: /// A writable bool-map that makes a sequence of "true" keys beckerjc@246: beckerjc@349: /// A writable bool-map that creates a sequence out of keys that receive beckerjc@349: /// the value "true". beckerjc@349: /// \warning Not a regular property map, as it doesn't know its KeyType beckerjc@246: beckerjc@349: template beckerjc@349: class SequenceOutput { beckerjc@352: mutable Iterator it; beckerjc@150: beckerjc@218: public: beckerjc@349: typedef bool ValueType; beckerjc@150: beckerjc@349: SequenceOutput(Iterator const &_it) : it(_it) {} beckerjc@150: beckerjc@349: template beckerjc@352: void set(KeyType const& k, bool v) const { if(v) {*it=k; ++it;} } beckerjc@218: }; beckerjc@150: beckerjc@349: template beckerjc@349: inline beckerjc@349: SequenceOutput beckerjc@349: makeSequenceOutput(Iterator it) { beckerjc@349: return SequenceOutput(it); beckerjc@349: } beckerjc@246: beckerjc@246: /* ** ** InputSource -ok ** ** */ beckerjc@246: beckerjc@246: template beckerjc@349: class KruskalPairVec : public std::vector< std::pair > { beckerjc@246: beckerjc@246: public: beckerjc@246: typedef std::vector< std::pair > Parent; beckerjc@246: typedef Key KeyType; beckerjc@246: typedef Val ValueType; beckerjc@246: typedef std::pair PairType; beckerjc@246: beckerjc@246: typedef typename Parent::iterator iterator; beckerjc@246: typedef typename Parent::const_iterator const_iterator; beckerjc@246: beckerjc@246: private: beckerjc@246: class comparePair { beckerjc@246: public: beckerjc@246: bool operator()(PairType const& a, PairType const& b) { beckerjc@246: return a.second < b.second; beckerjc@246: } beckerjc@246: }; beckerjc@246: beckerjc@246: public: beckerjc@246: beckerjc@246: // FIXME: kell ez? beckerjc@349: // KruskalPairVec(Parent const& p) : Parent(p) {} beckerjc@246: beckerjc@246: void sort() { beckerjc@246: std::sort(begin(), end(), comparePair()); beckerjc@246: } beckerjc@246: beckerjc@246: // FIXME: nem nagyon illik ez ide... beckerjc@246: template beckerjc@349: KruskalPairVec(Graph const& G, Map const& m) { beckerjc@246: typedef typename Graph::EdgeIt EdgeIt; beckerjc@246: beckerjc@246: clear(); beckerjc@349: FOR_EACH_LOC(EdgeIt, e, G) { beckerjc@349: // for (EdgeIt e=G.template first(); G.valid(e); G.next(e)) { beckerjc@246: push_back(make_pair(e, m[e])); beckerjc@246: } beckerjc@246: sort(); beckerjc@246: } beckerjc@246: beckerjc@246: Key const& first(const_iterator i) const { return i->first; } beckerjc@246: Key& first(iterator i) { return i->first; } beckerjc@246: beckerjc@246: Val const& second(const_iterator i) const { return i->second; } beckerjc@246: Val& second(iterator i) { return i->second; } beckerjc@246: }; beckerjc@246: beckerjc@349: beckerjc@349: template beckerjc@349: class KruskalMapVec : public std::vector { beckerjc@349: public: beckerjc@349: beckerjc@349: typedef typename Map::KeyType KeyType; beckerjc@349: typedef typename Map::ValueType ValueType; beckerjc@349: beckerjc@349: typedef typename std::vector Parent; beckerjc@349: typedef typename Parent::iterator iterator; beckerjc@349: typedef typename Parent::const_iterator const_iterator; beckerjc@349: beckerjc@349: private: beckerjc@349: beckerjc@349: const Map &m; beckerjc@349: beckerjc@349: class compareKeys { beckerjc@349: const Map &m; beckerjc@349: public: beckerjc@349: compareKeys(Map const &_m) : m(_m) {} beckerjc@349: bool operator()(KeyType const& a, KeyType const& b) { beckerjc@349: return m[a] < m[b]; beckerjc@349: } beckerjc@349: }; beckerjc@349: beckerjc@349: public: beckerjc@349: beckerjc@349: KruskalMapVec(Map const& _m) : m(_m) {} beckerjc@349: beckerjc@349: void sort() { beckerjc@349: std::sort(begin(), end(), compareKeys(m)); beckerjc@349: } beckerjc@349: beckerjc@349: // FIXME: nem nagyon illik ez ide... beckerjc@349: template beckerjc@349: KruskalMapVec(Graph const& G, Map const& _m) : m(_m) { beckerjc@349: typedef typename Graph::EdgeIt EdgeIt; beckerjc@349: beckerjc@349: clear(); beckerjc@349: FOR_EACH_LOC(EdgeIt, e, G) { beckerjc@349: // for (EdgeIt e=G.template first(); G.valid(e); G.next(e)) { beckerjc@349: push_back(e); beckerjc@349: } beckerjc@349: sort(); beckerjc@349: } beckerjc@349: beckerjc@349: KeyType const& first(const_iterator i) const { return *i; } beckerjc@349: KeyType& first(iterator i) { return *i; } beckerjc@349: beckerjc@349: ValueType const& second(const_iterator i) const { return m[*i]; } beckerjc@349: ValueType& second(iterator i) { return m[*i]; } beckerjc@349: }; beckerjc@349: beckerjc@246: /* ** ** Wrapper fuggvenyek ** ** */ beckerjc@246: beckerjc@349: beckerjc@349: /// \brief Wrapper to Kruskal(). beckerjc@349: /// Input is from an EdgeMap, output is a plain boolmap. beckerjc@246: template beckerjc@352: inline beckerjc@246: typename EdgeCostMap::ValueType beckerjc@349: Kruskal_EdgeCostMapIn_BoolMapOut(Graph const& G, beckerjc@349: EdgeCostMap const& edge_costs, beckerjc@349: RetEdgeBoolMap &ret_bool_map) { beckerjc@246: beckerjc@349: typedef KruskalPairVec beckerjc@246: InputVec; beckerjc@349: InputVec iv(G, edge_costs); beckerjc@246: beckerjc@349: return Kruskal(G, iv, ret_bool_map); beckerjc@246: } beckerjc@246: beckerjc@349: beckerjc@349: /// \brief Wrapper to Kruskal(). beckerjc@349: /// Input is from an EdgeMap, output is to a sequence. beckerjc@246: template beckerjc@352: inline beckerjc@246: typename EdgeCostMap::ValueType beckerjc@349: Kruskal_EdgeCostMapIn_IteratorOut(Graph const& G, beckerjc@349: EdgeCostMap const& edge_costs, beckerjc@349: RetIterator ret_iterator) { beckerjc@349: typedef SequenceOutput OutMap; beckerjc@349: OutMap out(ret_iterator); beckerjc@246: beckerjc@349: typedef KruskalPairVec beckerjc@246: InputVec; beckerjc@349: InputVec iv(G, edge_costs); beckerjc@246: beckerjc@349: return Kruskal(G, iv, out); beckerjc@246: } beckerjc@246: beckerjc@150: beckerjc@150: } //namespace hugo beckerjc@150: beckerjc@150: #endif //HUGO_KRUSKAL_H