Changeset 186:47cd1716870e in lemon-0.x for src/work/alpar/smart_graph.h
- Timestamp:
- 03/15/04 17:30:20 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@262
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/alpar/smart_graph.h
r185 r186 13 13 class SymSmartGraph; 14 14 15 // template<typename T> class SymSmartGraph::SymEdgeMap; 16 15 ///A smart graph class. 16 17 ///This is a simple and fast graph implementation. 18 ///It is also quite memory efficient, but at the price 19 ///that <b> it does not support node and edge deletion</b>. 20 ///Apart from this it conforms to the graph interface documented under 21 ///the description of \ref GraphSkeleton. 22 ///\sa \ref GraphSkeleton. 17 23 class SmartGraph { 18 24 … … 56 62 // protected: 57 63 // HELPME: 58 p ublic:64 protected: 59 65 ///\bug It must be public because of SymEdgeMap. 60 66 /// … … 100 106 int edgeNum() const { return edges.size(); } //FIXME: What is this? 101 107 108 ///\bug This function does something different than 109 ///its name would suggests... 102 110 int maxNodeId() const { return nodes.size(); } //FIXME: What is this? 111 ///\bug This function does something different than 112 ///its name would suggests... 103 113 int maxEdgeId() const { return edges.size(); } //FIXME: What is this? 104 114 105 106 115 Node tail(Edge e) const { return edges[e.n].tail; } 107 116 Node head(Edge e) const { return edges[e.n].head; } … … 481 490 ///The purpose of this graph structure is to handle graphs 482 491 ///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 492 ///of oppositely directed edges. 493 ///There is a new edge map type called 494 ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap" 495 ///that complements this 496 ///feature by 497 ///storing shared values for the edge pairs. The usual 498 ///\ref GraphSkeleton::EdgeMap "EdgeMap" 499 ///can be used 485 500 ///as well. 486 501 /// 487 ///The oppositely directed edge can also be obtained easily. 502 ///The oppositely directed edge can also be obtained easily 503 ///using \ref opposite. 504 ///\warning It shares the similarity with \ref SmartGraph that 505 ///it is not possible to delete edges or nodes from the graph. 506 //\sa \ref SmartGraph. 488 507 489 508 class SymSmartGraph : public SmartGraph 490 509 { 491 510 public: 511 template<typename T> class SymEdgeMap; 512 template<typename T> friend class SymEdgeMap; 513 492 514 SymSmartGraph() : SmartGraph() { } 493 515 SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { } … … 499 521 } 500 522 523 ///The oppositely directed edge. 524 525 ///Returns the oppositely directed 526 ///pair of the edge \c e. 501 527 Edge opposite(Edge e) const 502 528 { … … 506 532 } 507 533 534 ///Common data storage for the edge pairs. 535 536 ///This map makes it possible to store data shared by the oppositely 537 ///directed pairs of edges. 508 538 template <typename T> class SymEdgeMap : public DynMapBase<Edge> 509 539 { … … 514 544 typedef Edge KeyType; 515 545 516 SymEdgeMap(const S martGraph &_G) :546 SymEdgeMap(const SymSmartGraph &_G) : 517 547 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2) 518 548 { 519 G->dyn_edge_maps.push_back(this);520 } 521 SymEdgeMap(const S martGraph &_G,const T &t) :549 static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.push_back(this); 550 } 551 SymEdgeMap(const SymSmartGraph &_G,const T &t) : 522 552 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t) 523 553 { … … 551 581 if(G) { 552 582 std::vector<DynMapBase<Edge>* >::iterator i; 553 for(i=G->dyn_edge_maps.begin(); 554 i!=G->dyn_edge_maps.end() && *i!=this; ++i) ; 583 for(i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.begin(); 584 i!=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.end() 585 && *i!=this; ++i) ; 555 586 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow... 556 587 //A better way to do that: (Is this really important?) 557 588 if(*i==this) { 558 *i= G->dyn_edge_maps.back();559 G->dyn_edge_maps.pop_back();589 *i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.back(); 590 static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.pop_back(); 560 591 } 561 592 }
Note: See TracChangeset
for help on using the changeset viewer.