Changeset 394:3a34c5626e52 in lemon-0.x
- Timestamp:
- 04/24/04 18:03:25 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@525
- Location:
- src/work/johanna
- Files:
-
- 2 added
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/johanna/Makefile
r350 r394 1 BINARIES = kruskal_test ma_order_test 1 BINARIES = kruskal_test ma_order_test unionfind_test 2 2 INCLUDEDIRS= -I. -I.. -I../../include -I../{marci,jacint,alpar,klao,akos} 3 3 include ../makefile -
src/work/johanna/kruskal.h
r352 r394 26 26 for (typename InputEdgeOrder::const_iterator p = edges.begin(); 27 27 p!=edges.end(); ++p ) { 28 if ( uf.join Components(G.head(edges.first(p)),28 if ( uf.join(G.head(edges.first(p)), 29 29 G.tail(edges.first(p))) ) { 30 30 out_map.set(edges.first(p), true); -
src/work/johanna/unionfind.h
r349 r394 4 4 5 5 #include <vector> 6 #include <list> 6 7 #include <utility> 8 #include <algorithm> 9 10 #include <invalid.h> 7 11 8 12 namespace hugo { … … 23 27 24 28 25 int whichComponent(T a)29 int find(T a) 26 30 { 27 31 int comp0 = map[a]; 28 32 if (comp0 < 0) { 29 return insert NewElement(a);33 return insert(a); 30 34 } 31 35 int comp = comp0; … … 42 46 } 43 47 44 int insert NewElement(T a)48 int insert(T a) 45 49 { 46 50 int n = data.size(); 47 data.push_back( make_pair(n, 1));51 data.push_back(std::make_pair(n, 1)); 48 52 map.set(a,n); 49 53 return n; 50 54 } 51 55 52 bool join Components(T a, T b)53 { 54 int ca = whichComponent(a);55 int cb = whichComponent(b);56 bool join(T a, T b) 57 { 58 int ca = find(a); 59 int cb = find(b); 56 60 57 61 if ( ca == cb ) … … 69 73 } 70 74 71 int componentSize(T a)72 { 73 int ca = whichComponent(a);75 int size(T a) 76 { 77 int ca = find(a); 74 78 return data[ca].second; 75 79 } … … 77 81 }; 78 82 83 84 85 86 /*******************************************************/ 87 88 89 90 template <typename T> 91 struct UnionFindEnumItem { 92 93 typedef std::list<UnionFindEnumItem> ItemList; 94 typedef std::list<ItemList> ClassList; 95 typedef typename ItemList::iterator IIter; 96 typedef typename ClassList::iterator CIter; 97 98 T me; 99 IIter parent; 100 int size; 101 CIter my_class; 102 103 UnionFindEnumItem() {} 104 UnionFindEnumItem(const T &_me, CIter _my_class): 105 me(_me), size(1), my_class(_my_class) {} 106 }; 107 108 template <typename T, template <typename Item> class Map> 109 class UnionFindEnum { 110 111 typedef std::list<UnionFindEnumItem<T> > ItemList; 112 typedef std::list<ItemList> ClassList; 113 typedef typename ItemList::iterator IIter; 114 typedef typename ItemList::const_iterator IcIter; 115 typedef typename ClassList::iterator CIter; 116 typedef typename ClassList::const_iterator CcIter; 117 118 public: 119 typedef T ElementType; 120 typedef UnionFindEnumItem<T> ItemType; 121 typedef Map< IIter > MapType; 122 123 private: 124 MapType& m; 125 ClassList classes; 126 127 // IIter where(const T &a) { return m[a]; } 128 // IIter parent(IIter a) { return a->parent; } 129 // P sibling(P a) { return &m[a->sibling]; } 130 131 IIter _find(IIter a) const { 132 IIter comp = a; 133 IIter next; 134 while( (next = comp->parent) != comp ) { 135 comp = next; 136 } 137 138 IIter comp1 = a; 139 while( (next = comp1->parent) != comp ) { 140 comp1->parent = comp->parent; 141 comp1 = next; 142 } 143 return comp; 144 } 145 146 public: 147 UnionFindEnum(MapType& _m) : m(_m) {} 148 149 void insert(const T &a) 150 { 151 152 153 classes.push_back(ItemList()); 154 CIter aclass = classes.end(); 155 --aclass; 156 157 ItemList &alist = *aclass; 158 alist.push_back(ItemType(a, aclass)); 159 IIter ai = alist.begin(); 160 161 ai->parent = ai; 162 m.set(a, ai); 163 164 } 165 166 T find(const T &a) const { 167 return _find(m[a])->me; 168 } 169 170 bool join(T a, T b) { 171 172 IIter ca = _find(m[a]); 173 IIter cb = _find(m[b]); 174 175 if ( ca == cb ) { 176 return false; 177 } 178 179 if ( ca->size > cb->size ) { 180 181 cb->parent = ca->parent; 182 ca->size += cb->size; 183 184 ItemList &alist = *ca->my_class; 185 alist.splice(alist.end(),*cb->my_class); 186 187 classes.erase(cb->my_class); 188 cb->my_class = 0; 189 } 190 else { 191 192 ca->parent = cb->parent; 193 cb->size += ca->size; 194 195 ItemList &blist = *cb->my_class; 196 blist.splice(blist.end(),*ca->my_class); 197 198 classes.erase(ca->my_class); 199 ca->my_class = 0; 200 } 201 202 return true; 203 } 204 205 int size(const T &a) const { 206 return _find(m[a])->size; 207 } 208 209 210 void split(const T &a) { 211 212 IIter ca = _find(m[a]); 213 214 if ( ca->size == 1 ) 215 return; 216 217 CIter aclass = ca->my_class; 218 219 for(IIter curr = ca; ++curr != aclass->end(); curr=ca) { 220 classes.push_back(ItemList()); 221 CIter nl = --classes.end(); 222 nl->splice(nl->end(), *aclass, curr); 223 224 curr->size=1; 225 curr->parent=curr; 226 curr->my_class = nl; 227 } 228 229 ca->size=1; 230 return; 231 } 232 233 void erase(const T &a) { 234 235 IIter ma = m[a]; 236 if (ma == 0) return; 237 238 IIter la = _find(ma); 239 if (la == ma) { 240 if (ma -> size == 1){ 241 classes.erase(ma->my_class); 242 m.set(a,0); 243 return; 244 } 245 ++la; 246 la->size = ma->size - 1; 247 la->my_class = ma->my_class; 248 } 249 250 for (IIter i = la; i != la->my_class->end(); ++i) { 251 i->parent = la; 252 } 253 254 la->my_class->erase(ma); 255 m.set(a,0); 256 } 257 258 void eraseClass(const T &a) { 259 IIter ma = m[a]; 260 if (ma == 0) return; 261 # ifdef DEBUG 262 CIter c = _find(ma)->my_class; 263 for (IIter i=c->begin(); i!=c->end(); ++i) 264 m.set(i->me, 0); 265 # endif 266 classes.erase(_find(ma)->my_class); 267 } 268 269 270 class ClassIt { 271 friend class UnionFindEnum; 272 273 CcIter i; 274 public: 275 ClassIt(Invalid): i(0) {} 276 ClassIt() {} 277 278 operator const T& () const { 279 ItemList const &ll = *i; 280 return (ll.begin())->me; } 281 bool operator == (ClassIt it) const { 282 return (i == it.i); 283 } 284 bool operator != (ClassIt it) const { 285 return (i != it.i); 286 } 287 bool operator < (ClassIt it) const { 288 return (i < it.i); 289 } 290 291 bool valid() const { return i != 0; } 292 private: 293 void first(const ClassList &l) { i = l.begin(); validate(l); } 294 void next(const ClassList &l) { 295 ++i; 296 validate(l); 297 } 298 void validate(const ClassList &l) { 299 if ( i == l.end() ) 300 i = 0; 301 } 302 }; 303 304 305 ClassIt& first(ClassIt& it) const { 306 it.first(classes); 307 return it; 308 } 309 310 bool valid(ClassIt const &it) const { 311 return it.valid(); 312 } 313 314 ClassIt& next(ClassIt& it) const { 315 it.next(classes); 316 return it; 317 } 318 319 320 class ItemIt { 321 friend class UnionFindEnum; 322 323 IcIter i; 324 const ItemList *l; 325 public: 326 ItemIt(Invalid): i(0) {} 327 ItemIt() {} 328 329 operator const T& () const { return i->me; } 330 bool operator == (ItemIt it) const { 331 return (i == it.i); 332 } 333 bool operator != (ItemIt it) const { 334 return (i != it.i); 335 } 336 bool operator < (ItemIt it) const { 337 return (i < it.i); 338 } 339 340 bool valid() const { return i != 0; } 341 private: 342 void first(const ItemList &il) { l=&il; i = l->begin(); validate(); } 343 void next() { 344 ++i; 345 validate(); 346 } 347 void validate() { 348 if ( i == l->end() ) 349 i = 0; 350 } 351 }; 352 353 354 ItemIt& first(ItemIt& it, const T& a) const { 355 it.first( * _find(m[a])->my_class ); 356 return it; 357 } 358 359 bool valid(ItemIt const &it) const { 360 return it.valid(); 361 } 362 363 ItemIt& next(ItemIt& it) const { 364 it.next(); 365 return it; 366 } 367 368 369 370 }; 371 79 372 } //namespace hugo 80 373
Note: See TracChangeset
for help on using the changeset viewer.