Changeset 185:259540358bbf in lemon-0.x for src/work/alpar/smart_graph.h
- Timestamp:
- 03/13/04 23:53:07 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@261
- File:
-
- 1 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
Note: See TracChangeset
for help on using the changeset viewer.