The new for macros are: h_for, h_for_inc, h_for_glob, h_for_inc_glob.
7 #include <for_each_macros.h>
11 /// Kruskal's algorithm to compute a minimum cost tree
13 template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
14 typename InputEdgeOrder::ValueType
15 Kruskal(Graph const& G, InputEdgeOrder const& edges,
18 typedef typename InputEdgeOrder::ValueType EdgeCost;
19 typedef typename Graph::NodeMap<int> NodeIntMap;
20 typedef typename Graph::Node Node;
22 NodeIntMap comp_map(G, -1);
23 UnionFind<Node,NodeIntMap> uf(comp_map);
25 EdgeCost tot_cost = 0;
26 for (typename InputEdgeOrder::const_iterator p = edges.begin();
27 p!=edges.end(); ++p ) {
28 if ( uf.join(G.head(edges.first(p)),
29 G.tail(edges.first(p))) ) {
30 out_map.set(edges.first(p), true);
31 tot_cost += edges.second(p);
34 out_map.set(edges.first(p), false);
40 /* A work-around for running Kruskal with const-reference bool maps... */
42 template<typename Map>
46 typedef typename Map::ValueType ValueType;
48 NonConstMapWr(const Map &_m) : m(_m) {}
50 template<typename KeyType>
51 void set(KeyType const& k, ValueType const &v) const { m.set(k,v); }
54 template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
56 typename InputEdgeOrder::ValueType
57 Kruskal(Graph const& G, InputEdgeOrder const& edges,
58 OutBoolMap const& out_map)
60 NonConstMapWr<OutBoolMap> map_wr(out_map);
61 return Kruskal(G, edges, map_wr);
65 /* ** ** Output-objektumok: egyszeruen extra bool mapek ** ** */
67 /// A writable bool-map that makes a sequence of "true" keys
69 /// A writable bool-map that creates a sequence out of keys that receive
71 /// \warning Not a regular property map, as it doesn't know its KeyType
73 template<typename Iterator>
74 class SequenceOutput {
78 typedef bool ValueType;
80 SequenceOutput(Iterator const &_it) : it(_it) {}
82 template<typename KeyType>
83 void set(KeyType const& k, bool v) const { if(v) {*it=k; ++it;} }
86 template<typename Iterator>
88 SequenceOutput<Iterator>
89 makeSequenceOutput(Iterator it) {
90 return SequenceOutput<Iterator>(it);
93 /* ** ** InputSource -ok ** ** */
95 template<typename Key, typename Val>
96 class KruskalPairVec : public std::vector< std::pair<Key,Val> > {
99 typedef std::vector< std::pair<Key,Val> > Parent;
101 typedef Val ValueType;
102 typedef std::pair<Key,Val> PairType;
104 typedef typename Parent::iterator iterator;
105 typedef typename Parent::const_iterator const_iterator;
110 bool operator()(PairType const& a, PairType const& b) {
111 return a.second < b.second;
118 // KruskalPairVec(Parent const& p) : Parent(p) {}
121 std::sort(begin(), end(), comparePair());
124 // FIXME: nem nagyon illik ez ide...
125 template<typename Graph, typename Map>
126 KruskalPairVec(Graph const& G, Map const& m) {
127 typedef typename Graph::EdgeIt EdgeIt;
130 FOR_EACH_LOC(EdgeIt, e, G) {
131 // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
132 push_back(make_pair(e, m[e]));
137 Key const& first(const_iterator i) const { return i->first; }
138 Key& first(iterator i) { return i->first; }
140 Val const& second(const_iterator i) const { return i->second; }
141 Val& second(iterator i) { return i->second; }
145 template <typename Map>
146 class KruskalMapVec : public std::vector<typename Map::KeyType> {
149 typedef typename Map::KeyType KeyType;
150 typedef typename Map::ValueType ValueType;
152 typedef typename std::vector<KeyType> Parent;
153 typedef typename Parent::iterator iterator;
154 typedef typename Parent::const_iterator const_iterator;
163 compareKeys(Map const &_m) : m(_m) {}
164 bool operator()(KeyType const& a, KeyType const& b) {
171 KruskalMapVec(Map const& _m) : m(_m) {}
174 std::sort(begin(), end(), compareKeys(m));
177 // FIXME: nem nagyon illik ez ide...
178 template<typename Graph>
179 KruskalMapVec(Graph const& G, Map const& _m) : m(_m) {
180 typedef typename Graph::EdgeIt EdgeIt;
183 FOR_EACH_LOC(EdgeIt, e, G) {
184 // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
190 KeyType const& first(const_iterator i) const { return *i; }
191 KeyType& first(iterator i) { return *i; }
193 ValueType const& second(const_iterator i) const { return m[*i]; }
194 ValueType& second(iterator i) { return m[*i]; }
197 /* ** ** Wrapper fuggvenyek ** ** */
200 /// \brief Wrapper to Kruskal().
201 /// Input is from an EdgeMap, output is a plain boolmap.
202 template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
204 typename EdgeCostMap::ValueType
205 Kruskal_EdgeCostMapIn_BoolMapOut(Graph const& G,
206 EdgeCostMap const& edge_costs,
207 RetEdgeBoolMap &ret_bool_map) {
209 typedef KruskalPairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
211 InputVec iv(G, edge_costs);
213 return Kruskal(G, iv, ret_bool_map);
217 /// \brief Wrapper to Kruskal().
218 /// Input is from an EdgeMap, output is to a sequence.
219 template <typename Graph, typename EdgeCostMap, typename RetIterator>
221 typename EdgeCostMap::ValueType
222 Kruskal_EdgeCostMapIn_IteratorOut(Graph const& G,
223 EdgeCostMap const& edge_costs,
224 RetIterator ret_iterator) {
225 typedef SequenceOutput<RetIterator> OutMap;
226 OutMap out(ret_iterator);
228 typedef KruskalPairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
230 InputVec iv(G, edge_costs);
232 return Kruskal(G, iv, out);
238 #endif //HUGO_KRUSKAL_H