Changeset 349:42c660f58702 in lemon0.x
 Timestamp:
 04/17/04 21:19:57 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@468
 Location:
 src/work/johanna
 Files:

 3 edited
Legend:
 Unmodified
 Added
 Removed

src/work/johanna/kruskal.h
r246 r349 3 3 #define HUGO_KRUSKAL_H 4 4 5 #include "unionfind.h"6 5 #include <algorithm> 6 #include <unionfind.h> 7 #include <for_each_macros.h> 7 8 8 9 namespace hugo { 9 10 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); 14 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); 19 20 // FIXME: ret_iterator nem lehet referencia!!! 21 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); 26 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); 31 32 template <typename Graph, typename EdgePairVec, typename RetEdgeBoolMap> 33 int 34 kruskal5(Graph const& G, EdgePairVec const& edge_pair_vec, 35 RetEdgeBoolMap &ret_bool_map); 36 37 template <typename Graph, typename EdgePairVec, typename RetIterator> 38 int 39 kruskal6(Graph const& G, EdgePairVec const& edge_pair_vec, 40 RetIterator &ret_iterator); 41 42 43 template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap, 44 typename RetIterator> 45 typename EdgeCostMap::ValueType 46 kruskal7(Graph const& G, EdgeCostMap const& edge_costs, 47 RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator); 48 49 template <typename Graph, typename EdgeCostPairVec, typename RetEdgeBoolMap, 50 typename RetIterator> 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); 54 55 template <typename Graph, typename EdgePairVec, typename RetEdgeBoolMap, 56 typename RetIterator> 57 int 58 kruskal9(Graph const& G, EdgePairVec const& edge_pair_vec, 59 RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator); 60 61 62 63 64 template <typename Graph, typename InputEdgeOrder, typename OutputObserver> 65 class MinCostTreeKruskal 11 /// Kruskal's algorithm to compute a minimum cost tree 12 13 template <typename Graph, typename InputEdgeOrder, typename OutBoolMap> 14 typename InputEdgeOrder::ValueType 15 Kruskal(Graph const& G, InputEdgeOrder const& edges, 16 OutBoolMap& out_map) 66 17 { 67 68 typedef typename Graph::EdgeIt EdgeIt;69 typedef typename Graph::Edge Edge;70 71 public:72 18 typedef typename InputEdgeOrder::ValueType EdgeCost; 73 74 private: 75 Graph const &G; 76 InputEdgeOrder const &edges; 77 OutputObserver &out_obs; 78 79 public: 80 81 82 MinCostTreeKruskal(Graph const& _G, InputEdgeOrder const& _edges, 83 OutputObserver& _out_obs) : 84 G(_G), edges(_edges), out_obs(_out_obs) {} 19 typedef typename Graph::NodeMap<int> NodeIntMap; 20 typedef typename Graph::Node Node; 21 22 NodeIntMap comp_map(G, 1); 23 UnionFind<Node,NodeIntMap> uf(comp_map); 24 25 EdgeCost tot_cost = 0; 26 for (typename InputEdgeOrder::const_iterator p = edges.begin(); 27 p!=edges.end(); ++p ) { 28 if ( uf.joinComponents(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); 32 } 33 else { 34 out_map.set(edges.first(p), false); 35 } 36 } 37 return tot_cost; 38 } 39 40 85 41 86 87 EdgeCost run() 88 { 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); 93 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); 101 } 102 else { 103 out_obs.setFalse(edges.first(p)); 104 } 105 } 106 return tot_cost; 107 } 108 42 /* ** ** Outputobjektumok: egyszeruen extra bool mapek ** ** */ 43 44 /// A writable boolmap that makes a sequence of "true" keys 45 46 /// A writable boolmap that creates a sequence out of keys that receive 47 /// the value "true". 48 /// \warning Not a regular property map, as it doesn't know its KeyType 49 50 template<typename Iterator> 51 class SequenceOutput { 52 Iterator it; 53 54 public: 55 typedef bool ValueType; 56 57 SequenceOutput(Iterator const &_it) : it(_it) {} 58 59 template<typename KeyType> 60 void set(KeyType const& k, bool v) { if(v) {*it=k; ++it;} } 109 61 }; 110 62 111 112 /* ** ** Outputobjektumok (Observerek (?)) ** ** */ 113 114 template <typename BoolMap> 115 class BoolMapOutput { 116 BoolMap &bm; 117 typedef typename BoolMap::KeyType KeyType; 118 119 public: 120 BoolMapOutput(BoolMap &_bm) : bm(_bm) {} 121 122 void setTrue(KeyType const& k) { bm.set(k, true); } 123 void setFalse(KeyType const& k) { bm.set(k, false); } 124 }; 125 126 template <typename Iterator> 127 class SequenceOutput { 128 Iterator ⁢ 129 130 public: 131 SequenceOutput(Iterator &_it) : it(_it) {} 132 133 template<typename KeyType> 134 void setTrue(KeyType const& k) { *it=k; ++it; } 135 template<typename KeyType> 136 void setFalse(KeyType const& k) {} 137 }; 138 139 template <typename BoolMap, typename Iterator> 140 class CombinedOutput : BoolMapOutput<BoolMap>, SequenceOutput<Iterator> { 141 typedef BoolMapOutput<BoolMap> BMO; 142 typedef SequenceOutput<Iterator> SO; 143 public: 144 CombinedOutput(BoolMap &_bm, Iterator &_it) : 145 BMO(_bm), SO(_it) {} 146 147 template<typename KeyType> 148 void setTrue(KeyType const& k) { 149 BMO::setTrue(k); 150 SO::setTrue(k); 151 } 152 template<typename KeyType> 153 void setFalse(KeyType const& k) { 154 BMO::setFalse(k); 155 SO::setFalse(k); 156 } 157 }; 158 63 template<typename Iterator> 64 inline 65 SequenceOutput<Iterator> 66 makeSequenceOutput(Iterator it) { 67 return SequenceOutput<Iterator>(it); 68 } 159 69 160 70 /* ** ** InputSource ok ** ** */ 161 71 162 72 template<typename Key, typename Val> 163 class PairVec : public std::vector< std::pair<Key,Val> > {73 class KruskalPairVec : public std::vector< std::pair<Key,Val> > { 164 74 165 75 public: … … 172 82 typedef typename Parent::const_iterator const_iterator; 173 83 174 175 84 private: 176 177 85 class comparePair { 178 86 public: … … 185 93 186 94 // FIXME: kell ez? 187 // PairVec(Parent const& p) : Parent(p) {}95 // KruskalPairVec(Parent const& p) : Parent(p) {} 188 96 189 97 void sort() { … … 193 101 // FIXME: nem nagyon illik ez ide... 194 102 template<typename Graph, typename Map> 195 void readGraphEdgeMap(Graph const& G, Map const& m) {103 KruskalPairVec(Graph const& G, Map const& m) { 196 104 typedef typename Graph::EdgeIt EdgeIt; 197 105 198 106 clear(); 199 for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) { 107 FOR_EACH_LOC(EdgeIt, e, G) { 108 // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) { 200 109 push_back(make_pair(e, m[e])); 201 110 } 202 203 111 sort(); 204 112 } 205 206 int alma() { return 5; /* FIXME */ }207 113 208 114 Key const& first(const_iterator i) const { return i>first; } … … 213 119 }; 214 120 121 122 template <typename Map> 123 class KruskalMapVec : public std::vector<typename Map::KeyType> { 124 public: 125 126 typedef typename Map::KeyType KeyType; 127 typedef typename Map::ValueType ValueType; 128 129 typedef typename std::vector<KeyType> Parent; 130 typedef typename Parent::iterator iterator; 131 typedef typename Parent::const_iterator const_iterator; 132 133 private: 134 135 const Map &m; 136 137 class compareKeys { 138 const Map &m; 139 public: 140 compareKeys(Map const &_m) : m(_m) {} 141 bool operator()(KeyType const& a, KeyType const& b) { 142 return m[a] < m[b]; 143 } 144 }; 145 146 public: 147 148 KruskalMapVec(Map const& _m) : m(_m) {} 149 150 void sort() { 151 std::sort(begin(), end(), compareKeys(m)); 152 } 153 154 // FIXME: nem nagyon illik ez ide... 155 template<typename Graph> 156 KruskalMapVec(Graph const& G, Map const& _m) : m(_m) { 157 typedef typename Graph::EdgeIt EdgeIt; 158 159 clear(); 160 FOR_EACH_LOC(EdgeIt, e, G) { 161 // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) { 162 push_back(e); 163 } 164 sort(); 165 } 166 167 KeyType const& first(const_iterator i) const { return *i; } 168 KeyType& first(iterator i) { return *i; } 169 170 ValueType const& second(const_iterator i) const { return m[*i]; } 171 ValueType& second(iterator i) { return m[*i]; } 172 }; 173 215 174 /* ** ** Wrapper fuggvenyek ** ** */ 216 175 176 177 /// \brief Wrapper to Kruskal(). 178 /// Input is from an EdgeMap, output is a plain boolmap. 217 179 template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap> 218 180 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); 223 224 typedef PairVec<typename Graph::Edge, typename EdgeCostMap::ValueType> 181 Kruskal_EdgeCostMapIn_BoolMapOut(Graph const& G, 182 EdgeCostMap const& edge_costs, 183 RetEdgeBoolMap &ret_bool_map) { 184 185 typedef KruskalPairVec<typename Graph::Edge, typename EdgeCostMap::ValueType> 225 186 InputVec; 226 InputVec iv; 227 iv.readGraphEdgeMap(G, edge_costs); 228 229 MinCostTreeKruskal<Graph,InputVec,OutObs> mctk(G, iv, out); 230 return mctk.run(); 231 } 232 187 InputVec iv(G, edge_costs); 188 189 return Kruskal(G, iv, ret_bool_map); 190 } 191 192 193 /// \brief Wrapper to Kruskal(). 194 /// Input is from an EdgeMap, output is to a sequence. 233 195 template <typename Graph, typename EdgeCostMap, typename RetIterator> 234 196 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); 239 240 typedef PairVec<typename Graph::Edge, typename EdgeCostMap::ValueType> 197 Kruskal_EdgeCostMapIn_IteratorOut(Graph const& G, 198 EdgeCostMap const& edge_costs, 199 RetIterator ret_iterator) { 200 typedef SequenceOutput<RetIterator> OutMap; 201 OutMap out(ret_iterator); 202 203 typedef KruskalPairVec<typename Graph::Edge, typename EdgeCostMap::ValueType> 241 204 InputVec; 242 InputVec iv; 243 iv.readGraphEdgeMap(G, edge_costs); 244 245 MinCostTreeKruskal<Graph,InputVec,OutObs> mctk(G, iv, out); 246 return mctk.run(); 205 InputVec iv(G, edge_costs); 206 207 return Kruskal(G, iv, out); 247 208 } 248 209 
src/work/johanna/kruskal_test.cc
r246 r349 72 72 73 73 cout << "Uniform 2es koltseggel: " 74 << kruskal1(G, edge_cost_map, tree_map)74 << Kruskal_EdgeCostMapIn_BoolMapOut(G, edge_cost_map, tree_map) 75 75 << endl; 76 76 … … 90 90 91 91 cout << "Nemkonst koltseggel (31): " 92 << kruskal2(G, edge_cost_map, back_inserter(tree_edge_vec)) 92 << Kruskal_EdgeCostMapIn_IteratorOut(G, edge_cost_map, 93 back_inserter(tree_edge_vec)) 93 94 << endl; 94 95 95 96 int i = 1; 97 for(vector<Edge>::iterator e = tree_edge_vec.begin(); 98 e != tree_edge_vec.end(); ++e, ++i) { 99 cout << i << ". el: " << *e << endl; 100 } 101 102 tree_edge_vec.clear(); 103 SequenceOutput< back_insert_iterator< vector<Edge> > > 104 vec_filler(back_inserter(tree_edge_vec)); 105 cout << "Nemkonst koltseggel tarhatekonyabban: " 106 << Kruskal(G, 107 KruskalMapVec<ECostMap>(G, edge_cost_map), 108 vec_filler) 109 << endl; 110 111 i = 1; 96 112 for(vector<Edge>::iterator e = tree_edge_vec.begin(); 97 113 e != tree_edge_vec.end(); ++e, ++i) { 
src/work/johanna/unionfind.h
r218 r349 25 25 int whichComponent(T a) 26 26 { 27 int comp0 = map .get(a);27 int comp0 = map[a]; 28 28 if (comp0 < 0) { 29 29 return insertNewElement(a);
Note: See TracChangeset
for help on using the changeset viewer.