equal
deleted
inserted
replaced
35 } |
35 } |
36 } |
36 } |
37 return tot_cost; |
37 return tot_cost; |
38 } |
38 } |
39 |
39 |
|
40 /* A work-around for running Kruskal with const-reference bool maps... */ |
|
41 |
|
42 template<typename Map> |
|
43 class NonConstMapWr { |
|
44 const Map &m; |
|
45 public: |
|
46 typedef typename Map::ValueType ValueType; |
|
47 |
|
48 NonConstMapWr(const Map &_m) : m(_m) {} |
|
49 |
|
50 template<typename KeyType> |
|
51 void set(KeyType const& k, ValueType const &v) const { m.set(k,v); } |
|
52 }; |
|
53 |
|
54 template <typename Graph, typename InputEdgeOrder, typename OutBoolMap> |
|
55 inline |
|
56 typename InputEdgeOrder::ValueType |
|
57 Kruskal(Graph const& G, InputEdgeOrder const& edges, |
|
58 OutBoolMap const& out_map) |
|
59 { |
|
60 NonConstMapWr<OutBoolMap> map_wr(out_map); |
|
61 return Kruskal(G, edges, map_wr); |
|
62 } |
40 |
63 |
41 |
64 |
42 /* ** ** Output-objektumok: egyszeruen extra bool mapek ** ** */ |
65 /* ** ** Output-objektumok: egyszeruen extra bool mapek ** ** */ |
43 |
66 |
44 /// A writable bool-map that makes a sequence of "true" keys |
67 /// A writable bool-map that makes a sequence of "true" keys |
47 /// the value "true". |
70 /// the value "true". |
48 /// \warning Not a regular property map, as it doesn't know its KeyType |
71 /// \warning Not a regular property map, as it doesn't know its KeyType |
49 |
72 |
50 template<typename Iterator> |
73 template<typename Iterator> |
51 class SequenceOutput { |
74 class SequenceOutput { |
52 Iterator it; |
75 mutable Iterator it; |
53 |
76 |
54 public: |
77 public: |
55 typedef bool ValueType; |
78 typedef bool ValueType; |
56 |
79 |
57 SequenceOutput(Iterator const &_it) : it(_it) {} |
80 SequenceOutput(Iterator const &_it) : it(_it) {} |
58 |
81 |
59 template<typename KeyType> |
82 template<typename KeyType> |
60 void set(KeyType const& k, bool v) { if(v) {*it=k; ++it;} } |
83 void set(KeyType const& k, bool v) const { if(v) {*it=k; ++it;} } |
61 }; |
84 }; |
62 |
85 |
63 template<typename Iterator> |
86 template<typename Iterator> |
64 inline |
87 inline |
65 SequenceOutput<Iterator> |
88 SequenceOutput<Iterator> |
175 |
198 |
176 |
199 |
177 /// \brief Wrapper to Kruskal(). |
200 /// \brief Wrapper to Kruskal(). |
178 /// Input is from an EdgeMap, output is a plain boolmap. |
201 /// Input is from an EdgeMap, output is a plain boolmap. |
179 template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap> |
202 template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap> |
|
203 inline |
180 typename EdgeCostMap::ValueType |
204 typename EdgeCostMap::ValueType |
181 Kruskal_EdgeCostMapIn_BoolMapOut(Graph const& G, |
205 Kruskal_EdgeCostMapIn_BoolMapOut(Graph const& G, |
182 EdgeCostMap const& edge_costs, |
206 EdgeCostMap const& edge_costs, |
183 RetEdgeBoolMap &ret_bool_map) { |
207 RetEdgeBoolMap &ret_bool_map) { |
184 |
208 |
191 |
215 |
192 |
216 |
193 /// \brief Wrapper to Kruskal(). |
217 /// \brief Wrapper to Kruskal(). |
194 /// Input is from an EdgeMap, output is to a sequence. |
218 /// Input is from an EdgeMap, output is to a sequence. |
195 template <typename Graph, typename EdgeCostMap, typename RetIterator> |
219 template <typename Graph, typename EdgeCostMap, typename RetIterator> |
|
220 inline |
196 typename EdgeCostMap::ValueType |
221 typename EdgeCostMap::ValueType |
197 Kruskal_EdgeCostMapIn_IteratorOut(Graph const& G, |
222 Kruskal_EdgeCostMapIn_IteratorOut(Graph const& G, |
198 EdgeCostMap const& edge_costs, |
223 EdgeCostMap const& edge_costs, |
199 RetIterator ret_iterator) { |
224 RetIterator ret_iterator) { |
200 typedef SequenceOutput<RetIterator> OutMap; |
225 typedef SequenceOutput<RetIterator> OutMap; |