10 template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
11 typename EdgeCostMap::ValueType
12 kruskal1(Graph const& G, EdgeCostMap const& edge_costs,
13 RetEdgeBoolMap &ret_bool_map);
15 template <typename Graph, typename EdgeCostMap, typename RetIterator>
16 typename EdgeCostMap::ValueType
17 kruskal2(Graph const& G, EdgeCostMap const& edge_costs,
18 RetIterator ret_iterator);
20 // FIXME: ret_iterator nem lehet referencia!!!
22 template <typename Graph, typename EdgeCostPairVec, typename RetEdgeBoolMap>
23 typename EdgeCostPairVec::value_type::second_type
24 kruskal3(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec,
25 RetEdgeBoolMap &ret_bool_map);
27 template <typename Graph, typename EdgeCostPairVec, typename RetIterator>
28 typename EdgeCostPairVec::value_type::second_type
29 kruskal4(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec,
30 RetIterator &ret_iterator);
32 template <typename Graph, typename EdgePairVec, typename RetEdgeBoolMap>
34 kruskal5(Graph const& G, EdgePairVec const& edge_pair_vec,
35 RetEdgeBoolMap &ret_bool_map);
37 template <typename Graph, typename EdgePairVec, typename RetIterator>
39 kruskal6(Graph const& G, EdgePairVec const& edge_pair_vec,
40 RetIterator &ret_iterator);
43 template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap,
45 typename EdgeCostMap::ValueType
46 kruskal7(Graph const& G, EdgeCostMap const& edge_costs,
47 RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator);
49 template <typename Graph, typename EdgeCostPairVec, typename RetEdgeBoolMap,
51 typename EdgeCostPairVec::value_type::second_type
52 kruskal8(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec,
53 RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator);
55 template <typename Graph, typename EdgePairVec, typename RetEdgeBoolMap,
58 kruskal9(Graph const& G, EdgePairVec const& edge_pair_vec,
59 RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator);
64 template <typename Graph, typename InputEdgeOrder, typename OutputObserver>
65 class MinCostTreeKruskal
68 typedef typename Graph::EdgeIt EdgeIt;
69 typedef typename Graph::Edge Edge;
72 typedef typename InputEdgeOrder::ValueType EdgeCost;
76 InputEdgeOrder const &edges;
77 OutputObserver &out_obs;
82 MinCostTreeKruskal(Graph const& _G, InputEdgeOrder const& _edges,
83 OutputObserver& _out_obs) :
84 G(_G), edges(_edges), out_obs(_out_obs) {}
89 typedef typename Graph::NodeMap<int> NodeIntMap;
90 typedef typename Graph::Node Node;
91 NodeIntMap comp_map(G, -1);
92 UnionFind<Node,NodeIntMap> uf(comp_map);
94 EdgeCost tot_cost = 0;
95 for (typename InputEdgeOrder::const_iterator p = edges.begin();
96 p!=edges.end(); ++p ) {
97 if ( uf.joinComponents(G.head(edges.first(p)),
98 G.tail(edges.first(p))) ) {
99 out_obs.setTrue(edges.first(p));
100 tot_cost += edges.second(p);
103 out_obs.setFalse(edges.first(p));
112 /* ** ** Output-objektumok (Observerek (?)) ** ** */
114 template <typename BoolMap>
115 class BoolMapOutput {
117 typedef typename BoolMap::KeyType KeyType;
120 BoolMapOutput(BoolMap &_bm) : bm(_bm) {}
122 void setTrue(KeyType const& k) { bm.set(k, true); }
123 void setFalse(KeyType const& k) { bm.set(k, false); }
126 template <typename Iterator>
127 class SequenceOutput {
131 SequenceOutput(Iterator &_it) : it(_it) {}
133 template<typename KeyType>
134 void setTrue(KeyType const& k) { *it=k; ++it; }
135 template<typename KeyType>
136 void setFalse(KeyType const& k) {}
139 template <typename BoolMap, typename Iterator>
140 class CombinedOutput : BoolMapOutput<BoolMap>, SequenceOutput<Iterator> {
141 typedef BoolMapOutput<BoolMap> BMO;
142 typedef SequenceOutput<Iterator> SO;
144 CombinedOutput(BoolMap &_bm, Iterator &_it) :
147 template<typename KeyType>
148 void setTrue(KeyType const& k) {
152 template<typename KeyType>
153 void setFalse(KeyType const& k) {
160 /* ** ** InputSource -ok ** ** */
162 template<typename Key, typename Val>
163 class PairVec : public std::vector< std::pair<Key,Val> > {
166 typedef std::vector< std::pair<Key,Val> > Parent;
168 typedef Val ValueType;
169 typedef std::pair<Key,Val> PairType;
171 typedef typename Parent::iterator iterator;
172 typedef typename Parent::const_iterator const_iterator;
179 bool operator()(PairType const& a, PairType const& b) {
180 return a.second < b.second;
187 // PairVec(Parent const& p) : Parent(p) {}
190 std::sort(begin(), end(), comparePair());
193 // FIXME: nem nagyon illik ez ide...
194 template<typename Graph, typename Map>
195 void readGraphEdgeMap(Graph const& G, Map const& m) {
196 typedef typename Graph::EdgeIt EdgeIt;
199 for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
200 push_back(make_pair(e, m[e]));
206 int alma() { return 5; /* FIXME */ }
208 Key const& first(const_iterator i) const { return i->first; }
209 Key& first(iterator i) { return i->first; }
211 Val const& second(const_iterator i) const { return i->second; }
212 Val& second(iterator i) { return i->second; }
215 /* ** ** Wrapper fuggvenyek ** ** */
217 template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
218 typename EdgeCostMap::ValueType
219 kruskal1(Graph const& G, EdgeCostMap const& edge_costs,
220 RetEdgeBoolMap &ret_bool_map) {
221 typedef BoolMapOutput<RetEdgeBoolMap> OutObs;
222 OutObs out(ret_bool_map);
224 typedef PairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
227 iv.readGraphEdgeMap(G, edge_costs);
229 MinCostTreeKruskal<Graph,InputVec,OutObs> mctk(G, iv, out);
233 template <typename Graph, typename EdgeCostMap, typename RetIterator>
234 typename EdgeCostMap::ValueType
235 kruskal2(Graph const& G, EdgeCostMap const& edge_costs,
236 RetIterator ret_iterator) {
237 typedef SequenceOutput<RetIterator> OutObs;
238 OutObs out(ret_iterator);
240 typedef PairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
243 iv.readGraphEdgeMap(G, edge_costs);
245 MinCostTreeKruskal<Graph,InputVec,OutObs> mctk(G, iv, out);
252 #endif //HUGO_KRUSKAL_H