Docs are now divided into modules.
3 #ifndef HUGO_LIST_GRAPH_H
4 #define HUGO_LIST_GRAPH_H
8 ///\brief ListGraph, SymListGraph, NodeSet and EdgeSet classes.
17 /// \addtogroup graphs
22 ///A list graph class.
24 ///This is a simple and fast erasable graph implementation.
26 ///It conforms to the graph interface documented under
27 ///the description of \ref GraphSkeleton.
28 ///\sa \ref GraphSkeleton.
31 //Nodes are double linked.
32 //The free nodes are only single linked using the "next" field.
35 int first_in,first_out;
39 //Edges are double linked.
40 //The free edges are only single linked using the "next_in" field.
44 int prev_in, prev_out;
45 int next_in, next_out;
46 //FIXME: is this necessary?
47 // EdgeT() : next_in(-1), next_out(-1) prev_in(-1), prev_out(-1) {}
50 std::vector<NodeT> nodes;
55 std::vector<EdgeT> edges;
61 template <typename Key> class DynMapBase
66 virtual void add(const Key k) = NULL;
67 virtual void erase(const Key k) = NULL;
68 DynMapBase(const ListGraph &_G) : G(&_G) {}
69 virtual ~DynMapBase() {}
70 friend class ListGraph;
74 template <typename T> class EdgeMap;
75 template <typename T> class NodeMap;
83 ///\bug It must be public because of SymEdgeMap.
85 mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
86 ///\bug It must be public because of SymEdgeMap.
88 mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
97 template <typename T> class NodeMap;
98 template <typename T> class EdgeMap;
102 ListGraph() : nodes(), first_node(-1),
103 first_free_node(-1), edges(), first_free_edge(-1) {}
104 ListGraph(const ListGraph &_g) : nodes(_g.nodes), first_node(_g.first_node),
105 first_free_node(_g.first_free_node),
107 first_free_edge(_g.first_free_edge) {}
111 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
112 i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
113 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
114 i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
117 int nodeNum() const { return nodes.size(); } //FIXME: What is this?
118 int edgeNum() const { return edges.size(); } //FIXME: What is this?
120 ///\bug This function does something different than
121 ///its name would suggests...
122 int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
123 ///\bug This function does something different than
124 ///its name would suggests...
125 int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
127 Node tail(Edge e) const { return edges[e.n].tail; }
128 Node head(Edge e) const { return edges[e.n].head; }
130 Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
131 Node aNode(InEdgeIt e) const { return edges[e.n].head; }
133 Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
134 Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
136 NodeIt& first(NodeIt& v) const {
137 v=NodeIt(*this); return v; }
138 EdgeIt& first(EdgeIt& e) const {
139 e=EdgeIt(*this); return e; }
140 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
141 e=OutEdgeIt(*this,v); return e; }
142 InEdgeIt& first(InEdgeIt& e, const Node v) const {
143 e=InEdgeIt(*this,v); return e; }
145 // template< typename It >
146 // It first() const { It e; first(e); return e; }
148 // template< typename It >
149 // It first(Node v) const { It e; first(e,v); return e; }
151 bool valid(Edge e) const { return e.n!=-1; }
152 bool valid(Node n) const { return n.n!=-1; }
154 void setInvalid(Edge &e) { e.n=-1; }
155 void setInvalid(Node &n) { n.n=-1; }
157 template <typename It> It getNext(It it) const
158 { It tmp(it); return next(tmp); }
160 NodeIt& next(NodeIt& it) const {
161 it.n=nodes[it.n].next;
164 OutEdgeIt& next(OutEdgeIt& it) const
165 { it.n=edges[it.n].next_out; return it; }
166 InEdgeIt& next(InEdgeIt& it) const
167 { it.n=edges[it.n].next_in; return it; }
168 EdgeIt& next(EdgeIt& it) const {
169 if(edges[it.n].next_in!=-1) {
170 it.n=edges[it.n].next_in;
174 for(n=nodes[edges[it.n].head].next;
175 n!=-1 && nodes[n].first_in == -1;
177 it.n = (n==-1)?-1:nodes[n].first_in;
182 int id(Node v) const { return v.n; }
183 int id(Edge e) const { return e.n; }
185 /// Adds a new node to the graph.
187 /// \todo It adds the nodes in a reversed order.
188 /// (i.e. the lastly added node becomes the first.)
192 if(first_free_node==-1)
195 nodes.push_back(NodeT());
199 first_free_node = nodes[n].next;
202 nodes[n].next = first_node;
203 if(first_node != -1) nodes[first_node].prev = n;
207 nodes[n].first_in = nodes[n].first_out = -1;
211 //Update dynamic maps
212 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
213 i!=dyn_node_maps.end(); ++i) (**i).add(nn);
218 Edge addEdge(Node u, Node v) {
221 if(first_free_edge==-1)
224 edges.push_back(EdgeT());
228 first_free_edge = edges[n].next_in;
231 edges[n].tail = u.n; edges[n].head = v.n;
233 edges[n].next_out = nodes[u.n].first_out;
234 if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n;
235 edges[n].next_in = nodes[v.n].first_in;
236 if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n;
237 edges[n].prev_in = edges[n].prev_out = -1;
239 nodes[u.n].first_out = nodes[v.n].first_in = n;
243 //Update dynamic maps
244 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
245 i!=dyn_edge_maps.end(); ++i) (**i).add(e);
251 void eraseEdge(int n) {
253 if(edges[n].next_in!=-1)
254 edges[edges[n].next_in].prev_in = edges[n].prev_in;
255 if(edges[n].prev_in!=-1)
256 edges[edges[n].prev_in].next_in = edges[n].next_in;
257 else nodes[edges[n].head].first_in = edges[n].next_in;
259 if(edges[n].next_out!=-1)
260 edges[edges[n].next_out].prev_out = edges[n].prev_out;
261 if(edges[n].prev_out!=-1)
262 edges[edges[n].prev_out].next_out = edges[n].next_out;
263 else nodes[edges[n].tail].first_out = edges[n].next_out;
265 edges[n].next_in = first_free_edge;
266 first_free_edge = -1;
268 //Update dynamic maps
270 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
271 i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
276 void erase(Node nn) {
280 while((m=nodes[n].first_in)!=-1) eraseEdge(m);
281 while((m=nodes[n].first_out)!=-1) eraseEdge(m);
283 if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
284 if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
285 else first_node = nodes[n].next;
287 nodes[n].next = first_free_node;
290 //Update dynamic maps
291 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
292 i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
295 void erase(Edge e) { eraseEdge(e.n); }
297 ///\bug Dynamic maps must be updated!
300 nodes.clear();edges.clear();
301 first_node=first_free_node=first_free_edge=-1;
305 friend class ListGraph;
306 template <typename T> friend class NodeMap;
309 friend class OutEdgeIt;
310 friend class InEdgeIt;
311 friend class SymEdge;
315 friend int ListGraph::id(Node v) const;
319 Node (Invalid i) { n=-1; }
320 bool operator==(const Node i) const {return n==i.n;}
321 bool operator!=(const Node i) const {return n!=i.n;}
322 bool operator<(const Node i) const {return n<i.n;}
325 class NodeIt : public Node {
326 friend class ListGraph;
328 NodeIt() : Node() { }
329 NodeIt(Invalid i) : Node(i) { }
330 NodeIt(const ListGraph& G) : Node(G.first_node) { }
334 friend class ListGraph;
335 template <typename T> friend class EdgeMap;
337 //template <typename T> friend class SymListGraph::SymEdgeMap;
338 //friend Edge SymListGraph::opposite(Edge) const;
344 friend int ListGraph::id(Edge e) const;
349 Edge (Invalid) { n=-1; }
350 bool operator==(const Edge i) const {return n==i.n;}
351 bool operator!=(const Edge i) const {return n!=i.n;}
352 bool operator<(const Edge i) const {return n<i.n;}
353 ///\bug This is a workaround until somebody tells me how to
354 ///make class \c SymListGraph::SymEdgeMap friend of Edge
355 int &idref() {return n;}
356 const int &idref() const {return n;}
359 class EdgeIt : public Edge {
360 friend class ListGraph;
362 EdgeIt(const ListGraph& G) : Edge() {
365 m!=-1 && G.nodes[m].first_in == -1; m = G.nodes[m].next);
366 n = (m==-1)?-1:G.nodes[m].first_in;
368 EdgeIt (Invalid i) : Edge(i) { }
369 EdgeIt() : Edge() { }
370 ///\bug This is a workaround until somebody tells me how to
371 ///make class \c SymListGraph::SymEdgeMap friend of Edge
372 int &idref() {return n;}
375 class OutEdgeIt : public Edge {
376 friend class ListGraph;
378 OutEdgeIt() : Edge() { }
379 OutEdgeIt (Invalid i) : Edge(i) { }
381 OutEdgeIt(const ListGraph& G,const Node v)
382 : Edge(G.nodes[v.n].first_out) {}
385 class InEdgeIt : public Edge {
386 friend class ListGraph;
388 InEdgeIt() : Edge() { }
389 InEdgeIt (Invalid i) : Edge(i) { }
390 InEdgeIt(const ListGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
393 template <typename T> class NodeMap : public DynMapBase<Node>
395 std::vector<T> container;
399 typedef Node KeyType;
401 NodeMap(const ListGraph &_G) :
402 DynMapBase<Node>(_G), container(_G.maxNodeId())
404 G->dyn_node_maps.push_back(this);
406 NodeMap(const ListGraph &_G,const T &t) :
407 DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
409 G->dyn_node_maps.push_back(this);
412 NodeMap(const NodeMap<T> &m) :
413 DynMapBase<Node>(*m.G), container(m.container)
415 G->dyn_node_maps.push_back(this);
418 template<typename TT> friend class NodeMap;
420 ///\todo It can copy between different types.
422 template<typename TT> NodeMap(const NodeMap<TT> &m) :
423 DynMapBase<Node>(*m.G)
425 G->dyn_node_maps.push_back(this);
426 typename std::vector<TT>::const_iterator i;
427 for(typename std::vector<TT>::const_iterator i=m.container.begin();
428 i!=m.container.end();
430 container.push_back(*i);
435 std::vector<DynMapBase<Node>* >::iterator i;
436 for(i=G->dyn_node_maps.begin();
437 i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
438 //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
439 //A better way to do that: (Is this really important?)
441 *i=G->dyn_node_maps.back();
442 G->dyn_node_maps.pop_back();
447 void add(const Node k)
449 if(k.n>=int(container.size())) container.resize(k.n+1);
452 void erase(const Node) { }
454 void set(Node n, T a) { container[n.n]=a; }
455 //'T& operator[](Node n)' would be wrong here
456 typename std::vector<T>::reference
457 operator[](Node n) { return container[n.n]; }
458 //'const T& operator[](Node n)' would be wrong here
459 typename std::vector<T>::const_reference
460 operator[](Node n) const { return container[n.n]; }
462 ///\warning There is no safety check at all!
463 ///Using operator = between maps attached to different graph may
464 ///cause serious problem.
465 ///\todo Is this really so?
466 ///\todo It can copy between different types.
467 const NodeMap<T>& operator=(const NodeMap<T> &m)
469 container = m.container;
472 template<typename TT>
473 const NodeMap<T>& operator=(const NodeMap<TT> &m)
475 copy(m.container.begin(), m.container.end(), container.begin());
479 void update() {} //Useless for Dynamic Maps
480 void update(T a) {} //Useless for Dynamic Maps
483 template <typename T> class EdgeMap : public DynMapBase<Edge>
485 std::vector<T> container;
489 typedef Edge KeyType;
491 EdgeMap(const ListGraph &_G) :
492 DynMapBase<Edge>(_G), container(_G.maxEdgeId())
494 //FIXME: What if there are empty Id's?
495 //FIXME: Can I use 'this' in a constructor?
496 G->dyn_edge_maps.push_back(this);
498 EdgeMap(const ListGraph &_G,const T &t) :
499 DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
501 G->dyn_edge_maps.push_back(this);
503 EdgeMap(const EdgeMap<T> &m) :
504 DynMapBase<Edge>(*m.G), container(m.container)
506 G->dyn_node_maps.push_back(this);
509 template<typename TT> friend class EdgeMap;
511 ///\todo It can copy between different types.
513 template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
514 DynMapBase<Edge>(*m.G)
516 G->dyn_node_maps.push_back(this);
517 typename std::vector<TT>::const_iterator i;
518 for(typename std::vector<TT>::const_iterator i=m.container.begin();
519 i!=m.container.end();
521 container.push_back(*i);
526 std::vector<DynMapBase<Edge>* >::iterator i;
527 for(i=G->dyn_edge_maps.begin();
528 i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
529 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
530 //A better way to do that: (Is this really important?)
532 *i=G->dyn_edge_maps.back();
533 G->dyn_edge_maps.pop_back();
538 void add(const Edge k)
540 if(k.n>=int(container.size())) container.resize(k.n+1);
542 void erase(const Edge) { }
544 void set(Edge n, T a) { container[n.n]=a; }
545 //T get(Edge n) const { return container[n.n]; }
546 typename std::vector<T>::reference
547 operator[](Edge n) { return container[n.n]; }
548 typename std::vector<T>::const_reference
549 operator[](Edge n) const { return container[n.n]; }
551 ///\warning There is no safety check at all!
552 ///Using operator = between maps attached to different graph may
553 ///cause serious problem.
554 ///\todo Is this really so?
555 ///\todo It can copy between different types.
556 const EdgeMap<T>& operator=(const EdgeMap<T> &m)
558 container = m.container;
561 template<typename TT>
562 const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
564 copy(m.container.begin(), m.container.end(), container.begin());
568 void update() {} //Useless for DynMaps
569 void update(T a) {} //Useless for DynMaps
574 ///Graph for bidirectional edges.
576 ///The purpose of this graph structure is to handle graphs
577 ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
578 ///of oppositely directed edges.
579 ///There is a new edge map type called
580 ///\ref SymListGraph::SymEdgeMap "SymEdgeMap"
581 ///that complements this
583 ///storing shared values for the edge pairs. The usual
584 ///\ref GraphSkeleton::EdgeMap "EdgeMap"
588 ///The oppositely directed edge can also be obtained easily
589 ///using \ref opposite.
591 ///Here erase(Edge) deletes a pair of edges.
593 ///\todo this date structure need some reconsiderations. Maybe it
594 ///should be implemented independently from ListGraph.
596 class SymListGraph : public ListGraph
599 template<typename T> class SymEdgeMap;
600 template<typename T> friend class SymEdgeMap;
602 SymListGraph() : ListGraph() { }
603 SymListGraph(const ListGraph &_g) : ListGraph(_g) { }
604 ///Adds a pair of oppositely directed edges to the graph.
605 Edge addEdge(Node u, Node v)
607 Edge e = ListGraph::addEdge(u,v);
608 ListGraph::addEdge(v,u);
612 void erase(Node n) { ListGraph::erase(n); }
613 ///The oppositely directed edge.
615 ///Returns the oppositely directed
616 ///pair of the edge \c e.
617 Edge opposite(Edge e) const
620 f.idref() = e.idref() - 2*(e.idref()%2) + 1;
624 ///Removes a pair of oppositely directed edges to the graph.
626 ListGraph::erase(opposite(e));
630 ///Common data storage for the edge pairs.
632 ///This map makes it possible to store data shared by the oppositely
633 ///directed pairs of edges.
634 template <typename T> class SymEdgeMap : public DynMapBase<Edge>
636 std::vector<T> container;
640 typedef Edge KeyType;
642 SymEdgeMap(const SymListGraph &_G) :
643 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
645 static_cast<const SymListGraph*>(G)->dyn_edge_maps.push_back(this);
647 SymEdgeMap(const SymListGraph &_G,const T &t) :
648 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
650 G->dyn_edge_maps.push_back(this);
653 SymEdgeMap(const SymEdgeMap<T> &m) :
654 DynMapBase<SymEdge>(*m.G), container(m.container)
656 G->dyn_node_maps.push_back(this);
659 // template<typename TT> friend class SymEdgeMap;
661 ///\todo It can copy between different types.
664 template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :
665 DynMapBase<SymEdge>(*m.G)
667 G->dyn_node_maps.push_back(this);
668 typename std::vector<TT>::const_iterator i;
669 for(typename std::vector<TT>::const_iterator i=m.container.begin();
670 i!=m.container.end();
672 container.push_back(*i);
678 std::vector<DynMapBase<Edge>* >::iterator i;
679 for(i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.begin();
680 i!=static_cast<const SymListGraph*>(G)->dyn_edge_maps.end()
682 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
683 //A better way to do that: (Is this really important?)
685 *i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.back();
686 static_cast<const SymListGraph*>(G)->dyn_edge_maps.pop_back();
691 void add(const Edge k)
693 if(!k.idref()%2&&k.idref()/2>=int(container.size()))
694 container.resize(k.idref()/2+1);
696 void erase(const Edge k) { }
698 void set(Edge n, T a) { container[n.idref()/2]=a; }
699 //T get(Edge n) const { return container[n.idref()/2]; }
700 typename std::vector<T>::reference
701 operator[](Edge n) { return container[n.idref()/2]; }
702 typename std::vector<T>::const_reference
703 operator[](Edge n) const { return container[n.idref()/2]; }
705 ///\warning There is no safety check at all!
706 ///Using operator = between maps attached to different graph may
707 ///cause serious problem.
708 ///\todo Is this really so?
709 ///\todo It can copy between different types.
710 const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
712 container = m.container;
715 template<typename TT>
716 const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
718 copy(m.container.begin(), m.container.end(), container.begin());
722 void update() {} //Useless for DynMaps
723 void update(T a) {} //Useless for DynMaps
730 ///A graph class containing only nodes.
732 ///This class implements a graph structure without edges.
733 ///The most useful application of this class is to be the node set of an
734 ///\ref EdgeSet class.
736 ///It conforms to the graph interface documented under
737 ///the description of \ref GraphSkeleton with the exception that you cannot
738 ///add (or delete) edges. The usual edge iterators are exists, but they are
739 ///always \ref INVALID.
740 ///\sa \ref GraphSkeleton
744 //Nodes are double linked.
745 //The free nodes are only single linked using the "next" field.
748 int first_in,first_out;
753 std::vector<NodeT> nodes;
756 //The first free node
761 template <typename Key> class DynMapBase
766 virtual void add(const Key k) = NULL;
767 virtual void erase(const Key k) = NULL;
768 DynMapBase(const NodeSet &_G) : G(&_G) {}
769 virtual ~DynMapBase() {}
770 friend class NodeSet;
774 template <typename T> class EdgeMap;
775 template <typename T> class NodeMap;
783 ///\bug It must be public because of SymEdgeMap.
785 mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
786 //mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
795 template <typename T> class NodeMap;
796 template <typename T> class EdgeMap;
800 NodeSet() : nodes(), first_node(-1),
801 first_free_node(-1) {}
802 NodeSet(const NodeSet &_g) : nodes(_g.nodes), first_node(_g.first_node),
803 first_free_node(_g.first_free_node) {}
807 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
808 i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
809 //for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
810 // i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
813 int nodeNum() const { return nodes.size(); } //FIXME: What is this?
814 int edgeNum() const { return 0; } //FIXME: What is this?
816 ///\bug This function does something different than
817 ///its name would suggests...
818 int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
819 ///\bug This function does something different than
820 ///its name would suggests...
821 int maxEdgeId() const { return 0; } //FIXME: What is this?
823 Node tail(Edge e) const { return INVALID; }
824 Node head(Edge e) const { return INVALID; }
826 Node aNode(OutEdgeIt e) const { return INVALID; }
827 Node aNode(InEdgeIt e) const { return INVALID; }
829 Node bNode(OutEdgeIt e) const { return INVALID; }
830 Node bNode(InEdgeIt e) const { return INVALID; }
832 NodeIt& first(NodeIt& v) const {
833 v=NodeIt(*this); return v; }
834 EdgeIt& first(EdgeIt& e) const {
835 e=EdgeIt(*this); return e; }
836 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
837 e=OutEdgeIt(*this,v); return e; }
838 InEdgeIt& first(InEdgeIt& e, const Node v) const {
839 e=InEdgeIt(*this,v); return e; }
841 // template< typename It >
842 // It first() const { It e; first(e); return e; }
844 // template< typename It >
845 // It first(Node v) const { It e; first(e,v); return e; }
847 bool valid(Edge e) const { return false; }
848 bool valid(Node n) const { return n.n!=-1; }
850 void setInvalid(Edge &e) { }
851 void setInvalid(Node &n) { n.n=-1; }
853 template <typename It> It getNext(It it) const
854 { It tmp(it); return next(tmp); }
856 NodeIt& next(NodeIt& it) const {
857 it.n=nodes[it.n].next;
860 OutEdgeIt& next(OutEdgeIt& it) const { return it; }
861 InEdgeIt& next(InEdgeIt& it) const { return it; }
862 EdgeIt& next(EdgeIt& it) const { return it; }
864 int id(Node v) const { return v.n; }
865 int id(Edge e) const { return -1; }
867 /// Adds a new node to the graph.
869 /// \todo It adds the nodes in a reversed order.
870 /// (i.e. the lastly added node becomes the first.)
874 if(first_free_node==-1)
877 nodes.push_back(NodeT());
881 first_free_node = nodes[n].next;
884 nodes[n].next = first_node;
885 if(first_node != -1) nodes[first_node].prev = n;
889 nodes[n].first_in = nodes[n].first_out = -1;
893 //Update dynamic maps
894 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
895 i!=dyn_node_maps.end(); ++i) (**i).add(nn);
900 void erase(Node nn) {
903 if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
904 if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
905 else first_node = nodes[n].next;
907 nodes[n].next = first_free_node;
910 //Update dynamic maps
911 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
912 i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
915 ///\bug Dynamic maps must be updated!
919 first_node = first_free_node = -1;
923 friend class NodeSet;
924 template <typename T> friend class NodeMap;
927 friend class OutEdgeIt;
928 friend class InEdgeIt;
932 friend int NodeSet::id(Node v) const;
936 Node (Invalid i) { n=-1; }
937 bool operator==(const Node i) const {return n==i.n;}
938 bool operator!=(const Node i) const {return n!=i.n;}
939 bool operator<(const Node i) const {return n<i.n;}
942 class NodeIt : public Node {
943 friend class NodeSet;
945 NodeIt(const NodeSet& G) : Node(G.first_node) { }
946 NodeIt() : Node() { }
950 //friend class NodeSet;
951 //template <typename T> friend class EdgeMap;
953 //template <typename T> friend class SymNodeSet::SymEdgeMap;
954 //friend Edge SymNodeSet::opposite(Edge) const;
956 // friend class Node;
957 // friend class NodeIt;
959 //friend int NodeSet::id(Edge e) const;
964 bool operator==(const Edge i) const {return true;}
965 bool operator!=(const Edge i) const {return false;}
966 bool operator<(const Edge i) const {return false;}
967 ///\bug This is a workaround until somebody tells me how to
968 ///make class \c SymNodeSet::SymEdgeMap friend of Edge
969 // int idref() {return -1;}
970 // int idref() const {return -1;}
973 class EdgeIt : public Edge {
974 //friend class NodeSet;
976 EdgeIt(const NodeSet& G) : Edge() { }
977 EdgeIt (Invalid i) : Edge(i) { }
978 EdgeIt() : Edge() { }
979 ///\bug This is a workaround until somebody tells me how to
980 ///make class \c SymNodeSet::SymEdgeMap friend of Edge
981 // int idref() {return -1;}
984 class OutEdgeIt : public Edge {
985 friend class NodeSet;
987 OutEdgeIt() : Edge() { }
988 OutEdgeIt (Invalid i) : Edge(i) { }
989 OutEdgeIt(const NodeSet& G,const Node v) : Edge() {}
992 class InEdgeIt : public Edge {
993 friend class NodeSet;
995 InEdgeIt() : Edge() { }
996 InEdgeIt (Invalid i) : Edge(i) { }
997 InEdgeIt(const NodeSet& G,Node v) :Edge() {}
1000 template <typename T> class NodeMap : public DynMapBase<Node>
1002 std::vector<T> container;
1005 typedef T ValueType;
1006 typedef Node KeyType;
1008 NodeMap(const NodeSet &_G) :
1009 DynMapBase<Node>(_G), container(_G.maxNodeId())
1011 G->dyn_node_maps.push_back(this);
1013 NodeMap(const NodeSet &_G,const T &t) :
1014 DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
1016 G->dyn_node_maps.push_back(this);
1019 NodeMap(const NodeMap<T> &m) :
1020 DynMapBase<Node>(*m.G), container(m.container)
1022 G->dyn_node_maps.push_back(this);
1025 template<typename TT> friend class NodeMap;
1027 ///\todo It can copy between different types.
1029 template<typename TT> NodeMap(const NodeMap<TT> &m) :
1030 DynMapBase<Node>(*m.G)
1032 G->dyn_node_maps.push_back(this);
1033 typename std::vector<TT>::const_iterator i;
1034 for(typename std::vector<TT>::const_iterator i=m.container.begin();
1035 i!=m.container.end();
1037 container.push_back(*i);
1042 std::vector<DynMapBase<Node>* >::iterator i;
1043 for(i=G->dyn_node_maps.begin();
1044 i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
1045 //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
1046 //A better way to do that: (Is this really important?)
1048 *i=G->dyn_node_maps.back();
1049 G->dyn_node_maps.pop_back();
1054 void add(const Node k)
1056 if(k.n>=int(container.size())) container.resize(k.n+1);
1059 void erase(const Node) { }
1061 void set(Node n, T a) { container[n.n]=a; }
1062 //'T& operator[](Node n)' would be wrong here
1063 typename std::vector<T>::reference
1064 operator[](Node n) { return container[n.n]; }
1065 //'const T& operator[](Node n)' would be wrong here
1066 typename std::vector<T>::const_reference
1067 operator[](Node n) const { return container[n.n]; }
1069 ///\warning There is no safety check at all!
1070 ///Using operator = between maps attached to different graph may
1071 ///cause serious problem.
1072 ///\todo Is this really so?
1073 ///\todo It can copy between different types.
1074 const NodeMap<T>& operator=(const NodeMap<T> &m)
1076 container = m.container;
1079 template<typename TT>
1080 const NodeMap<T>& operator=(const NodeMap<TT> &m)
1082 copy(m.container.begin(), m.container.end(), container.begin());
1086 void update() {} //Useless for Dynamic Maps
1087 void update(T a) {} //Useless for Dynamic Maps
1090 template <typename T> class EdgeMap
1093 typedef T ValueType;
1094 typedef Edge KeyType;
1096 EdgeMap(const NodeSet &) { }
1097 EdgeMap(const NodeSet &,const T &) { }
1098 EdgeMap(const EdgeMap<T> &) { }
1099 // template<typename TT> friend class EdgeMap;
1101 ///\todo It can copy between different types.
1103 template<typename TT> EdgeMap(const EdgeMap<TT> &) { }
1106 void add(const Edge ) { }
1107 void erase(const Edge) { }
1109 void set(Edge, T) { }
1110 //T get(Edge n) const { return container[n.n]; }
1111 ValueType &operator[](Edge) { return *((T*)(NULL)); }
1112 const ValueType &operator[](Edge) const { return *((T*)(NULL)); }
1114 const EdgeMap<T>& operator=(const EdgeMap<T> &) { return *this; }
1116 template<typename TT>
1117 const EdgeMap<T>& operator=(const EdgeMap<TT> &m) { return *this; }
1126 ///Graph structure using a node set of another graph.
1128 ///This structure can be used to establish another graph over a node set
1129 /// of an existing one. The node iterator will go through the nodes of the
1130 /// original graph, and the NodeMap's of both graphs will convert to
1133 ///\warning Adding or deleting nodes from the graph is not safe if an
1134 ///\ref EdgeSet is currently attached to it!
1136 ///\todo Make it possible to add/delete edges from the base graph
1137 ///(and from \ref EdgeSet, as well)
1139 ///\param GG The type of the graph which shares its node set with this class.
1140 ///Its interface must conform with \ref GraphSkeleton.
1142 ///It conforms to the graph interface documented under
1143 ///the description of \ref GraphSkeleton.
1144 ///\sa \ref GraphSkeleton.
1145 ///\sa \ref NodeSet.
1146 template<typename GG>
1149 typedef GG NodeGraphType;
1155 //Edges are double linked.
1156 //The free edges are only single linked using the "next_in" field.
1159 int first_in,first_out;
1160 NodeT() : first_in(-1), first_out(-1) { }
1166 int prev_in, prev_out;
1167 int next_in, next_out;
1171 typename NodeGraphType::NodeMap<NodeT> nodes;
1173 std::vector<EdgeT> edges;
1174 //The first free edge
1175 int first_free_edge;
1179 template <typename Key> class DynMapBase
1184 virtual void add(const Key k) = NULL;
1185 virtual void erase(const Key k) = NULL;
1186 DynMapBase(const EdgeSet &_G) : G(&_G) {}
1187 virtual ~DynMapBase() {}
1188 friend class EdgeSet;
1192 //template <typename T> class NodeMap;
1193 template <typename T> class EdgeMap;
1201 // mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
1202 ///\bug It must be public because of SymEdgeMap.
1204 mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
1213 template <typename T> class NodeMap;
1214 template <typename T> class EdgeMap;
1218 EdgeSet(NodeGraphType &_G) : G(_G),
1220 first_free_edge(-1) { }
1221 EdgeSet(const EdgeSet &_g) : G(_g.G), nodes(_g.G), edges(_g.edges),
1222 first_free_edge(_g.first_free_edge) { }
1226 // for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
1227 // i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
1228 for(typename std::vector<DynMapBase<Edge> * >::iterator
1229 i=dyn_edge_maps.begin();
1230 i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
1233 int nodeNum() const { return G.nodeNum(); } //FIXME: What is this?
1234 int edgeNum() const { return edges.size(); } //FIXME: What is this?
1236 ///\bug This function does something different than
1237 ///its name would suggests...
1238 int maxNodeId() const { return G.maxNodeId(); } //FIXME: What is this?
1239 ///\bug This function does something different than
1240 ///its name would suggests...
1241 int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
1243 Node tail(Edge e) const { return edges[e.n].tail; }
1244 Node head(Edge e) const { return edges[e.n].head; }
1246 Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
1247 Node aNode(InEdgeIt e) const { return edges[e.n].head; }
1249 Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
1250 Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
1252 NodeIt& first(NodeIt& v) const {
1253 v=NodeIt(*this); return v; }
1254 EdgeIt& first(EdgeIt& e) const {
1255 e=EdgeIt(*this); return e; }
1256 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
1257 e=OutEdgeIt(*this,v); return e; }
1258 InEdgeIt& first(InEdgeIt& e, const Node v) const {
1259 e=InEdgeIt(*this,v); return e; }
1261 // template< typename It >
1262 // It first() const { It e; first(e); return e; }
1264 // template< typename It >
1265 // It first(Node v) const { It e; first(e,v); return e; }
1267 bool valid(Edge e) const { return e.n!=-1; }
1268 bool valid(Node n) const { return G.valid(n); }
1270 void setInvalid(Edge &e) { e.n=-1; }
1271 void setInvalid(Node &n) { G.setInvalid(n); }
1273 template <typename It> It getNext(It it) const
1274 { It tmp(it); return next(tmp); }
1276 NodeIt& next(NodeIt& it) const { G.next(it); return it; }
1277 OutEdgeIt& next(OutEdgeIt& it) const
1278 { it.n=edges[it.n].next_out; return it; }
1279 InEdgeIt& next(InEdgeIt& it) const
1280 { it.n=edges[it.n].next_in; return it; }
1281 EdgeIt& next(EdgeIt& it) const {
1282 if(edges[it.n].next_in!=-1) {
1283 it.n=edges[it.n].next_in;
1286 typename NodeGraphType::Node n;
1287 for(n=G.next(edges[it.n].head);
1288 G.valid(n) && nodes[n].first_in == -1;
1290 it.n = (G.valid(n))?-1:nodes[n].first_in;
1295 int id(Node v) const { return G.id(v); }
1296 int id(Edge e) const { return e.n; }
1298 /// Adds a new node to the graph.
1299 Node addNode() { return G.AddNode(); }
1301 Edge addEdge(Node u, Node v) {
1304 if(first_free_edge==-1)
1307 edges.push_back(EdgeT());
1310 n = first_free_edge;
1311 first_free_edge = edges[n].next_in;
1314 edges[n].tail = u; edges[n].head = v;
1316 edges[n].next_out = nodes[u].first_out;
1317 if(nodes[u].first_out != -1) edges[nodes[u].first_out].prev_out = n;
1318 edges[n].next_in = nodes[v].first_in;
1319 if(nodes[v].first_in != -1) edges[nodes[v].first_in].prev_in = n;
1320 edges[n].prev_in = edges[n].prev_out = -1;
1322 nodes[u].first_out = nodes[v].first_in = n;
1326 //Update dynamic maps
1327 for(typename std::vector<DynMapBase<Edge> * >::iterator
1328 i=dyn_edge_maps.begin();
1329 i!=dyn_edge_maps.end(); ++i) (**i).add(e);
1335 void eraseEdge(int n) {
1337 if(edges[n].next_in!=-1)
1338 edges[edges[n].next_in].prev_in = edges[n].prev_in;
1339 if(edges[n].prev_in!=-1)
1340 edges[edges[n].prev_in].next_in = edges[n].next_in;
1341 else nodes[edges[n].head].first_in = edges[n].next_in;
1343 if(edges[n].next_out!=-1)
1344 edges[edges[n].next_out].prev_out = edges[n].prev_out;
1345 if(edges[n].prev_out!=-1)
1346 edges[edges[n].prev_out].next_out = edges[n].next_out;
1347 else nodes[edges[n].tail].first_out = edges[n].next_out;
1349 edges[n].next_in = first_free_edge;
1350 first_free_edge = -1;
1352 //Update dynamic maps
1354 for(typename std::vector<DynMapBase<Edge> * >::iterator
1355 i=dyn_edge_maps.begin();
1356 i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
1361 // void erase(Node nn) {
1364 // while((m=nodes[n].first_in)!=-1) eraseEdge(m);
1365 // while((m=nodes[n].first_out)!=-1) eraseEdge(m);
1368 void erase(Edge e) { eraseEdge(e.n); }
1370 // //\bug Dynamic maps must be updated!
1373 // nodes.clear();edges.clear();
1374 // first_node=first_free_node=first_free_edge=-1;
1377 class Node : public NodeGraphType::Node {
1378 friend class EdgeSet;
1379 // template <typename T> friend class NodeMap;
1382 friend class OutEdgeIt;
1383 friend class InEdgeIt;
1384 friend class SymEdge;
1387 friend int EdgeSet::id(Node v) const;
1388 // Node(int nn) {n=nn;}
1390 Node() : NodeGraphType::Node() {}
1391 Node (Invalid i) : NodeGraphType::Node(i) {}
1392 Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {}
1395 class NodeIt : public NodeGraphType::NodeIt {
1396 friend class EdgeSet;
1398 NodeIt() : NodeGraphType::NodeIt() { }
1399 NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {}
1400 NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { }
1401 NodeIt(const typename NodeGraphType::NodeIt &n)
1402 : NodeGraphType::NodeIt(n) {}
1403 operator Node() { return Node(*this);}
1407 friend class EdgeSet;
1408 template <typename T> friend class EdgeMap;
1410 //template <typename T> friend class SymEdgeSet::SymEdgeMap;
1411 //friend Edge SymEdgeSet::opposite(Edge) const;
1414 friend class NodeIt;
1417 friend int EdgeSet::id(Edge e) const;
1419 Edge(int nn) {n=nn;}
1422 Edge (Invalid) { n=-1; }
1423 bool operator==(const Edge i) const {return n==i.n;}
1424 bool operator!=(const Edge i) const {return n!=i.n;}
1425 bool operator<(const Edge i) const {return n<i.n;}
1426 ///\bug This is a workaround until somebody tells me how to
1427 ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
1428 int &idref() {return n;}
1429 const int &idref() const {return n;}
1432 class EdgeIt : public Edge {
1433 friend class EdgeSet;
1435 EdgeIt(const EdgeSet& G) : Edge() {
1436 typename NodeGraphType::Node m;
1438 G.valid(m) && nodes[m].first_in == -1; G.next[m]);
1439 n = G.valid(m)?-1:nodes[m].first_in;
1441 EdgeIt (Invalid i) : Edge(i) { }
1442 EdgeIt() : Edge() { }
1443 ///\bug This is a workaround until somebody tells me how to
1444 ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
1445 int &idref() {return n;}
1448 class OutEdgeIt : public Edge {
1449 friend class EdgeSet;
1451 OutEdgeIt() : Edge() { }
1452 OutEdgeIt (Invalid i) : Edge(i) { }
1454 OutEdgeIt(const EdgeSet& G,const Node v) : Edge(nodes[v].first_out) { }
1457 class InEdgeIt : public Edge {
1458 friend class EdgeSet;
1460 InEdgeIt() : Edge() { }
1461 InEdgeIt (Invalid i) : Edge(i) { }
1462 InEdgeIt(const EdgeSet& G,Node v) :Edge(nodes[v].first_in) { }
1465 template <typename T> class NodeMap : public NodeGraphType::NodeMap<T>
1468 NodeMap(const EdgeSet &_G) :
1469 NodeGraphType::NodeMap<T>(_G.G) { }
1470 NodeMap(const EdgeSet &_G,const T &t) :
1471 NodeGraphType::NodeMap<T>(_G.G,t) { }
1473 NodeMap(const typename NodeGraphType::NodeMap<T> &m)
1474 : NodeGraphType::NodeMap<T>(m) { }
1476 ///\todo It can copy between different types.
1478 template<typename TT>
1479 NodeMap(const typename NodeGraphType::NodeMap<TT> &m)
1480 : NodeGraphType::NodeMap<T>(m) { }
1483 template <typename T> class EdgeMap : public DynMapBase<Edge>
1485 std::vector<T> container;
1488 typedef T ValueType;
1489 typedef Edge KeyType;
1491 EdgeMap(const EdgeSet &_G) :
1492 DynMapBase<Edge>(_G), container(_G.maxEdgeId())
1494 //FIXME: What if there are empty Id's?
1495 //FIXME: Can I use 'this' in a constructor?
1496 G->dyn_edge_maps.push_back(this);
1498 EdgeMap(const EdgeSet &_G,const T &t) :
1499 DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
1501 G->dyn_edge_maps.push_back(this);
1503 EdgeMap(const EdgeMap<T> &m) :
1504 DynMapBase<Edge>(*m.G), container(m.container)
1506 G->dyn_node_maps.push_back(this);
1509 template<typename TT> friend class EdgeMap;
1511 ///\todo It can copy between different types.
1513 template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
1514 DynMapBase<Edge>(*m.G)
1516 G->dyn_node_maps.push_back(this);
1517 typename std::vector<TT>::const_iterator i;
1518 for(typename std::vector<TT>::const_iterator i=m.container.begin();
1519 i!=m.container.end();
1521 container.push_back(*i);
1526 typename std::vector<DynMapBase<Edge>* >::iterator i;
1527 for(i=G->dyn_edge_maps.begin();
1528 i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
1529 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
1530 //A better way to do that: (Is this really important?)
1532 *i=G->dyn_edge_maps.back();
1533 G->dyn_edge_maps.pop_back();
1538 void add(const Edge k)
1540 if(k.n>=int(container.size())) container.resize(k.n+1);
1542 void erase(const Edge) { }
1544 void set(Edge n, T a) { container[n.n]=a; }
1545 //T get(Edge n) const { return container[n.n]; }
1546 typename std::vector<T>::reference
1547 operator[](Edge n) { return container[n.n]; }
1548 typename std::vector<T>::const_reference
1549 operator[](Edge n) const { return container[n.n]; }
1551 ///\warning There is no safety check at all!
1552 ///Using operator = between maps attached to different graph may
1553 ///cause serious problem.
1554 ///\todo Is this really so?
1555 ///\todo It can copy between different types.
1556 const EdgeMap<T>& operator=(const EdgeMap<T> &m)
1558 container = m.container;
1561 template<typename TT>
1562 const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
1564 copy(m.container.begin(), m.container.end(), container.begin());
1568 void update() {} //Useless for DynMaps
1569 void update(T a) {} //Useless for DynMaps
1578 #endif //HUGO_LIST_GRAPH_H