Changeset 737:2d867176d10e in lemon0.x for src/work/johanna/kruskal.h
 Timestamp:
 07/23/04 19:13:23 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@994
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/johanna/kruskal.h
r682 r737 4 4 5 5 #include <algorithm> 6 #include <unionfind.h> 7 #include <for_each_macros.h> 6 #include <hugo/unionfind.h> 8 7 9 8 ///\file … … 12 11 namespace hugo { 13 12 14 /// Kruskal's algorithm to compute a minimum cost tree 13 /// Kruskal's algorithm to find a minimum cost tree of a graph. 14 15 /// This function runs Kruskal's algorithm to find a minimum cost tree. 16 /// \param G The graph the algorithm runs on. 17 /// \param in This object is used to describe the edge costs. It must 18 /// be an STL 'forward container' 19 /// with value_type <tt> std::pair<Graph::Edge,X> </tt>, 20 /// where X is the type of the costs. It must contain every edge in 21 /// costascending order. 22 /// \retval out This must be a writeable EdgeMap. After running the algorithm 23 /// this will contain the found minimum cost spanning tree: the value of an 24 /// edge will be set to \c true if it belongs to the tree, otherwise it will 25 /// be set to \c false. The value of each edge will be set exactly once.\n 26 /// For the sake of simplicity, there is a helper class KruskalPairVec, 27 /// which converts a 28 /// simple EdgeMap to an input of this form. Alternatively, you can use 29 /// the function \ref kruskalEdgeMap to compute the minimum cost tree if 30 /// the edge costs are given by an EdgeMap. 31 /// \return The cost of the found tree. 15 32 16 33 template <typename Graph, typename InputEdgeOrder, typename OutBoolMap> 17 typename InputEdgeOrder:: ValueType18 Kruskal(Graph const& G, InputEdgeOrder const& edges,19 OutBoolMap& out_map)34 typename InputEdgeOrder::value_type::second_type 35 kruskal(Graph const& G, InputEdgeOrder const& in, 36 OutBoolMap& out) 20 37 { 21 typedef typename InputEdgeOrder:: ValueType EdgeCost;22 typedef typename Graph:: NodeMap<int> NodeIntMap;38 typedef typename InputEdgeOrder::value_type::second_type EdgeCost; 39 typedef typename Graph::template NodeMap<int> NodeIntMap; 23 40 typedef typename Graph::Node Node; 24 41 25 NodeIntMap comp _map(G, 1);26 UnionFind<Node,NodeIntMap> uf(comp _map);42 NodeIntMap comp(G, 1); 43 UnionFind<Node,NodeIntMap> uf(comp); 27 44 28 45 EdgeCost tot_cost = 0; 29 for (typename InputEdgeOrder::const_iterator p = edges.begin();30 p!= edges.end(); ++p ) {31 if ( uf.join(G.head( edges.first(p)),32 G.tail(edges.first(p))) ) {33 out _map.set(edges.first(p), true);34 tot_cost += edges.second(p);46 for (typename InputEdgeOrder::const_iterator p = in.begin(); 47 p!=in.end(); ++p ) { 48 if ( uf.join(G.head((*p).first), 49 G.tail((*p).first)) ) { 50 out.set((*p).first, true); 51 tot_cost += (*p).second; 35 52 } 36 53 else { 37 out _map.set(edges.first(p), false);54 out.set((*p).first, false); 38 55 } 39 56 } … … 58 75 inline 59 76 typename InputEdgeOrder::ValueType 60 Kruskal(Graph const& G, InputEdgeOrder const& edges,77 kruskal(Graph const& G, InputEdgeOrder const& edges, 61 78 OutBoolMap const& out_map) 62 79 { 63 80 NonConstMapWr<OutBoolMap> map_wr(out_map); 64 return Kruskal(G, edges, map_wr);81 return kruskal(G, edges, map_wr); 65 82 } 66 83 … … 70 87 /// A writable boolmap that makes a sequence of "true" keys 71 88 72 /// A writable boolmap that creates a sequence out of keys that receive 89 /// A writable boolmap that creates a sequence out of keys that receives 73 90 /// the value "true". 74 91 /// \warning Not a regular property map, as it doesn't know its KeyType … … 96 113 /* ** ** InputSource ok ** ** */ 97 114 98 template<typename Key, typename Val> 99 class KruskalPairVec : public std::vector< std::pair<Key,Val> > { 100 101 public: 102 typedef std::vector< std::pair<Key,Val> > Parent; 103 typedef Key KeyType; 104 typedef Val ValueType; 105 typedef std::pair<Key,Val> PairType; 106 107 typedef typename Parent::iterator iterator; 108 typedef typename Parent::const_iterator const_iterator; 115 /// Kruskal input source. 116 117 /// Kruskal input source. 118 /// 119 template<typename Graph, typename Map> 120 class KruskalPairVec 121 : public std::vector< std::pair<typename Graph::Edge, 122 typename Map::ValueType> > { 123 124 public: 125 typedef std::vector< std::pair<typename Graph::Edge, 126 typename Map::ValueType> > Parent; 127 typedef typename Parent::value_type value_type; 128 // typedef Key KeyType; 129 // typedef Val ValueType; 130 // typedef std::pair<Key,Val> PairType; 131 // typedef typename Parent::iterator iterator; 132 // typedef typename Parent::const_iterator const_iterator; 109 133 110 134 private: 111 135 class comparePair { 112 136 public: 113 bool operator()(PairType const& a, PairType const& b) { 137 bool operator()(const value_type& a, 138 const value_type& b) { 114 139 return a.second < b.second; 115 140 } … … 122 147 123 148 void sort() { 124 std::sort( begin(),end(), comparePair());149 std::sort(this>begin(), this>end(), comparePair()); 125 150 } 126 151 127 152 // FIXME: nem nagyon illik ez ide... 128 template<typename Graph, typename Map>129 153 KruskalPairVec(Graph const& G, Map const& m) { 130 154 typedef typename Graph::EdgeIt EdgeIt; 131 132 clear();133 FOR_EACH_LOC(EdgeIt, e, G) {134 155 156 this>clear(); 157 for(EdgeIt e(G);G.valid(e);G.next(e)) { 158 // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) { 135 159 push_back(make_pair(e, m[e])); 136 160 } … … 138 162 } 139 163 140 Key const& first(const_iterator i) const { return i>first; }141 Key& first(iterator i) { return i>first; }142 143 Val const& second(const_iterator i) const { return i>second; }144 Val& second(iterator i) { return i>second; }164 // Key const& first(const_iterator i) const { return i>first; } 165 // Key& first(iterator i) { return i>first; } 166 167 // Val const& second(const_iterator i) const { return i>second; } 168 // Val& second(iterator i) { return i>second; } 145 169 }; 146 170 147 171 148 template <typename Map>149 class KruskalMapVec : public std::vector<typename Map::KeyType> {150 public:151 152 typedef typename Map::KeyType KeyType;153 typedef typename Map::ValueType ValueType;154 155 typedef typename std::vector<KeyType> Parent;156 typedef typename Parent::iterator iterator;157 typedef typename Parent::const_iterator const_iterator;158 159 private:160 161 const Map &m;162 163 class compareKeys {164 const Map &m;165 public:166 compareKeys(Map const &_m) : m(_m) {}167 bool operator()(KeyType const& a, KeyType const& b) {168 return m[a] < m[b];169 }170 };171 172 public:173 174 KruskalMapVec(Map const& _m) : m(_m) {}175 176 void sort() {177 std::sort(begin(), end(), compareKeys(m));178 }179 180 // FIXME: nem nagyon illik ez ide...181 template<typename Graph>182 KruskalMapVec(Graph const& G, Map const& _m) : m(_m) {183 typedef typename Graph::EdgeIt EdgeIt;184 185 clear();186 FOR_EACH_LOC(EdgeIt, e, G) {187 // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) { 188 push_back(e);189 }190 sort();191 }192 193 KeyType const& first(const_iterator i) const { return *i; }194 KeyType& first(iterator i) { return *i; }195 196 ValueType const& second(const_iterator i) const { return m[*i]; }197 ValueType& second(iterator i) { return m[*i]; }198 };172 // template <typename Map> 173 // class KruskalMapVec : public std::vector<typename Map::KeyType> { 174 // public: 175 176 // typedef typename Map::KeyType KeyType; 177 // typedef typename Map::ValueType ValueType; 178 179 // typedef typename std::vector<KeyType> Parent; 180 // typedef typename Parent::iterator iterator; 181 // typedef typename Parent::const_iterator const_iterator; 182 183 // private: 184 185 // const Map &m; 186 187 // class compareKeys { 188 // const Map &m; 189 // public: 190 // compareKeys(Map const &_m) : m(_m) {} 191 // bool operator()(KeyType const& a, KeyType const& b) { 192 // return m[a] < m[b]; 193 // } 194 // }; 195 196 // public: 197 198 // KruskalMapVec(Map const& _m) : m(_m) {} 199 200 // void sort() { 201 // std::sort(begin(), end(), compareKeys(m)); 202 // } 203 204 // // FIXME: nem nagyon illik ez ide... 205 // template<typename Graph> 206 // KruskalMapVec(Graph const& G, Map const& _m) : m(_m) { 207 // typedef typename Graph::EdgeIt EdgeIt; 208 209 // clear(); 210 // for(EdgeIt e(G);G.valid(e);G.next(e)) { 211 // // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) 212 // push_back(e); 213 // } 214 // sort(); 215 // } 216 217 // KeyType const& first(const_iterator i) const { return *i; } 218 // KeyType& first(iterator i) { return *i; } 219 220 // ValueType const& second(const_iterator i) const { return m[*i]; } 221 // ValueType& second(iterator i) { return m[*i]; } 222 // }; 199 223 200 224 /* ** ** Wrapper fuggvenyek ** ** */ … … 203 227 /// \brief Wrapper to Kruskal(). 204 228 /// Input is from an EdgeMap, output is a plain boolmap. 229 230 ///\todo some more words would be nice here. 231 /// 205 232 template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap> 206 233 inline 207 234 typename EdgeCostMap::ValueType 208 Kruskal_EdgeCostMapIn_BoolMapOut(Graph const& G,209 210 211 212 typedef KruskalPairVec< typename Graph::Edge, typename EdgeCostMap::ValueType>213 InputVec;235 kruskalEdgeMap(Graph const& G, 236 EdgeCostMap const& edge_costs, 237 RetEdgeBoolMap &ret_bool_map) { 238 239 typedef KruskalPairVec<Graph,EdgeCostMap> InputVec; 240 214 241 InputVec iv(G, edge_costs); 215 216 return Kruskal(G, iv, ret_bool_map); 242 return kruskal(G, iv, ret_bool_map); 217 243 } 218 244 … … 220 246 /// \brief Wrapper to Kruskal(). 221 247 /// Input is from an EdgeMap, output is to a sequence. 248 249 ///\todo it does not follow the naming convention. 250 /// 222 251 template <typename Graph, typename EdgeCostMap, typename RetIterator> 223 252 inline 224 253 typename EdgeCostMap::ValueType 225 Kruskal_EdgeCostMapIn_IteratorOut(Graph const& G, 226 EdgeCostMap const& edge_costs, 227 RetIterator ret_iterator) { 254 kruskalEdgeMap_IteratorOut(const Graph& G, 255 const EdgeCostMap& edge_costs, 256 RetIterator ret_iterator) 257 { 258 typedef typename EdgeCostMap::ValueType ValueType; 259 228 260 typedef SequenceOutput<RetIterator> OutMap; 229 261 OutMap out(ret_iterator); 230 262 231 typedef KruskalPairVec< typename Graph::Edge, typename EdgeCostMap::ValueType>232 InputVec; 263 typedef KruskalPairVec<Graph, EdgeCostMap> InputVec; 264 233 265 InputVec iv(G, edge_costs); 234 266 235 return Kruskal(G, iv, out);267 return kruskal(G, iv, out); 236 268 } 237 269
Note: See TracChangeset
for help on using the changeset viewer.