Changeset 782:df2e45e09652 in lemon-0.x for src/hugo/smart_graph.h
- Timestamp:
- 09/02/04 12:07:30 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1075
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/hugo/smart_graph.h
r774 r782 9 9 10 10 #include <vector> 11 #include < limits.h>11 #include <climits> 12 12 13 13 #include <hugo/invalid.h> 14 15 #include <hugo/array_map_factory.h> 16 #include <hugo/sym_map_factory.h> 17 #include <hugo/map_registry.h> 18 19 #include <hugo/map_defines.h> 14 20 15 21 namespace hugo { … … 17 23 /// \addtogroup graphs 18 24 /// @{ 19 class SymSmartGraph;25 // class SymSmartGraph; 20 26 21 27 ///A smart graph class. … … 54 60 std::vector<EdgeT> edges; 55 61 56 protected:57 58 template <typename Key> class DynMapBase59 {60 protected:61 const SmartGraph* G;62 public:63 virtual void add(const Key k) = 0;64 virtual void erase(const Key k) = 0;65 DynMapBase(const SmartGraph &_G) : G(&_G) {}66 virtual ~DynMapBase() {}67 friend class SmartGraph;68 };69 62 70 63 public: 71 template <typename T> class EdgeMap; 72 t emplate <typename T> class NodeMap;64 65 typedef SmartGraph Graph; 73 66 74 67 class Node; 75 68 class Edge; 76 77 // protected:78 // HELPME:79 protected:80 ///\bug It must be public because of SymEdgeMap.81 ///82 mutable std::vector<DynMapBase<Node> * > dyn_node_maps;83 ///\bug It must be public because of SymEdgeMap.84 ///85 mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;86 87 public:88 89 69 90 70 class NodeIt; … … 93 73 class InEdgeIt; 94 74 95 template <typename T> class NodeMap;96 template <typename T> class EdgeMap;75 CREATE_MAP_REGISTRIES; 76 CREATE_MAPS(ArrayMapFactory); 97 77 98 78 public: … … 101 81 SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { } 102 82 103 ~SmartGraph()104 {105 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();106 i!=dyn_node_maps.end(); ++i) (**i).G=NULL;107 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();108 i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;109 }110 111 83 int nodeNum() const { return nodes.size(); } //FIXME: What is this? 112 84 int edgeNum() const { return edges.size(); } //FIXME: What is this? … … 138 110 nodes.push_back(NodeT()); //FIXME: Hmmm... 139 111 140 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); 141 i!=dyn_node_maps.end(); ++i) (**i).add(n); 142 112 113 node_maps.add(n); 143 114 return n; 144 115 } … … 151 122 nodes[u.n].first_out=nodes[v.n].first_in=e.n; 152 123 153 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin(); 154 i!=dyn_edge_maps.end(); ++i) (**i).add(e); 124 edge_maps.add(e); 155 125 156 126 return e; … … 173 143 } 174 144 175 void clear() {nodes.clear();edges.clear();} 145 void clear() { 146 edge_maps.clear(); 147 edges.clear(); 148 node_maps.clear(); 149 nodes.clear(); 150 } 176 151 177 152 class Node { … … 289 264 // ///Validity check 290 265 // operator bool() { return Edge::operator bool(); } 291 };292 293 template <typename T> class NodeMap : public DynMapBase<Node>294 {295 std::vector<T> container;296 297 public:298 typedef T ValueType;299 typedef Node KeyType;300 301 NodeMap(const SmartGraph &_G) :302 DynMapBase<Node>(_G), container(_G.maxNodeId())303 {304 G->dyn_node_maps.push_back(this);305 }306 NodeMap(const SmartGraph &_G,const T &t) :307 DynMapBase<Node>(_G), container(_G.maxNodeId(),t)308 {309 G->dyn_node_maps.push_back(this);310 }311 312 NodeMap(const NodeMap<T> &m) :313 DynMapBase<Node>(*m.G), container(m.container)314 {315 G->dyn_node_maps.push_back(this);316 }317 318 template<typename TT> friend class NodeMap;319 320 ///\todo It can copy between different types.321 ///\todo We could use 'copy'322 template<typename TT> NodeMap(const NodeMap<TT> &m) :323 DynMapBase<Node>(*m.G), container(m.container.size())324 {325 G->dyn_node_maps.push_back(this);326 typename std::vector<TT>::const_iterator i;327 for(typename std::vector<TT>::const_iterator i=m.container.begin();328 i!=m.container.end();329 i++)330 container.push_back(*i);331 }332 ~NodeMap()333 {334 if(G) {335 std::vector<DynMapBase<Node>* >::iterator i;336 for(i=G->dyn_node_maps.begin();337 i!=G->dyn_node_maps.end() && *i!=this; ++i) ;338 //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...339 //A better way to do that: (Is this really important?)340 if(*i==this) {341 *i=G->dyn_node_maps.back();342 G->dyn_node_maps.pop_back();343 }344 }345 }346 347 void add(const Node k)348 {349 if(k.n>=int(container.size())) container.resize(k.n+1);350 }351 352 void erase(const Node) { }353 354 void set(Node n, T a) { container[n.n]=a; }355 //'T& operator[](Node n)' would be wrong here356 typename std::vector<T>::reference357 operator[](Node n) { return container[n.n]; }358 //'const T& operator[](Node n)' would be wrong here359 typename std::vector<T>::const_reference360 operator[](Node n) const { return container[n.n]; }361 362 ///\warning There is no safety check at all!363 ///Using operator = between maps attached to different graph may364 ///cause serious problem.365 ///\todo Is this really so?366 ///\todo It can copy between different types.367 const NodeMap<T>& operator=(const NodeMap<T> &m)368 {369 container = m.container;370 return *this;371 }372 template<typename TT>373 const NodeMap<T>& operator=(const NodeMap<TT> &m)374 {375 std::copy(m.container.begin(), m.container.end(), container.begin());376 return *this;377 }378 379 void update() {} //Useless for Dynamic Maps380 void update(T a) {} //Useless for Dynamic Maps381 };382 383 template <typename T> class EdgeMap : public DynMapBase<Edge>384 {385 std::vector<T> container;386 387 public:388 typedef T ValueType;389 typedef Edge KeyType;390 391 EdgeMap(const SmartGraph &_G) :392 DynMapBase<Edge>(_G), container(_G.maxEdgeId())393 {394 //FIXME: What if there are empty Id's?395 //FIXME: Can I use 'this' in a constructor?396 G->dyn_edge_maps.push_back(this);397 }398 EdgeMap(const SmartGraph &_G,const T &t) :399 DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)400 {401 G->dyn_edge_maps.push_back(this);402 }403 EdgeMap(const EdgeMap<T> &m) :404 DynMapBase<Edge>(*m.G), container(m.container)405 {406 G->dyn_edge_maps.push_back(this);407 }408 409 template<typename TT> friend class EdgeMap;410 411 ///\todo It can copy between different types.412 template<typename TT> EdgeMap(const EdgeMap<TT> &m)413 : DynMapBase<Edge>(*m.G), container(m.container.size())414 {415 G->dyn_edge_maps.push_back(this);416 typename std::vector<TT>::const_iterator i;417 for(typename std::vector<TT>::const_iterator i=m.container.begin();418 i!=m.container.end();419 i++)420 container.push_back(*i);421 }422 ~EdgeMap()423 {424 if(G) {425 std::vector<DynMapBase<Edge>* >::iterator i;426 for(i=G->dyn_edge_maps.begin();427 i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;428 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...429 //A better way to do that: (Is this really important?)430 if(*i==this) {431 *i=G->dyn_edge_maps.back();432 G->dyn_edge_maps.pop_back();433 }434 }435 }436 437 void add(const Edge k)438 {439 if(k.n>=int(container.size())) container.resize(k.n+1);440 }441 void erase(const Edge) { }442 443 void set(Edge n, T a) { container[n.n]=a; }444 //T get(Edge n) const { return container[n.n]; }445 typename std::vector<T>::reference446 operator[](Edge n) { return container[n.n]; }447 typename std::vector<T>::const_reference448 operator[](Edge n) const { return container[n.n]; }449 450 ///\warning There is no safety check at all!451 ///Using operator = between maps attached to different graph may452 ///cause serious problem.453 ///\todo Is this really so?454 ///\todo It can copy between different types.455 const EdgeMap<T>& operator=(const EdgeMap<T> &m)456 {457 container = m.container;458 return *this;459 }460 template<typename TT>461 const EdgeMap<T>& operator=(const EdgeMap<TT> &m)462 {463 std::copy(m.container.begin(), m.container.end(), container.begin());464 return *this;465 }466 467 void update() {} //Useless for DynMaps468 void update(T a) {} //Useless for DynMaps469 266 }; 470 267 … … 494 291 { 495 292 public: 496 template<typename T> class SymEdgeMap; 497 template<typename T> friend class SymEdgeMap; 293 typedef SymSmartGraph Graph; 294 295 KEEP_NODE_MAP(SmartGraph); 296 KEEP_EDGE_MAP(SmartGraph); 297 298 CREATE_SYM_EDGE_MAP_REGISTRY; 299 CREATE_SYM_EDGE_MAP_FACTORY(ArrayMapFactory); 300 IMPORT_SYM_EDGE_MAP(SymEdgeMapFactory); 498 301 499 302 SymSmartGraph() : SmartGraph() { } … … 518 321 } 519 322 520 ///Common data storage for the edge pairs.521 522 ///This map makes it possible to store data shared by the oppositely523 ///directed pairs of edges.524 template <typename T> class SymEdgeMap : public DynMapBase<Edge>525 {526 std::vector<T> container;527 528 public:529 typedef T ValueType;530 typedef Edge KeyType;531 532 SymEdgeMap(const SymSmartGraph &_G) :533 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)534 {535 static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.push_back(this);536 }537 SymEdgeMap(const SymSmartGraph &_G,const T &t) :538 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)539 {540 G->dyn_edge_maps.push_back(this);541 }542 543 SymEdgeMap(const SymEdgeMap<T> &m) :544 DynMapBase<SymEdge>(*m.G), container(m.container)545 {546 G->dyn_node_maps.push_back(this);547 }548 549 // template<typename TT> friend class SymEdgeMap;550 551 ///\todo It can copy between different types.552 ///553 554 template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m)555 : DynMapBase<SymEdge>(*m.G), container(m.container.size())556 {557 G->dyn_node_maps.push_back(this);558 typename std::vector<TT>::const_iterator i;559 for(typename std::vector<TT>::const_iterator i=m.container.begin();560 i!=m.container.end();561 i++)562 container.push_back(*i);563 }564 565 ~SymEdgeMap()566 {567 if(G) {568 std::vector<DynMapBase<Edge>* >::iterator i;569 for(i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.begin();570 i!=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.end()571 && *i!=this; ++i) ;572 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...573 //A better way to do that: (Is this really important?)574 if(*i==this) {575 *i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.back();576 static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.pop_back();577 }578 }579 }580 581 void add(const Edge k)582 {583 if(!k.idref()%2&&k.idref()/2>=int(container.size()))584 container.resize(k.idref()/2+1);585 }586 void erase(const Edge k) { }587 588 void set(Edge n, T a) { container[n.idref()/2]=a; }589 //T get(Edge n) const { return container[n.idref()/2]; }590 typename std::vector<T>::reference591 operator[](Edge n) { return container[n.idref()/2]; }592 typename std::vector<T>::const_reference593 operator[](Edge n) const { return container[n.idref()/2]; }594 595 ///\warning There is no safety check at all!596 ///Using operator = between maps attached to different graph may597 ///cause serious problem.598 ///\todo Is this really so?599 ///\todo It can copy between different types.600 const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)601 {602 container = m.container;603 return *this;604 }605 template<typename TT>606 const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)607 {608 std::copy(m.container.begin(), m.container.end(), container.begin());609 return *this;610 }611 612 void update() {} //Useless for DynMaps613 void update(T a) {} //Useless for DynMaps614 615 };616 323 617 324 }; 618 325 619 326 /// @} 620 621 327 } //namespace hugo 622 328
Note: See TracChangeset
for help on using the changeset viewer.