3 #ifndef HUGO_SMART_GRAPH_H
4 #define HUGO_SMART_GRAPH_H
7 ///\brief ListGraph and SymListGraph classes.
18 ///A smart graph class.
20 ///This is a simple and fast erasable graph implementation.
22 ///It conforms to the graph interface documented under
23 ///the description of \ref GraphSkeleton.
24 ///\sa \ref GraphSkeleton.
27 //Nodes are double linked.
28 //The free nodes are only single linked using the "next" field.
31 int first_in,first_out;
35 //Edges are double linked.
36 //The free edges are only single linked using the "next_in" field.
40 int prev_in, prev_out;
41 int next_in, next_out;
42 //FIXME: is this necessary?
43 // EdgeT() : next_in(-1), next_out(-1) prev_in(-1), prev_out(-1) {}
46 std::vector<NodeT> nodes;
51 std::vector<EdgeT> edges;
57 template <typename Key> class DynMapBase
62 virtual void add(const Key k) = NULL;
63 virtual void erase(const Key k) = NULL;
64 DynMapBase(const ListGraph &_G) : G(&_G) {}
65 virtual ~DynMapBase() {}
66 friend class ListGraph;
70 template <typename T> class EdgeMap;
71 template <typename T> class NodeMap;
79 ///\bug It must be public because of SymEdgeMap.
81 mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
82 ///\bug It must be public because of SymEdgeMap.
84 mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
93 template <typename T> class NodeMap;
94 template <typename T> class EdgeMap;
98 ListGraph() : nodes(), first_node(-1),
99 first_free_node(-1), edges(), first_free_edge(-1) {}
100 ListGraph(const ListGraph &_g) : nodes(_g.nodes), first_node(_g.first_node),
101 first_free_node(_g.first_free_node),
103 first_free_edge(_g.first_free_edge) {}
107 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
108 i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
109 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
110 i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
113 int nodeNum() const { return nodes.size(); } //FIXME: What is this?
114 int edgeNum() const { return edges.size(); } //FIXME: What is this?
116 ///\bug This function does something different than
117 ///its name would suggests...
118 int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
119 ///\bug This function does something different than
120 ///its name would suggests...
121 int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
123 Node tail(Edge e) const { return edges[e.n].tail; }
124 Node head(Edge e) const { return edges[e.n].head; }
126 Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
127 Node aNode(InEdgeIt e) const { return edges[e.n].head; }
129 Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
130 Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
132 NodeIt& first(NodeIt& v) const {
133 v=NodeIt(*this); return v; }
134 EdgeIt& first(EdgeIt& e) const {
135 e=EdgeIt(*this); return e; }
136 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
137 e=OutEdgeIt(*this,v); return e; }
138 InEdgeIt& first(InEdgeIt& e, const Node v) const {
139 e=InEdgeIt(*this,v); return e; }
141 // template< typename It >
142 // It first() const { It e; first(e); return e; }
144 // template< typename It >
145 // It first(Node v) const { It e; first(e,v); return e; }
147 bool valid(Edge e) const { return e.n!=-1; }
148 bool valid(Node n) const { return n.n!=-1; }
150 void setInvalid(Edge &e) { e.n=-1; }
151 void setInvalid(Node &n) { n.n=-1; }
153 template <typename It> It getNext(It it) const
154 { It tmp(it); return next(tmp); }
156 NodeIt& next(NodeIt& it) const {
157 it.n=nodes[it.n].next;
160 OutEdgeIt& next(OutEdgeIt& it) const
161 { it.n=edges[it.n].next_out; return it; }
162 InEdgeIt& next(InEdgeIt& it) const
163 { it.n=edges[it.n].next_in; return it; }
164 EdgeIt& next(EdgeIt& it) const {
165 if(edges[it.n].next_in!=-1) {
166 it.n=edges[it.n].next_in;
170 for(n=nodes[edges[it.n].head].next;
171 n!=-1 && nodes[n].first_in == -1;
173 it.n = (n==-1)?-1:nodes[n].first_in;
178 int id(Node v) const { return v.n; }
179 int id(Edge e) const { return e.n; }
181 /// Adds a new node to the graph.
183 /// \todo It adds the nodes in a reversed order.
184 /// (i.e. the lastly added node becomes the first.)
188 if(first_free_node==-1)
191 nodes.push_back(NodeT());
195 first_free_node = nodes[n].next;
198 nodes[n].next = first_node;
199 if(first_node != -1) nodes[first_node].prev = n;
203 nodes[n].first_in = nodes[n].first_out = -1;
207 //Update dynamic maps
208 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
209 i!=dyn_node_maps.end(); ++i) (**i).add(nn);
214 Edge addEdge(Node u, Node v) {
217 if(first_free_edge==-1)
220 edges.push_back(EdgeT());
224 first_free_edge = edges[n].next_in;
227 edges[n].tail = u.n; edges[n].head = v.n;
229 edges[n].next_out = nodes[u.n].first_out;
230 if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n;
231 edges[n].next_in = nodes[v.n].first_in;
232 if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n;
233 edges[n].prev_in = edges[n].prev_out = -1;
235 nodes[u.n].first_out = nodes[v.n].first_in = n;
239 //Update dynamic maps
240 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
241 i!=dyn_edge_maps.end(); ++i) (**i).add(e);
247 void eraseEdge(int n) {
249 if(edges[n].next_in!=-1)
250 edges[edges[n].next_in].prev_in = edges[n].prev_in;
251 if(edges[n].prev_in!=-1)
252 edges[edges[n].prev_in].next_in = edges[n].next_in;
253 else nodes[edges[n].head].first_in = edges[n].next_in;
255 if(edges[n].next_out!=-1)
256 edges[edges[n].next_out].prev_out = edges[n].prev_out;
257 if(edges[n].prev_out!=-1)
258 edges[edges[n].prev_out].next_out = edges[n].next_out;
259 else nodes[edges[n].tail].first_out = edges[n].next_out;
261 edges[n].next_in = first_free_edge;
262 first_free_edge = -1;
264 //Update dynamic maps
266 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
267 i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
272 void erase(Node nn) {
276 while((m=nodes[n].first_in)!=-1) eraseEdge(m);
277 while((m=nodes[n].first_out)!=-1) eraseEdge(m);
279 if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
280 if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
281 else first_node = nodes[n].next;
283 nodes[n].next = first_free_node;
286 //Update dynamic maps
287 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
288 i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
291 void erase(Edge e) { eraseEdge(e.n); }
293 ///\bug Dynamic maps must be updated!
296 nodes.clear();edges.clear();
297 first_node=first_free_node=first_free_edge=-1;
301 friend class ListGraph;
302 template <typename T> friend class NodeMap;
305 friend class OutEdgeIt;
306 friend class InEdgeIt;
307 friend class SymEdge;
311 friend int ListGraph::id(Node v) const;
315 Node (Invalid i) { n=-1; }
316 bool operator==(const Node i) const {return n==i.n;}
317 bool operator!=(const Node i) const {return n!=i.n;}
318 bool operator<(const Node i) const {return n<i.n;}
321 class NodeIt : public Node {
322 friend class ListGraph;
324 NodeIt() : Node() { }
325 NodeIt(Invalid i) : Node(i) { }
326 NodeIt(const ListGraph& G) : Node(G.first_node) { }
330 friend class ListGraph;
331 template <typename T> friend class EdgeMap;
333 //template <typename T> friend class SymListGraph::SymEdgeMap;
334 //friend Edge SymListGraph::opposite(Edge) const;
340 friend int ListGraph::id(Edge e) const;
345 Edge (Invalid) { n=-1; }
346 bool operator==(const Edge i) const {return n==i.n;}
347 bool operator!=(const Edge i) const {return n!=i.n;}
348 bool operator<(const Edge i) const {return n<i.n;}
349 ///\bug This is a workaround until somebody tells me how to
350 ///make class \c SymListGraph::SymEdgeMap friend of Edge
351 int &idref() {return n;}
352 const int &idref() const {return n;}
355 class EdgeIt : public Edge {
356 friend class ListGraph;
358 EdgeIt(const ListGraph& G) : Edge() {
361 m!=-1 && G.nodes[m].first_in == -1; m = G.nodes[m].next);
362 n = (m==-1)?-1:G.nodes[m].first_in;
364 EdgeIt (Invalid i) : Edge(i) { }
365 EdgeIt() : Edge() { }
366 ///\bug This is a workaround until somebody tells me how to
367 ///make class \c SymListGraph::SymEdgeMap friend of Edge
368 int &idref() {return n;}
371 class OutEdgeIt : public Edge {
372 friend class ListGraph;
374 OutEdgeIt() : Edge() { }
375 OutEdgeIt (Invalid i) : Edge(i) { }
377 OutEdgeIt(const ListGraph& G,const Node v)
378 : Edge(G.nodes[v.n].first_out) {}
381 class InEdgeIt : public Edge {
382 friend class ListGraph;
384 InEdgeIt() : Edge() { }
385 InEdgeIt (Invalid i) : Edge(i) { }
386 InEdgeIt(const ListGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
389 template <typename T> class NodeMap : public DynMapBase<Node>
391 std::vector<T> container;
395 typedef Node KeyType;
397 NodeMap(const ListGraph &_G) :
398 DynMapBase<Node>(_G), container(_G.maxNodeId())
400 G->dyn_node_maps.push_back(this);
402 NodeMap(const ListGraph &_G,const T &t) :
403 DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
405 G->dyn_node_maps.push_back(this);
408 NodeMap(const NodeMap<T> &m) :
409 DynMapBase<Node>(*m.G), container(m.container)
411 G->dyn_node_maps.push_back(this);
414 template<typename TT> friend class NodeMap;
416 ///\todo It can copy between different types.
418 template<typename TT> NodeMap(const NodeMap<TT> &m) :
419 DynMapBase<Node>(*m.G)
421 G->dyn_node_maps.push_back(this);
422 typename std::vector<TT>::const_iterator i;
423 for(typename std::vector<TT>::const_iterator i=m.container.begin();
424 i!=m.container.end();
426 container.push_back(*i);
431 std::vector<DynMapBase<Node>* >::iterator i;
432 for(i=G->dyn_node_maps.begin();
433 i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
434 //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
435 //A better way to do that: (Is this really important?)
437 *i=G->dyn_node_maps.back();
438 G->dyn_node_maps.pop_back();
443 void add(const Node k)
445 if(k.n>=int(container.size())) container.resize(k.n+1);
448 void erase(const Node) { }
450 void set(Node n, T a) { container[n.n]=a; }
451 //'T& operator[](Node n)' would be wrong here
452 typename std::vector<T>::reference
453 operator[](Node n) { return container[n.n]; }
454 //'const T& operator[](Node n)' would be wrong here
455 typename std::vector<T>::const_reference
456 operator[](Node n) const { return container[n.n]; }
458 ///\warning There is no safety check at all!
459 ///Using operator = between maps attached to different graph may
460 ///cause serious problem.
461 ///\todo Is this really so?
462 ///\todo It can copy between different types.
463 const NodeMap<T>& operator=(const NodeMap<T> &m)
465 container = m.container;
468 template<typename TT>
469 const NodeMap<T>& operator=(const NodeMap<TT> &m)
471 copy(m.container.begin(), m.container.end(), container.begin());
475 void update() {} //Useless for Dynamic Maps
476 void update(T a) {} //Useless for Dynamic Maps
479 template <typename T> class EdgeMap : public DynMapBase<Edge>
481 std::vector<T> container;
485 typedef Edge KeyType;
487 EdgeMap(const ListGraph &_G) :
488 DynMapBase<Edge>(_G), container(_G.maxEdgeId())
490 //FIXME: What if there are empty Id's?
491 //FIXME: Can I use 'this' in a constructor?
492 G->dyn_edge_maps.push_back(this);
494 EdgeMap(const ListGraph &_G,const T &t) :
495 DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
497 G->dyn_edge_maps.push_back(this);
499 EdgeMap(const EdgeMap<T> &m) :
500 DynMapBase<Edge>(*m.G), container(m.container)
502 G->dyn_node_maps.push_back(this);
505 template<typename TT> friend class EdgeMap;
507 ///\todo It can copy between different types.
509 template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
510 DynMapBase<Edge>(*m.G)
512 G->dyn_node_maps.push_back(this);
513 typename std::vector<TT>::const_iterator i;
514 for(typename std::vector<TT>::const_iterator i=m.container.begin();
515 i!=m.container.end();
517 container.push_back(*i);
522 std::vector<DynMapBase<Edge>* >::iterator i;
523 for(i=G->dyn_edge_maps.begin();
524 i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
525 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
526 //A better way to do that: (Is this really important?)
528 *i=G->dyn_edge_maps.back();
529 G->dyn_edge_maps.pop_back();
534 void add(const Edge k)
536 if(k.n>=int(container.size())) container.resize(k.n+1);
538 void erase(const Edge) { }
540 void set(Edge n, T a) { container[n.n]=a; }
541 //T get(Edge n) const { return container[n.n]; }
542 typename std::vector<T>::reference
543 operator[](Edge n) { return container[n.n]; }
544 typename std::vector<T>::const_reference
545 operator[](Edge n) const { return container[n.n]; }
547 ///\warning There is no safety check at all!
548 ///Using operator = between maps attached to different graph may
549 ///cause serious problem.
550 ///\todo Is this really so?
551 ///\todo It can copy between different types.
552 const EdgeMap<T>& operator=(const EdgeMap<T> &m)
554 container = m.container;
557 template<typename TT>
558 const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
560 copy(m.container.begin(), m.container.end(), container.begin());
564 void update() {} //Useless for DynMaps
565 void update(T a) {} //Useless for DynMaps
570 ///Graph for bidirectional edges.
572 ///The purpose of this graph structure is to handle graphs
573 ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
574 ///of oppositely directed edges.
575 ///There is a new edge map type called
576 ///\ref SymListGraph::SymEdgeMap "SymEdgeMap"
577 ///that complements this
579 ///storing shared values for the edge pairs. The usual
580 ///\ref GraphSkeleton::EdgeMap "EdgeMap"
584 ///The oppositely directed edge can also be obtained easily
585 ///using \ref opposite.
587 ///Here erase(Edge) deletes a pair of edges.
589 ///\todo this date structure need some reconsiderations. Maybe it
590 ///should be implemented independently from ListGraph.
592 class SymListGraph : public ListGraph
595 template<typename T> class SymEdgeMap;
596 template<typename T> friend class SymEdgeMap;
598 SymListGraph() : ListGraph() { }
599 SymListGraph(const ListGraph &_g) : ListGraph(_g) { }
600 ///Adds a pair of oppositely directed edges to the graph.
601 Edge addEdge(Node u, Node v)
603 Edge e = ListGraph::addEdge(u,v);
604 ListGraph::addEdge(v,u);
608 void erase(Node n) { ListGraph::erase(n); }
609 ///The oppositely directed edge.
611 ///Returns the oppositely directed
612 ///pair of the edge \c e.
613 Edge opposite(Edge e) const
616 f.idref() = e.idref() - 2*(e.idref()%2) + 1;
620 ///Removes a pair of oppositely directed edges to the graph.
622 ListGraph::erase(opposite(e));
626 ///Common data storage for the edge pairs.
628 ///This map makes it possible to store data shared by the oppositely
629 ///directed pairs of edges.
630 template <typename T> class SymEdgeMap : public DynMapBase<Edge>
632 std::vector<T> container;
636 typedef Edge KeyType;
638 SymEdgeMap(const SymListGraph &_G) :
639 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
641 static_cast<const SymListGraph*>(G)->dyn_edge_maps.push_back(this);
643 SymEdgeMap(const SymListGraph &_G,const T &t) :
644 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
646 G->dyn_edge_maps.push_back(this);
649 SymEdgeMap(const SymEdgeMap<T> &m) :
650 DynMapBase<SymEdge>(*m.G), container(m.container)
652 G->dyn_node_maps.push_back(this);
655 // template<typename TT> friend class SymEdgeMap;
657 ///\todo It can copy between different types.
660 template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :
661 DynMapBase<SymEdge>(*m.G)
663 G->dyn_node_maps.push_back(this);
664 typename std::vector<TT>::const_iterator i;
665 for(typename std::vector<TT>::const_iterator i=m.container.begin();
666 i!=m.container.end();
668 container.push_back(*i);
674 std::vector<DynMapBase<Edge>* >::iterator i;
675 for(i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.begin();
676 i!=static_cast<const SymListGraph*>(G)->dyn_edge_maps.end()
678 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
679 //A better way to do that: (Is this really important?)
681 *i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.back();
682 static_cast<const SymListGraph*>(G)->dyn_edge_maps.pop_back();
687 void add(const Edge k)
689 if(!k.idref()%2&&k.idref()/2>=int(container.size()))
690 container.resize(k.idref()/2+1);
692 void erase(const Edge k) { }
694 void set(Edge n, T a) { container[n.idref()/2]=a; }
695 //T get(Edge n) const { return container[n.idref()/2]; }
696 typename std::vector<T>::reference
697 operator[](Edge n) { return container[n.idref()/2]; }
698 typename std::vector<T>::const_reference
699 operator[](Edge n) const { return container[n.idref()/2]; }
701 ///\warning There is no safety check at all!
702 ///Using operator = between maps attached to different graph may
703 ///cause serious problem.
704 ///\todo Is this really so?
705 ///\todo It can copy between different types.
706 const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
708 container = m.container;
711 template<typename TT>
712 const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
714 copy(m.container.begin(), m.container.end(), container.begin());
718 void update() {} //Useless for DynMaps
719 void update(T a) {} //Useless for DynMaps
726 ///A smart graph class.
728 ///This is a simple and fast erasable graph implementation.
730 ///It conforms to the graph interface documented under
731 ///the description of \ref GraphSkeleton.
732 ///\sa \ref GraphSkeleton.
735 //Nodes are double linked.
736 //The free nodes are only single linked using the "next" field.
739 int first_in,first_out;
744 std::vector<NodeT> nodes;
747 //The first free node
752 template <typename Key> class DynMapBase
757 virtual void add(const Key k) = NULL;
758 virtual void erase(const Key k) = NULL;
759 DynMapBase(const NodeSet &_G) : G(&_G) {}
760 virtual ~DynMapBase() {}
761 friend class NodeSet;
765 template <typename T> class EdgeMap;
766 template <typename T> class NodeMap;
774 ///\bug It must be public because of SymEdgeMap.
776 mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
777 //mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
786 template <typename T> class NodeMap;
787 template <typename T> class EdgeMap;
791 NodeSet() : nodes(), first_node(-1),
792 first_free_node(-1) {}
793 NodeSet(const NodeSet &_g) : nodes(_g.nodes), first_node(_g.first_node),
794 first_free_node(_g.first_free_node) {}
798 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
799 i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
800 //for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
801 // i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
804 int nodeNum() const { return nodes.size(); } //FIXME: What is this?
805 int edgeNum() const { return 0; } //FIXME: What is this?
807 ///\bug This function does something different than
808 ///its name would suggests...
809 int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
810 ///\bug This function does something different than
811 ///its name would suggests...
812 int maxEdgeId() const { return 0; } //FIXME: What is this?
814 Node tail(Edge e) const { return INVALID; }
815 Node head(Edge e) const { return INVALID; }
817 Node aNode(OutEdgeIt e) const { return INVALID; }
818 Node aNode(InEdgeIt e) const { return INVALID; }
820 Node bNode(OutEdgeIt e) const { return INVALID; }
821 Node bNode(InEdgeIt e) const { return INVALID; }
823 NodeIt& first(NodeIt& v) const {
824 v=NodeIt(*this); return v; }
825 EdgeIt& first(EdgeIt& e) const {
826 e=EdgeIt(*this); return e; }
827 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
828 e=OutEdgeIt(*this,v); return e; }
829 InEdgeIt& first(InEdgeIt& e, const Node v) const {
830 e=InEdgeIt(*this,v); return e; }
832 // template< typename It >
833 // It first() const { It e; first(e); return e; }
835 // template< typename It >
836 // It first(Node v) const { It e; first(e,v); return e; }
838 bool valid(Edge e) const { return false; }
839 bool valid(Node n) const { return n.n!=-1; }
841 void setInvalid(Edge &e) { }
842 void setInvalid(Node &n) { n.n=-1; }
844 template <typename It> It getNext(It it) const
845 { It tmp(it); return next(tmp); }
847 NodeIt& next(NodeIt& it) const {
848 it.n=nodes[it.n].next;
851 OutEdgeIt& next(OutEdgeIt& it) const { return it; }
852 InEdgeIt& next(InEdgeIt& it) const { return it; }
853 EdgeIt& next(EdgeIt& it) const { return it; }
855 int id(Node v) const { return v.n; }
856 int id(Edge e) const { return -1; }
858 /// Adds a new node to the graph.
860 /// \todo It adds the nodes in a reversed order.
861 /// (i.e. the lastly added node becomes the first.)
865 if(first_free_node==-1)
868 nodes.push_back(NodeT());
872 first_free_node = nodes[n].next;
875 nodes[n].next = first_node;
876 if(first_node != -1) nodes[first_node].prev = n;
880 nodes[n].first_in = nodes[n].first_out = -1;
884 //Update dynamic maps
885 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
886 i!=dyn_node_maps.end(); ++i) (**i).add(nn);
891 void erase(Node nn) {
894 if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
895 if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
896 else first_node = nodes[n].next;
898 nodes[n].next = first_free_node;
901 //Update dynamic maps
902 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
903 i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
906 ///\bug Dynamic maps must be updated!
910 first_node = first_free_node = -1;
914 friend class NodeSet;
915 template <typename T> friend class NodeMap;
918 friend class OutEdgeIt;
919 friend class InEdgeIt;
923 friend int NodeSet::id(Node v) const;
927 Node (Invalid i) { n=-1; }
928 bool operator==(const Node i) const {return n==i.n;}
929 bool operator!=(const Node i) const {return n!=i.n;}
930 bool operator<(const Node i) const {return n<i.n;}
933 class NodeIt : public Node {
934 friend class NodeSet;
936 NodeIt(const NodeSet& G) : Node(G.first_node) { }
937 NodeIt() : Node() { }
941 //friend class NodeSet;
942 //template <typename T> friend class EdgeMap;
944 //template <typename T> friend class SymNodeSet::SymEdgeMap;
945 //friend Edge SymNodeSet::opposite(Edge) const;
947 // friend class Node;
948 // friend class NodeIt;
950 //friend int NodeSet::id(Edge e) const;
955 bool operator==(const Edge i) const {return true;}
956 bool operator!=(const Edge i) const {return false;}
957 bool operator<(const Edge i) const {return false;}
958 ///\bug This is a workaround until somebody tells me how to
959 ///make class \c SymNodeSet::SymEdgeMap friend of Edge
960 // int idref() {return -1;}
961 // int idref() const {return -1;}
964 class EdgeIt : public Edge {
965 //friend class NodeSet;
967 EdgeIt(const NodeSet& G) : Edge() { }
968 EdgeIt (Invalid i) : Edge(i) { }
969 EdgeIt() : Edge() { }
970 ///\bug This is a workaround until somebody tells me how to
971 ///make class \c SymNodeSet::SymEdgeMap friend of Edge
972 // int idref() {return -1;}
975 class OutEdgeIt : public Edge {
976 friend class NodeSet;
978 OutEdgeIt() : Edge() { }
979 OutEdgeIt (Invalid i) : Edge(i) { }
980 OutEdgeIt(const NodeSet& G,const Node v) : Edge() {}
983 class InEdgeIt : public Edge {
984 friend class NodeSet;
986 InEdgeIt() : Edge() { }
987 InEdgeIt (Invalid i) : Edge(i) { }
988 InEdgeIt(const NodeSet& G,Node v) :Edge() {}
991 template <typename T> class NodeMap : public DynMapBase<Node>
993 std::vector<T> container;
997 typedef Node KeyType;
999 NodeMap(const NodeSet &_G) :
1000 DynMapBase<Node>(_G), container(_G.maxNodeId())
1002 G->dyn_node_maps.push_back(this);
1004 NodeMap(const NodeSet &_G,const T &t) :
1005 DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
1007 G->dyn_node_maps.push_back(this);
1010 NodeMap(const NodeMap<T> &m) :
1011 DynMapBase<Node>(*m.G), container(m.container)
1013 G->dyn_node_maps.push_back(this);
1016 template<typename TT> friend class NodeMap;
1018 ///\todo It can copy between different types.
1020 template<typename TT> NodeMap(const NodeMap<TT> &m) :
1021 DynMapBase<Node>(*m.G)
1023 G->dyn_node_maps.push_back(this);
1024 typename std::vector<TT>::const_iterator i;
1025 for(typename std::vector<TT>::const_iterator i=m.container.begin();
1026 i!=m.container.end();
1028 container.push_back(*i);
1033 std::vector<DynMapBase<Node>* >::iterator i;
1034 for(i=G->dyn_node_maps.begin();
1035 i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
1036 //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
1037 //A better way to do that: (Is this really important?)
1039 *i=G->dyn_node_maps.back();
1040 G->dyn_node_maps.pop_back();
1045 void add(const Node k)
1047 if(k.n>=int(container.size())) container.resize(k.n+1);
1050 void erase(const Node) { }
1052 void set(Node n, T a) { container[n.n]=a; }
1053 //'T& operator[](Node n)' would be wrong here
1054 typename std::vector<T>::reference
1055 operator[](Node n) { return container[n.n]; }
1056 //'const T& operator[](Node n)' would be wrong here
1057 typename std::vector<T>::const_reference
1058 operator[](Node n) const { return container[n.n]; }
1060 ///\warning There is no safety check at all!
1061 ///Using operator = between maps attached to different graph may
1062 ///cause serious problem.
1063 ///\todo Is this really so?
1064 ///\todo It can copy between different types.
1065 const NodeMap<T>& operator=(const NodeMap<T> &m)
1067 container = m.container;
1070 template<typename TT>
1071 const NodeMap<T>& operator=(const NodeMap<TT> &m)
1073 copy(m.container.begin(), m.container.end(), container.begin());
1077 void update() {} //Useless for Dynamic Maps
1078 void update(T a) {} //Useless for Dynamic Maps
1081 template <typename T> class EdgeMap
1084 typedef T ValueType;
1085 typedef Edge KeyType;
1087 EdgeMap(const NodeSet &) { }
1088 EdgeMap(const NodeSet &,const T &) { }
1089 EdgeMap(const EdgeMap<T> &) { }
1090 // template<typename TT> friend class EdgeMap;
1092 ///\todo It can copy between different types.
1094 template<typename TT> EdgeMap(const EdgeMap<TT> &) { }
1097 void add(const Edge ) { }
1098 void erase(const Edge) { }
1100 void set(Edge, T) { }
1101 //T get(Edge n) const { return container[n.n]; }
1102 ValueType &operator[](Edge) { return *((T*)(NULL)); }
1103 const ValueType &operator[](Edge) const { return *((T*)(NULL)); }
1105 const EdgeMap<T>& operator=(const EdgeMap<T> &) { return *this; }
1107 template<typename TT>
1108 const EdgeMap<T>& operator=(const EdgeMap<TT> &m) { return *this; }
1117 ///This is a simple and fast erasable graph implementation.
1119 ///It conforms to the graph interface documented under
1120 ///the description of \ref GraphSkeleton.
1121 ///\sa \ref GraphSkeleton.
1122 template<typename GG>
1125 typedef GG NodeGraphType;
1131 //Edges are double linked.
1132 //The free edges are only single linked using the "next_in" field.
1135 int first_in,first_out;
1136 NodeT() : first_in(-1), first_out(-1) { }
1142 int prev_in, prev_out;
1143 int next_in, next_out;
1147 typename NodeGraphType::NodeMap<NodeT> nodes;
1149 std::vector<EdgeT> edges;
1150 //The first free edge
1151 int first_free_edge;
1155 template <typename Key> class DynMapBase
1160 virtual void add(const Key k) = NULL;
1161 virtual void erase(const Key k) = NULL;
1162 DynMapBase(const EdgeSet &_G) : G(&_G) {}
1163 virtual ~DynMapBase() {}
1164 friend class EdgeSet;
1168 //template <typename T> class NodeMap;
1169 template <typename T> class EdgeMap;
1177 // mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
1178 ///\bug It must be public because of SymEdgeMap.
1180 mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
1189 template <typename T> class NodeMap;
1190 template <typename T> class EdgeMap;
1194 EdgeSet(const NodeGraphType &_G) : G(_G),
1196 first_free_edge(-1) {}
1197 EdgeSet(const EdgeSet &_g) : G(_g.G), nodes(_g.G), edges(_g.edges),
1198 first_free_edge(_g.first_free_edge) {}
1202 // for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
1203 // i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
1204 for(typename std::vector<DynMapBase<Edge> * >::iterator
1205 i=dyn_edge_maps.begin();
1206 i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
1209 int nodeNum() const { return G.nodeNum(); } //FIXME: What is this?
1210 int edgeNum() const { return edges.size(); } //FIXME: What is this?
1212 ///\bug This function does something different than
1213 ///its name would suggests...
1214 int maxNodeId() const { return G.maxNodeId(); } //FIXME: What is this?
1215 ///\bug This function does something different than
1216 ///its name would suggests...
1217 int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
1219 Node tail(Edge e) const { return edges[e.n].tail; }
1220 Node head(Edge e) const { return edges[e.n].head; }
1222 Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
1223 Node aNode(InEdgeIt e) const { return edges[e.n].head; }
1225 Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
1226 Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
1228 NodeIt& first(NodeIt& v) const {
1229 v=NodeIt(*this); return v; }
1230 EdgeIt& first(EdgeIt& e) const {
1231 e=EdgeIt(*this); return e; }
1232 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
1233 e=OutEdgeIt(*this,v); return e; }
1234 InEdgeIt& first(InEdgeIt& e, const Node v) const {
1235 e=InEdgeIt(*this,v); return e; }
1237 // template< typename It >
1238 // It first() const { It e; first(e); return e; }
1240 // template< typename It >
1241 // It first(Node v) const { It e; first(e,v); return e; }
1243 bool valid(Edge e) const { return e.n!=-1; }
1244 bool valid(Node n) const { return G.valid(n); }
1246 void setInvalid(Edge &e) { e.n=-1; }
1247 void setInvalid(Node &n) { G.setInvalid(n); }
1249 template <typename It> It getNext(It it) const
1250 { It tmp(it); return next(tmp); }
1252 NodeIt& next(NodeIt& it) const { G.next(it); return it; }
1253 OutEdgeIt& next(OutEdgeIt& it) const
1254 { it.n=edges[it.n].next_out; return it; }
1255 InEdgeIt& next(InEdgeIt& it) const
1256 { it.n=edges[it.n].next_in; return it; }
1257 EdgeIt& next(EdgeIt& it) const {
1258 if(edges[it.n].next_in!=-1) {
1259 it.n=edges[it.n].next_in;
1262 typename NodeGraphType::Node n;
1263 for(n=G.next(edges[it.n].head);
1264 G.valid(n) && nodes[n].first_in == -1;
1266 it.n = (G.valid(n))?-1:nodes[n].first_in;
1271 int id(Node v) const { return G.id(v); }
1272 int id(Edge e) const { return e.n; }
1274 /// Adds a new node to the graph.
1275 Node addNode() { return G.AddNode(); }
1277 Edge addEdge(Node u, Node v) {
1280 if(first_free_edge==-1)
1283 edges.push_back(EdgeT());
1286 n = first_free_edge;
1287 first_free_edge = edges[n].next_in;
1290 edges[n].tail = u.n; edges[n].head = v.n;
1292 edges[n].next_out = nodes[u.n].first_out;
1293 if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n;
1294 edges[n].next_in = nodes[v.n].first_in;
1295 if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n;
1296 edges[n].prev_in = edges[n].prev_out = -1;
1298 nodes[u.n].first_out = nodes[v.n].first_in = n;
1302 //Update dynamic maps
1303 for(typename std::vector<DynMapBase<Edge> * >::iterator
1304 i=dyn_edge_maps.begin();
1305 i!=dyn_edge_maps.end(); ++i) (**i).add(e);
1311 void eraseEdge(int n) {
1313 if(edges[n].next_in!=-1)
1314 edges[edges[n].next_in].prev_in = edges[n].prev_in;
1315 if(edges[n].prev_in!=-1)
1316 edges[edges[n].prev_in].next_in = edges[n].next_in;
1317 else nodes[edges[n].head].first_in = edges[n].next_in;
1319 if(edges[n].next_out!=-1)
1320 edges[edges[n].next_out].prev_out = edges[n].prev_out;
1321 if(edges[n].prev_out!=-1)
1322 edges[edges[n].prev_out].next_out = edges[n].next_out;
1323 else nodes[edges[n].tail].first_out = edges[n].next_out;
1325 edges[n].next_in = first_free_edge;
1326 first_free_edge = -1;
1328 //Update dynamic maps
1330 for(typename std::vector<DynMapBase<Edge> * >::iterator
1331 i=dyn_edge_maps.begin();
1332 i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
1337 // void erase(Node nn) {
1340 // while((m=nodes[n].first_in)!=-1) eraseEdge(m);
1341 // while((m=nodes[n].first_out)!=-1) eraseEdge(m);
1344 void erase(Edge e) { eraseEdge(e.n); }
1346 // //\bug Dynamic maps must be updated!
1349 // nodes.clear();edges.clear();
1350 // first_node=first_free_node=first_free_edge=-1;
1353 class Node : public NodeGraphType::Node {
1354 friend class EdgeSet;
1355 // template <typename T> friend class NodeMap;
1358 friend class OutEdgeIt;
1359 friend class InEdgeIt;
1360 friend class SymEdge;
1363 friend int EdgeSet::id(Node v) const;
1364 // Node(int nn) {n=nn;}
1366 Node() : NodeGraphType::Node() {}
1367 Node (Invalid i) : NodeGraphType::Node(i) {}
1368 Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {}
1371 class NodeIt : public NodeGraphType::NodeIt {
1372 friend class EdgeSet;
1374 NodeIt() : NodeGraphType::NodeIt() { }
1375 NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {}
1376 NodeIt(const EdgeSet& _G) : NodeGraphType::Node(_G.G) { }
1377 NodeIt(const typename NodeGraphType::NodeIt &n)
1378 : NodeGraphType::NodeIt(n) {}
1379 operator Node() { return Node(*this);}
1383 friend class EdgeSet;
1384 template <typename T> friend class EdgeMap;
1386 //template <typename T> friend class SymEdgeSet::SymEdgeMap;
1387 //friend Edge SymEdgeSet::opposite(Edge) const;
1390 friend class NodeIt;
1393 friend int EdgeSet::id(Edge e) const;
1395 Edge(int nn) {n=nn;}
1398 Edge (Invalid) { n=-1; }
1399 bool operator==(const Edge i) const {return n==i.n;}
1400 bool operator!=(const Edge i) const {return n!=i.n;}
1401 bool operator<(const Edge i) const {return n<i.n;}
1402 ///\bug This is a workaround until somebody tells me how to
1403 ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
1404 int &idref() {return n;}
1405 const int &idref() const {return n;}
1408 class EdgeIt : public Edge {
1409 friend class EdgeSet;
1411 EdgeIt(const EdgeSet& G) : Edge() {
1412 typename NodeGraphType::Node m;
1414 G.valid(m) && nodes[m].first_in == -1; G.next[m]);
1415 n = G.valid(m)?-1:nodes[m].first_in;
1417 EdgeIt (Invalid i) : Edge(i) { }
1418 EdgeIt() : Edge() { }
1419 ///\bug This is a workaround until somebody tells me how to
1420 ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
1421 int &idref() {return n;}
1424 class OutEdgeIt : public Edge {
1425 friend class EdgeSet;
1427 OutEdgeIt() : Edge() { }
1428 OutEdgeIt (Invalid i) : Edge(i) { }
1430 OutEdgeIt(const EdgeSet& G,const Node v) : Edge(nodes[v].first_out) { }
1433 class InEdgeIt : public Edge {
1434 friend class EdgeSet;
1436 InEdgeIt() : Edge() { }
1437 InEdgeIt (Invalid i) : Edge(i) { }
1438 InEdgeIt(const EdgeSet& G,Node v) :Edge(nodes[v].first_in) { }
1441 template <typename T> class NodeMap : public NodeGraphType::NodeMap<T>
1444 NodeMap(const EdgeSet &_G) :
1445 NodeGraphType::NodeMap<T>(_G.G) { }
1446 NodeMap(const EdgeSet &_G,const T &t) :
1447 NodeGraphType::NodeMap<T>(_G.G,t) { }
1449 NodeMap(const typename NodeGraphType::NodeMap<T> &m)
1450 : NodeGraphType::NodeMap<T>(m) { }
1452 ///\todo It can copy between different types.
1454 template<typename TT> friend class NodeMap;
1455 NodeMap(const typename NodeGraphType::NodeMap<TT> &m)
1456 : NodeGraphType::NodeMap<T>(m) { }
1459 template <typename T> class EdgeMap : public DynMapBase<Edge>
1461 std::vector<T> container;
1464 typedef T ValueType;
1465 typedef Edge KeyType;
1467 EdgeMap(const EdgeSet &_G) :
1468 DynMapBase<Edge>(_G), container(_G.maxEdgeId())
1470 //FIXME: What if there are empty Id's?
1471 //FIXME: Can I use 'this' in a constructor?
1472 G->dyn_edge_maps.push_back(this);
1474 EdgeMap(const EdgeSet &_G,const T &t) :
1475 DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
1477 G->dyn_edge_maps.push_back(this);
1479 EdgeMap(const EdgeMap<T> &m) :
1480 DynMapBase<Edge>(*m.G), container(m.container)
1482 G->dyn_node_maps.push_back(this);
1485 template<typename TT> friend class EdgeMap;
1487 ///\todo It can copy between different types.
1489 template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
1490 DynMapBase<Edge>(*m.G)
1492 G->dyn_node_maps.push_back(this);
1493 typename std::vector<TT>::const_iterator i;
1494 for(typename std::vector<TT>::const_iterator i=m.container.begin();
1495 i!=m.container.end();
1497 container.push_back(*i);
1502 typename std::vector<DynMapBase<Edge>* >::iterator i;
1503 for(i=G->dyn_edge_maps.begin();
1504 i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
1505 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
1506 //A better way to do that: (Is this really important?)
1508 *i=G->dyn_edge_maps.back();
1509 G->dyn_edge_maps.pop_back();
1514 void add(const Edge k)
1516 if(k.n>=int(container.size())) container.resize(k.n+1);
1518 void erase(const Edge) { }
1520 void set(Edge n, T a) { container[n.n]=a; }
1521 //T get(Edge n) const { return container[n.n]; }
1522 typename std::vector<T>::reference
1523 operator[](Edge n) { return container[n.n]; }
1524 typename std::vector<T>::const_reference
1525 operator[](Edge n) const { return container[n.n]; }
1527 ///\warning There is no safety check at all!
1528 ///Using operator = between maps attached to different graph may
1529 ///cause serious problem.
1530 ///\todo Is this really so?
1531 ///\todo It can copy between different types.
1532 const EdgeMap<T>& operator=(const EdgeMap<T> &m)
1534 container = m.container;
1537 template<typename TT>
1538 const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
1540 copy(m.container.begin(), m.container.end(), container.begin());
1544 void update() {} //Useless for DynMaps
1545 void update(T a) {} //Useless for DynMaps
1562 #endif //SMART_GRAPH_H