Changeset 185:259540358bbf in lemon0.x
 Timestamp:
 03/13/04 23:53:07 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@261
 Location:
 src/work/alpar
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

src/work/alpar/smart_graph.h
r177 r185 1 1 // * mode:C++ * 2 2 3 #ifndef SMART_GRAPH_H4 #define SMART_GRAPH_H3 #ifndef HUGO_SMART_GRAPH_H 4 #define HUGO_SMART_GRAPH_H 5 5 6 6 #include <vector> … … 11 11 namespace hugo { 12 12 13 class SymSmartGraph; 14 15 // template<typename T> class SymSmartGraph::SymEdgeMap; 16 13 17 class SmartGraph { 14 18 … … 29 33 std::vector<EdgeT> edges; 30 34 35 protected: 36 31 37 template <typename Key> class DynMapBase 32 38 { 33 39 protected: 34 SmartGraph* G;40 const SmartGraph* G; 35 41 public: 36 42 virtual void add(const Key k) = NULL; … … 40 46 friend class SmartGraph; 41 47 }; 48 42 49 public: 43 template <typename T> class DynEdgeMap;44 template <typename T> class DynEdgeMap;50 template <typename T> class EdgeMap; 51 template <typename T> class EdgeMap; 45 52 46 53 class Node; 47 54 class Edge; 48 55 49 protected: 56 // protected: 57 // HELPME: 58 public: 59 ///\bug It must be public because of SymEdgeMap. 60 /// 50 61 mutable std::vector<DynMapBase<Node> * > dyn_node_maps; 62 ///\bug It must be public because of SymEdgeMap. 63 /// 51 64 mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps; 52 65 … … 169 182 friend class SmartGraph; 170 183 template <typename T> friend class NodeMap; 171 template <typename T> friend class DynNodeMap;172 184 173 185 friend class Edge; … … 198 210 friend class SmartGraph; 199 211 template <typename T> friend class EdgeMap; 200 template <typename T> friend class DynEdgeMap; 212 213 //template <typename T> friend class SymSmartGraph::SymEdgeMap; 214 //friend Edge SymSmartGraph::opposite(Edge) const; 201 215 202 216 friend class Node; … … 213 227 bool operator!=(const Edge i) const {return n!=i.n;} 214 228 bool operator<(const Edge i) const {return n<i.n;} 229 ///\bug This is a workaround until somebody tells me how to 230 ///make class \c SymSmartGraph::SymEdgeMap friend of Edge 231 int &idref() {return n;} 232 const int &idref() const {return n;} 215 233 }; 216 234 … … 221 239 EdgeIt (Invalid i) : Edge(i) { } 222 240 EdgeIt() : Edge() { } 241 ///\bug This is a workaround until somebody tells me how to 242 ///make class \c SymSmartGraph::SymEdgeMap friend of Edge 243 int &idref() {return n;} 223 244 }; 224 245 … … 243 264 // Map types 244 265 245 template <typename T> 246 class NodeMap { 247 const SmartGraph& G; 266 // // Static Maps are not necessary. 267 // template <typename T> 268 // class NodeMap { 269 // const SmartGraph& G; 270 // std::vector<T> container; 271 // public: 272 // typedef T ValueType; 273 // typedef Node KeyType; 274 // NodeMap(const SmartGraph& _G) : G(_G), container(G.maxNodeId()) { } 275 // NodeMap(const SmartGraph& _G, T a) : 276 // G(_G), container(G.maxNodeId(), a) { } 277 // void set(Node n, T a) { container[n.n]=a; } 278 // T get(Node n) const { return container[n.n]; } 279 // T& operator[](Node n) { return container[n.n]; } 280 // const T& operator[](Node n) const { return container[n.n]; } 281 // void update() { container.resize(G.maxNodeId()); } 282 // void update(T a) { container.resize(G.maxNodeId(), a); } 283 // }; 284 285 // template <typename T> 286 // class EdgeMap { 287 // const SmartGraph& G; 288 // std::vector<T> container; 289 // public: 290 // typedef T ValueType; 291 // typedef Edge KeyType; 292 // EdgeMap(const SmartGraph& _G) : G(_G), container(G.maxEdgeId()) { } 293 // EdgeMap(const SmartGraph& _G, T a) : 294 // G(_G), container(G.maxEdgeId(), a) { } 295 // void set(Edge e, T a) { container[e.n]=a; } 296 // T get(Edge e) const { return container[e.n]; } 297 // T& operator[](Edge e) { return container[e.n]; } 298 // const T& operator[](Edge e) const { return container[e.n]; } 299 // void update() { container.resize(G.maxEdgeId()); } 300 // void update(T a) { container.resize(G.maxEdgeId(), a); } 301 // }; 302 303 template <typename T> class NodeMap : public DynMapBase<Node> 304 { 248 305 std::vector<T> container; 306 249 307 public: 250 308 typedef T ValueType; 251 309 typedef Node KeyType; 252 NodeMap(const SmartGraph& _G) : G(_G), container(G.maxNodeId()) { } 253 NodeMap(const SmartGraph& _G, T a) : 254 G(_G), container(G.maxNodeId(), a) { } 255 void set(Node n, T a) { container[n.n]=a; } 256 T get(Node n) const { return container[n.n]; } 257 T& operator[](Node n) { return container[n.n]; } 258 const T& operator[](Node n) const { return container[n.n]; } 259 void update() { container.resize(G.maxNodeId()); } 260 void update(T a) { container.resize(G.maxNodeId(), a); } 261 }; 262 263 template <typename T> 264 class EdgeMap { 265 const SmartGraph& G; 266 std::vector<T> container; 267 public: 268 typedef T ValueType; 269 typedef Edge KeyType; 270 EdgeMap(const SmartGraph& _G) : G(_G), container(G.maxEdgeId()) { } 271 EdgeMap(const SmartGraph& _G, T a) : 272 G(_G), container(G.maxEdgeId(), a) { } 273 void set(Edge e, T a) { container[e.n]=a; } 274 T get(Edge e) const { return container[e.n]; } 275 T& operator[](Edge e) { return container[e.n]; } 276 const T& operator[](Edge e) const { return container[e.n]; } 277 void update() { container.resize(G.maxEdgeId()); } 278 void update(T a) { container.resize(G.maxEdgeId(), a); } 279 }; 280 281 template <typename T> class DynNodeMap : public DynMapBase<Node> 282 { 283 std::vector<T> container; 284 285 public: 286 typedef T ValueType; 287 typedef Node KeyType; 288 289 DynNodeMap(const SmartGraph &_G) : 310 311 NodeMap(const SmartGraph &_G) : 290 312 DynMapBase<Node>(_G), container(_G.maxNodeId()) 291 313 { 292 //FIXME: What if there are empty Id's?293 //FIXME: Can I use 'this' in a constructor?294 314 G>dyn_node_maps.push_back(this); 295 315 } 296 ~DynNodeMap() 316 NodeMap(const SmartGraph &_G,const T &t) : 317 DynMapBase<Node>(_G), container(_G.maxNodeId(),t) 318 { 319 G>dyn_node_maps.push_back(this); 320 } 321 322 NodeMap(const NodeMap<T> &m) : 323 DynMapBase<Node>(*m.G), container(m.container) 324 { 325 G>dyn_node_maps.push_back(this); 326 } 327 328 template<typename TT> friend class NodeMap; 329 330 ///\todo It can copy between different types. 331 /// 332 template<typename TT> NodeMap(const NodeMap<TT> &m) : 333 DynMapBase<Node>(*m.G) 334 { 335 G>dyn_node_maps.push_back(this); 336 typename std::vector<TT>::const_iterator i; 337 for(typename std::vector<TT>::const_iterator i=m.container.begin(); 338 i!=m.container.end(); 339 i++) 340 container.push_back(*i); 341 } 342 ~NodeMap() 297 343 { 298 344 if(G) { … … 311 357 void add(const Node k) 312 358 { 313 if(k.n>=container.size()) container.resize(k.n+1); 314 } 315 316 // void erase(const Node k) 317 // { 318 // //FIXME: Please implement me. 319 // } 320 // void erase(const Edge k) 321 // { 322 // //FIXME: Please implement me. 323 // } 359 if(k.n>=int(container.size())) container.resize(k.n+1); 360 } 361 362 void erase(const Node k) { } 324 363 325 364 void set(Node n, T a) { container[n.n]=a; } … … 328 367 const T& operator[](Node n) const { return container[n.n]; } 329 368 369 ///\warning There is no safety check at all! 370 ///Using operator = between maps attached to different graph may 371 ///cause serious problem. 372 ///\todo Is this really so? 373 ///\todo It can copy between different types. 374 const NodeMap<T>& operator=(const NodeMap<T> &m) 375 { 376 container = m.container; 377 return *this; 378 } 379 template<typename TT> 380 const NodeMap<T>& operator=(const NodeMap<TT> &m) 381 { 382 copy(m.container.begin(), m.container.end(), container.begin()); 383 return *this; 384 } 385 330 386 void update() {} //Useless for DynMaps 331 387 void update(T a) {} //Useless for DynMaps 332 388 }; 333 389 334 template <typename T> class DynEdgeMap : public DynMapBase<Edge>390 template <typename T> class EdgeMap : public DynMapBase<Edge> 335 391 { 336 392 std::vector<T> container; … … 340 396 typedef Edge KeyType; 341 397 342 DynEdgeMap(const SmartGraph &_G) :398 EdgeMap(const SmartGraph &_G) : 343 399 DynMapBase<Edge>(_G), container(_G.maxEdgeId()) 344 400 { … … 347 403 G>dyn_edge_maps.push_back(this); 348 404 } 349 ~DynEdgeMap() 405 EdgeMap(const SmartGraph &_G,const T &t) : 406 DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t) 407 { 408 G>dyn_edge_maps.push_back(this); 409 } 410 EdgeMap(const EdgeMap<T> &m) : 411 DynMapBase<Edge>(*m.G), container(m.container) 412 { 413 G>dyn_node_maps.push_back(this); 414 } 415 416 template<typename TT> friend class EdgeMap; 417 418 ///\todo It can copy between different types. 419 /// 420 template<typename TT> EdgeMap(const EdgeMap<TT> &m) : 421 DynMapBase<Edge>(*m.G) 422 { 423 G>dyn_node_maps.push_back(this); 424 typename std::vector<TT>::const_iterator i; 425 for(typename std::vector<TT>::const_iterator i=m.container.begin(); 426 i!=m.container.end(); 427 i++) 428 container.push_back(*i); 429 } 430 ~EdgeMap() 350 431 { 351 432 if(G) { … … 366 447 if(k.n>=int(container.size())) container.resize(k.n+1); 367 448 } 368 void erase(const Edge k) 369 { 370 //FIXME: Please implement me. 371 } 449 void erase(const Edge k) { } 372 450 373 451 void set(Edge n, T a) { container[n.n]=a; } … … 376 454 const T& operator[](Edge n) const { return container[n.n]; } 377 455 456 ///\warning There is no safety check at all! 457 ///Using operator = between maps attached to different graph may 458 ///cause serious problem. 459 ///\todo Is this really so? 460 ///\todo It can copy between different types. 461 const EdgeMap<T>& operator=(const EdgeMap<T> &m) 462 { 463 container = m.container; 464 return *this; 465 } 466 template<typename TT> 467 const EdgeMap<T>& operator=(const EdgeMap<TT> &m) 468 { 469 copy(m.container.begin(), m.container.end(), container.begin()); 470 return *this; 471 } 472 378 473 void update() {} //Useless for DynMaps 379 474 void update(T a) {} //Useless for DynMaps 380 475 }; 381 476 382 477 }; 478 479 ///Graph for bidirectional edges. 480 481 ///The purpose of this graph structure is to handle graphs 482 ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair 483 ///of oppositely directed edges. You can define edge maps which 484 ///stores a common value for the edge pairs. The usual edge maps can be used 485 ///as well. 486 /// 487 ///The oppositely directed edge can also be obtained easily. 488 489 class SymSmartGraph : public SmartGraph 490 { 491 public: 492 SymSmartGraph() : SmartGraph() { } 493 SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { } 494 Edge addEdge(Node u, Node v) 495 { 496 Edge e = SmartGraph::addEdge(u,v); 497 SmartGraph::addEdge(v,u); 498 return e; 499 } 500 501 Edge opposite(Edge e) const 502 { 503 Edge f; 504 f.idref() = e.idref()  2*(e.idref()%2) + 1; 505 return f; 506 } 507 508 template <typename T> class SymEdgeMap : public DynMapBase<Edge> 509 { 510 std::vector<T> container; 511 512 public: 513 typedef T ValueType; 514 typedef Edge KeyType; 515 516 SymEdgeMap(const SmartGraph &_G) : 517 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2) 518 { 519 G>dyn_edge_maps.push_back(this); 520 } 521 SymEdgeMap(const SmartGraph &_G,const T &t) : 522 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t) 523 { 524 G>dyn_edge_maps.push_back(this); 525 } 526 527 SymEdgeMap(const SymEdgeMap<T> &m) : 528 DynMapBase<SymEdge>(*m.G), container(m.container) 529 { 530 G>dyn_node_maps.push_back(this); 531 } 532 533 // template<typename TT> friend class SymEdgeMap; 534 535 ///\todo It can copy between different types. 536 /// 537 538 template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) : 539 DynMapBase<SymEdge>(*m.G) 540 { 541 G>dyn_node_maps.push_back(this); 542 typename std::vector<TT>::const_iterator i; 543 for(typename std::vector<TT>::const_iterator i=m.container.begin(); 544 i!=m.container.end(); 545 i++) 546 container.push_back(*i); 547 } 548 549 ~SymEdgeMap() 550 { 551 if(G) { 552 std::vector<DynMapBase<Edge>* >::iterator i; 553 for(i=G>dyn_edge_maps.begin(); 554 i!=G>dyn_edge_maps.end() && *i!=this; ++i) ; 555 //if(*i==this) G>dyn_edge_maps.erase(i); //Way too slow... 556 //A better way to do that: (Is this really important?) 557 if(*i==this) { 558 *i=G>dyn_edge_maps.back(); 559 G>dyn_edge_maps.pop_back(); 560 } 561 } 562 } 563 564 void add(const Edge k) 565 { 566 if(!k.idref()%2&&k.idref()/2>=int(container.size())) 567 container.resize(k.idref()/2+1); 568 } 569 void erase(const Edge k) { } 570 571 void set(Edge n, T a) { container[n.idref()/2]=a; } 572 T get(Edge n) const { return container[n.idref()/2]; } 573 T& operator[](Edge n) { return container[n.idref()/2]; } 574 const T& operator[](Edge n) const { return container[n.idref()/2]; } 575 576 ///\warning There is no safety check at all! 577 ///Using operator = between maps attached to different graph may 578 ///cause serious problem. 579 ///\todo Is this really so? 580 ///\todo It can copy between different types. 581 const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m) 582 { 583 container = m.container; 584 return *this; 585 } 586 template<typename TT> 587 const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m) 588 { 589 copy(m.container.begin(), m.container.end(), container.begin()); 590 return *this; 591 } 592 593 void update() {} //Useless for DynMaps 594 void update(T a) {} //Useless for DynMaps 595 596 }; 597 598 }; 599 600 383 601 } //namespace hugo 384 602 
src/work/alpar/smart_graph_demo.cc
r164 r185 7 7 using namespace hugo; 8 8 9 //typedef SmartGraph Graph;10 typedef EmptyGraphGraph;9 typedef SmartGraph Graph; 10 //typedef GraphSkeleton Graph; 11 11 12 12 … … 27 27 28 28 Graph G; 29 NodeIt n; 29 30 { 31 NodeIt n; 30 32 33 for(int i=0;i<10;i++) G.addNode(); 34 for(G.first(n);G.valid(n);G.next(n)) 35 for(NodeIt m(G);m!=INVALID;G.next(m)) 36 if(n!=m) G.addEdge(n,m); 37 38 OutEdgeIt e = safeFirstOut(G,n); 39 OutEdgeIt f = safeFirstOut(G,NodeIt(G)); 40 41 42 InEdgeIt i(INVALID), j; 43 InEdgeIt ii(i); 44 ii=G.first(i,n); 45 ii=G.next(i); 46 47 OutEdgeIt o(INVALID), oo; 48 OutEdgeIt ooo(oo); 49 oo=G.first(o,n); 50 oo=G.next(o); 51 52 EdgeIt ei(INVALID), eie; 53 EdgeIt eiee(ei); 54 eie=G.first(ei); 55 eie=G.next(ei); 56 57 Edge eee(i); 58 eee=o; 59 eee=eie; 60 61 62 bool tm; 63 tm = G.valid(n) && G.valid(i) && G.valid(o) && G.valid(ei); 64 65 std::vector<InEdgeIt> v(10); 66 std::vector<InEdgeIt> w(10,INVALID); 67 68 } 69 70 // Test of maps 31 71 72 G.clear(); 73 32 74 for(int i=0;i<10;i++) G.addNode(); 33 for(G.first(n);G.valid(n);G.next(n)) 34 for(NodeIt m(G);m!=INVALID;G.next(m)) 35 if(n!=m) G.addEdge(n,m); 75 for(NodeIt i(G);G.valid(i);G.next(i)) 76 for(NodeIt j(G);G.valid(j);G.next(j)) 77 if(i<j) G.addEdge(i,j); //The iterators are comparable 78 79 Graph::NodeMap<int> n(G); 80 int count=0; 81 for(NodeIt i(G);G.valid(i);G.next(i)) n[i]=count++; 82 83 Graph::NodeMap<int> nn=n; 84 Graph::NodeMap<double> dd=n; 36 85 37 OutEdgeIt e = safeFirstOut(G,n); 38 OutEdgeIt f = safeFirstOut(G,NodeIt(G)); 86 n = nn; 39 87 88 dd = nn; 89 90 Graph::EdgeMap<int> emap(G); 40 91 41 InEdgeIt i(INVALID), j; 42 InEdgeIt ii(i); 43 ii=G.first(i,n); 44 ii=G.next(i); 92 // Test of SymSmartGraph 45 93 46 OutEdgeIt o(INVALID), oo; 47 OutEdgeIt ooo(oo); 48 oo=G.first(o,n); 49 oo=G.next(o); 94 { 95 typedef SymSmartGraph Graph; 96 typedef Graph::Edge Edge; 97 typedef Graph::InEdgeIt InEdgeIt; 98 typedef Graph::OutEdgeIt OutEdgeIt; 99 typedef Graph::EdgeIt EdgeIt; 100 typedef Graph::Node Node; 101 typedef Graph::NodeIt NodeIt; 102 103 Graph G; 104 105 for(int i=0;i<10;i++) G.addNode(); 106 for(NodeIt i(G);G.valid(i);G.next(i)) 107 for(NodeIt j(G);G.valid(j);G.next(j)) 108 if(i<j) G.addEdge(i,j); //The iterators are comparable 50 109 51 EdgeIt ei(INVALID), eie; 52 EdgeIt eiee(ei); 53 eie=G.first(ei); 54 eie=G.next(ei); 55 56 Edge eee(i); 57 eee=o; 58 eee=eie; 59 60 61 bool tm; 62 tm = G.valid(n) && G.valid(i) && G.valid(o) && G.valid(ei); 63 64 std::vector<InEdgeIt> v(10); 65 std::vector<InEdgeIt> w(10,INVALID); 110 Graph::EdgeMap<int> em(G); 111 Graph::SymEdgeMap<int> sm(G); 112 for(EdgeIt e(G);G.valid(e);G.next(e)) em[e]=G.id(e); 113 for(EdgeIt e(G);G.valid(e);G.next(e)) 114 if(G.tail(e)<G.head(e)) sm[e]=G.id(e); 115 116 for(EdgeIt e(G);G.valid(e);G.next(e)) 117 std::cout << G.id(G.tail(e)) << ">" << G.id(G.head(e)) 118 << ": id=" << G.id(e) << " oppid=" << G.id(G.opposite(e)) 119 << " em=" << em[e] 120 << " sm=" << sm[e] << "\n"; 121 122 } 66 123 67 124 }
Note: See TracChangeset
for help on using the changeset viewer.