3 #ifndef HUGO_LIST_GRAPH_H
4 #define HUGO_LIST_GRAPH_H
8 ///\brief ListGraph, SymListGraph, NodeSet and EdgeSet classes.
13 #include <hugo/invalid.h>
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) = 0;
67 virtual void erase(const Key k) = 0;
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;
99 ListGraph() : nodes(), first_node(-1),
100 first_free_node(-1), edges(), first_free_edge(-1) {}
101 ListGraph(const ListGraph &_g) : nodes(_g.nodes), first_node(_g.first_node),
102 first_free_node(_g.first_free_node),
104 first_free_edge(_g.first_free_edge) {}
108 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
109 i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
110 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
111 i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
114 int nodeNum() const { return nodes.size(); } //FIXME: What is this?
115 int edgeNum() const { return edges.size(); } //FIXME: What is this?
117 ///\bug This function does something different than
118 ///its name would suggests...
119 int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
120 ///\bug This function does something different than
121 ///its name would suggests...
122 int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
124 Node tail(Edge e) const { return edges[e.n].tail; }
125 Node head(Edge e) const { return edges[e.n].head; }
127 Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
128 Node aNode(InEdgeIt e) const { return edges[e.n].head; }
130 Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
131 Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
133 NodeIt& first(NodeIt& v) const {
134 v=NodeIt(*this); return v; }
135 EdgeIt& first(EdgeIt& e) const {
136 e=EdgeIt(*this); return e; }
137 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
138 e=OutEdgeIt(*this,v); return e; }
139 InEdgeIt& first(InEdgeIt& e, const Node v) const {
140 e=InEdgeIt(*this,v); return e; }
142 // template< typename It >
143 // It first() const { It e; first(e); return e; }
145 // template< typename It >
146 // It first(Node v) const { It e; first(e,v); return e; }
148 bool valid(Edge e) const { return e.n!=-1; }
149 bool valid(Node n) const { return n.n!=-1; }
151 void setInvalid(Edge &e) { e.n=-1; }
152 void setInvalid(Node &n) { n.n=-1; }
154 template <typename It> It getNext(It it) const
155 { It tmp(it); return next(tmp); }
157 NodeIt& next(NodeIt& it) const {
158 it.n=nodes[it.n].next;
161 OutEdgeIt& next(OutEdgeIt& it) const
162 { it.n=edges[it.n].next_out; return it; }
163 InEdgeIt& next(InEdgeIt& it) const
164 { it.n=edges[it.n].next_in; return it; }
165 EdgeIt& next(EdgeIt& it) const {
166 if(edges[it.n].next_in!=-1) {
167 it.n=edges[it.n].next_in;
171 for(n=nodes[edges[it.n].head].next;
172 n!=-1 && nodes[n].first_in == -1;
174 it.n = (n==-1)?-1:nodes[n].first_in;
179 int id(Node v) const { return v.n; }
180 int id(Edge e) const { return e.n; }
182 /// Adds a new node to the graph.
184 /// \todo It adds the nodes in a reversed order.
185 /// (i.e. the lastly added node becomes the first.)
189 if(first_free_node==-1)
192 nodes.push_back(NodeT());
196 first_free_node = nodes[n].next;
199 nodes[n].next = first_node;
200 if(first_node != -1) nodes[first_node].prev = n;
204 nodes[n].first_in = nodes[n].first_out = -1;
208 //Update dynamic maps
209 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
210 i!=dyn_node_maps.end(); ++i) (**i).add(nn);
215 Edge addEdge(Node u, Node v) {
218 if(first_free_edge==-1)
221 edges.push_back(EdgeT());
225 first_free_edge = edges[n].next_in;
228 edges[n].tail = u.n; edges[n].head = v.n;
230 edges[n].next_out = nodes[u.n].first_out;
231 if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n;
232 edges[n].next_in = nodes[v.n].first_in;
233 if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n;
234 edges[n].prev_in = edges[n].prev_out = -1;
236 nodes[u.n].first_out = nodes[v.n].first_in = n;
240 //Update dynamic maps
241 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
242 i!=dyn_edge_maps.end(); ++i) (**i).add(e);
248 void eraseEdge(int n) {
250 if(edges[n].next_in!=-1)
251 edges[edges[n].next_in].prev_in = edges[n].prev_in;
252 if(edges[n].prev_in!=-1)
253 edges[edges[n].prev_in].next_in = edges[n].next_in;
254 else nodes[edges[n].head].first_in = edges[n].next_in;
256 if(edges[n].next_out!=-1)
257 edges[edges[n].next_out].prev_out = edges[n].prev_out;
258 if(edges[n].prev_out!=-1)
259 edges[edges[n].prev_out].next_out = edges[n].next_out;
260 else nodes[edges[n].tail].first_out = edges[n].next_out;
262 edges[n].next_in = first_free_edge;
263 first_free_edge = -1;
265 //Update dynamic maps
267 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
268 i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
273 void erase(Node nn) {
277 while((m=nodes[n].first_in)!=-1) eraseEdge(m);
278 while((m=nodes[n].first_out)!=-1) eraseEdge(m);
280 if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
281 if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
282 else first_node = nodes[n].next;
284 nodes[n].next = first_free_node;
287 //Update dynamic maps
288 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
289 i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
292 void erase(Edge e) { eraseEdge(e.n); }
294 ///\bug Dynamic maps must be updated!
297 nodes.clear();edges.clear();
298 first_node=first_free_node=first_free_edge=-1;
302 friend class ListGraph;
303 template <typename T> friend class NodeMap;
306 friend class OutEdgeIt;
307 friend class InEdgeIt;
308 friend class SymEdge;
312 friend int ListGraph::id(Node v) const;
316 Node (Invalid) { n=-1; }
317 bool operator==(const Node i) const {return n==i.n;}
318 bool operator!=(const Node i) const {return n!=i.n;}
319 bool operator<(const Node i) const {return n<i.n;}
322 class NodeIt : public Node {
323 friend class ListGraph;
325 NodeIt() : Node() { }
326 NodeIt(Invalid i) : Node(i) { }
327 NodeIt(const ListGraph& G) : Node(G.first_node) { }
328 ///\todo Undocumented conversion Node -\> NodeIt.
329 NodeIt(const ListGraph& G, const Node &n) : Node(n) { }
333 friend class ListGraph;
334 template <typename T> friend class EdgeMap;
336 //template <typename T> friend class SymListGraph::SymEdgeMap;
337 //friend Edge SymListGraph::opposite(Edge) const;
343 friend int ListGraph::id(Edge e) const;
348 Edge (Invalid) { n=-1; }
349 bool operator==(const Edge i) const {return n==i.n;}
350 bool operator!=(const Edge i) const {return n!=i.n;}
351 bool operator<(const Edge i) const {return n<i.n;}
352 ///\bug This is a workaround until somebody tells me how to
353 ///make class \c SymListGraph::SymEdgeMap friend of Edge
354 int &idref() {return n;}
355 const int &idref() const {return n;}
358 class EdgeIt : public Edge {
359 friend class ListGraph;
361 EdgeIt(const ListGraph& G) : Edge() {
364 m!=-1 && G.nodes[m].first_in == -1; m = G.nodes[m].next);
365 n = (m==-1)?-1:G.nodes[m].first_in;
367 EdgeIt (Invalid i) : Edge(i) { }
368 EdgeIt() : Edge() { }
369 ///\bug This is a workaround until somebody tells me how to
370 ///make class \c SymListGraph::SymEdgeMap friend of Edge
371 int &idref() {return n;}
374 class OutEdgeIt : public Edge {
375 friend class ListGraph;
377 OutEdgeIt() : Edge() { }
378 OutEdgeIt (Invalid i) : Edge(i) { }
380 OutEdgeIt(const ListGraph& G,const Node v)
381 : Edge(G.nodes[v.n].first_out) {}
384 class InEdgeIt : public Edge {
385 friend class ListGraph;
387 InEdgeIt() : Edge() { }
388 InEdgeIt (Invalid i) : Edge(i) { }
389 InEdgeIt(const ListGraph& G,Node v) :Edge(G.nodes[v.n].first_in) {}
392 template <typename T> class NodeMap : public DynMapBase<Node>
394 std::vector<T> container;
398 typedef Node KeyType;
400 NodeMap(const ListGraph &_G) :
401 DynMapBase<Node>(_G), container(_G.maxNodeId())
403 G->dyn_node_maps.push_back(this);
405 NodeMap(const ListGraph &_G,const T &t) :
406 DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
408 G->dyn_node_maps.push_back(this);
411 NodeMap(const NodeMap<T> &m) :
412 DynMapBase<Node>(*m.G), container(m.container)
414 G->dyn_node_maps.push_back(this);
417 template<typename TT> friend class NodeMap;
419 ///\todo It can copy between different types.
421 template<typename TT> NodeMap(const NodeMap<TT> &m) :
422 DynMapBase<Node>(*m.G), container(m.container.size())
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 std::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>
486 std::vector<T> container;
490 typedef Edge KeyType;
492 EdgeMap(const ListGraph &_G) :
493 DynMapBase<Edge>(_G), container(_G.maxEdgeId())
495 //FIXME: What if there are empty Id's?
496 //FIXME: Can I use 'this' in a constructor?
497 G->dyn_edge_maps.push_back(this);
499 EdgeMap(const ListGraph &_G,const T &t) :
500 DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
502 G->dyn_edge_maps.push_back(this);
504 EdgeMap(const EdgeMap<T> &m) :
505 DynMapBase<Edge>(*m.G), container(m.container)
507 G->dyn_edge_maps.push_back(this);
510 template<typename TT> friend class EdgeMap;
512 ///\todo It can copy between different types.
514 template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
515 DynMapBase<Edge>(*m.G), container(m.container.size())
517 G->dyn_edge_maps.push_back(this);
518 typename std::vector<TT>::const_iterator i;
519 for(typename std::vector<TT>::const_iterator i=m.container.begin();
520 i!=m.container.end();
522 container.push_back(*i);
527 std::vector<DynMapBase<Edge>* >::iterator i;
528 for(i=G->dyn_edge_maps.begin();
529 i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
530 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
531 //A better way to do that: (Is this really important?)
533 *i=G->dyn_edge_maps.back();
534 G->dyn_edge_maps.pop_back();
539 void add(const Edge k)
541 if(k.n>=int(container.size())) container.resize(k.n+1);
543 void erase(const Edge) { }
545 void set(Edge n, T a) { container[n.n]=a; }
546 //T get(Edge n) const { return container[n.n]; }
547 typename std::vector<T>::reference
548 operator[](Edge n) { return container[n.n]; }
549 typename std::vector<T>::const_reference
550 operator[](Edge n) const { return container[n.n]; }
552 ///\warning There is no safety check at all!
553 ///Using operator = between maps attached to different graph may
554 ///cause serious problem.
555 ///\todo Is this really so?
556 ///\todo It can copy between different types.
557 const EdgeMap<T>& operator=(const EdgeMap<T> &m)
559 container = m.container;
562 template<typename TT>
563 const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
565 std::copy(m.container.begin(), m.container.end(), container.begin());
569 void update() {} //Useless for DynMaps
570 void update(T a) {} //Useless for DynMaps
575 ///Graph for bidirectional edges.
577 ///The purpose of this graph structure is to handle graphs
578 ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
579 ///of oppositely directed edges.
580 ///There is a new edge map type called
581 ///\ref SymListGraph::SymEdgeMap "SymEdgeMap"
582 ///that complements this
584 ///storing shared values for the edge pairs. The usual
585 ///\ref GraphSkeleton::EdgeMap "EdgeMap"
589 ///The oppositely directed edge can also be obtained easily
590 ///using \ref opposite.
592 ///Here erase(Edge) deletes a pair of edges.
594 ///\todo this date structure need some reconsiderations. Maybe it
595 ///should be implemented independently from ListGraph.
597 class SymListGraph : public ListGraph
600 template<typename T> class SymEdgeMap;
601 template<typename T> friend class SymEdgeMap;
603 SymListGraph() : ListGraph() { }
604 SymListGraph(const ListGraph &_g) : ListGraph(_g) { }
605 ///Adds a pair of oppositely directed edges to the graph.
606 Edge addEdge(Node u, Node v)
608 Edge e = ListGraph::addEdge(u,v);
609 ListGraph::addEdge(v,u);
613 void erase(Node n) { ListGraph::erase(n); }
614 ///The oppositely directed edge.
616 ///Returns the oppositely directed
617 ///pair of the edge \c e.
618 Edge opposite(Edge e) const
621 f.idref() = e.idref() - 2*(e.idref()%2) + 1;
625 ///Removes a pair of oppositely directed edges to the graph.
627 ListGraph::erase(opposite(e));
631 ///Common data storage for the edge pairs.
633 ///This map makes it possible to store data shared by the oppositely
634 ///directed pairs of edges.
635 template <typename T> class SymEdgeMap : public DynMapBase<Edge>
637 std::vector<T> container;
641 typedef Edge KeyType;
643 SymEdgeMap(const SymListGraph &_G) :
644 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
646 static_cast<const SymListGraph*>(G)->dyn_edge_maps.push_back(this);
648 SymEdgeMap(const SymListGraph &_G,const T &t) :
649 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
651 G->dyn_edge_maps.push_back(this);
654 SymEdgeMap(const SymEdgeMap<T> &m) :
655 DynMapBase<SymEdge>(*m.G), container(m.container)
657 G->dyn_node_maps.push_back(this);
660 // template<typename TT> friend class SymEdgeMap;
662 ///\todo It can copy between different types.
665 template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :
666 DynMapBase<SymEdge>(*m.G), container(m.container.size())
668 G->dyn_node_maps.push_back(this);
669 typename std::vector<TT>::const_iterator i;
670 for(typename std::vector<TT>::const_iterator i=m.container.begin();
671 i!=m.container.end();
673 container.push_back(*i);
679 std::vector<DynMapBase<Edge>* >::iterator i;
680 for(i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.begin();
681 i!=static_cast<const SymListGraph*>(G)->dyn_edge_maps.end()
683 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
684 //A better way to do that: (Is this really important?)
686 *i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.back();
687 static_cast<const SymListGraph*>(G)->dyn_edge_maps.pop_back();
692 void add(const Edge k)
694 if(!k.idref()%2&&k.idref()/2>=int(container.size()))
695 container.resize(k.idref()/2+1);
697 void erase(const Edge k) { }
699 void set(Edge n, T a) { container[n.idref()/2]=a; }
700 //T get(Edge n) const { return container[n.idref()/2]; }
701 typename std::vector<T>::reference
702 operator[](Edge n) { return container[n.idref()/2]; }
703 typename std::vector<T>::const_reference
704 operator[](Edge n) const { return container[n.idref()/2]; }
706 ///\warning There is no safety check at all!
707 ///Using operator = between maps attached to different graph may
708 ///cause serious problem.
709 ///\todo Is this really so?
710 ///\todo It can copy between different types.
711 const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
713 container = m.container;
716 template<typename TT>
717 const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
719 std::copy(m.container.begin(), m.container.end(), container.begin());
723 void update() {} //Useless for DynMaps
724 void update(T a) {} //Useless for DynMaps
731 ///A graph class containing only nodes.
733 ///This class implements a graph structure without edges.
734 ///The most useful application of this class is to be the node set of an
735 ///\ref EdgeSet class.
737 ///It conforms to the graph interface documented under
738 ///the description of \ref GraphSkeleton with the exception that you cannot
739 ///add (or delete) edges. The usual edge iterators are exists, but they are
740 ///always \ref INVALID.
741 ///\sa \ref GraphSkeleton
745 //Nodes are double linked.
746 //The free nodes are only single linked using the "next" field.
749 int first_in,first_out;
754 std::vector<NodeT> nodes;
757 //The first free node
762 template <typename Key> class DynMapBase
767 virtual void add(const Key k) = 0;
768 virtual void erase(const Key k) = 0;
769 DynMapBase(const NodeSet &_G) : G(&_G) {}
770 virtual ~DynMapBase() {}
771 friend class NodeSet;
775 template <typename T> class EdgeMap;
776 template <typename T> class NodeMap;
784 ///\bug It must be public because of SymEdgeMap.
786 mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
787 //mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
796 template <typename T> class NodeMap;
797 template <typename T> class EdgeMap;
801 ///Default constructor
802 NodeSet() : nodes(), first_node(-1),
803 first_free_node(-1) {}
805 NodeSet(const NodeSet &_g) : nodes(_g.nodes), first_node(_g.first_node),
806 first_free_node(_g.first_free_node) {}
810 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
811 i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
812 //for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
813 // i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
816 int nodeNum() const { return nodes.size(); } //FIXME: What is this?
817 int edgeNum() const { return 0; } //FIXME: What is this?
819 ///\bug This function does something different than
820 ///its name would suggests...
821 int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
822 ///\bug This function does something different than
823 ///its name would suggests...
824 int maxEdgeId() const { return 0; } //FIXME: What is this?
826 Node tail(Edge e) const { return INVALID; }
827 Node head(Edge e) const { return INVALID; }
829 Node aNode(OutEdgeIt e) const { return INVALID; }
830 Node aNode(InEdgeIt e) const { return INVALID; }
832 Node bNode(OutEdgeIt e) const { return INVALID; }
833 Node bNode(InEdgeIt e) const { return INVALID; }
835 NodeIt& first(NodeIt& v) const {
836 v=NodeIt(*this); return v; }
837 EdgeIt& first(EdgeIt& e) const {
838 e=EdgeIt(*this); return e; }
839 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
840 e=OutEdgeIt(*this,v); return e; }
841 InEdgeIt& first(InEdgeIt& e, const Node v) const {
842 e=InEdgeIt(*this,v); return e; }
844 // template< typename It >
845 // It first() const { It e; first(e); return e; }
847 // template< typename It >
848 // It first(Node v) const { It e; first(e,v); return e; }
850 bool valid(Edge e) const { return false; }
851 bool valid(Node n) const { return n.n!=-1; }
853 void setInvalid(Edge &e) { }
854 void setInvalid(Node &n) { n.n=-1; }
856 template <typename It> It getNext(It it) const
857 { It tmp(it); return next(tmp); }
859 NodeIt& next(NodeIt& it) const {
860 it.n=nodes[it.n].next;
863 OutEdgeIt& next(OutEdgeIt& it) const { return it; }
864 InEdgeIt& next(InEdgeIt& it) const { return it; }
865 EdgeIt& next(EdgeIt& it) const { return it; }
867 int id(Node v) const { return v.n; }
868 int id(Edge e) const { return -1; }
870 /// Adds a new node to the graph.
872 /// \todo It adds the nodes in a reversed order.
873 /// (i.e. the lastly added node becomes the first.)
877 if(first_free_node==-1)
880 nodes.push_back(NodeT());
884 first_free_node = nodes[n].next;
887 nodes[n].next = first_node;
888 if(first_node != -1) nodes[first_node].prev = n;
892 nodes[n].first_in = nodes[n].first_out = -1;
896 //Update dynamic maps
897 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
898 i!=dyn_node_maps.end(); ++i) (**i).add(nn);
903 void erase(Node nn) {
906 if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
907 if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
908 else first_node = nodes[n].next;
910 nodes[n].next = first_free_node;
913 //Update dynamic maps
914 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
915 i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
918 ///\bug Dynamic maps must be updated!
922 first_node = first_free_node = -1;
926 friend class NodeSet;
927 template <typename T> friend class NodeMap;
930 friend class OutEdgeIt;
931 friend class InEdgeIt;
935 friend int NodeSet::id(Node v) const;
939 Node (Invalid i) { n=-1; }
940 bool operator==(const Node i) const {return n==i.n;}
941 bool operator!=(const Node i) const {return n!=i.n;}
942 bool operator<(const Node i) const {return n<i.n;}
945 class NodeIt : public Node {
946 friend class NodeSet;
948 NodeIt() : Node() { }
949 NodeIt(Invalid i) : Node(i) { }
950 NodeIt(const NodeSet& G) : Node(G.first_node) { }
951 ///\todo Undocumented conversion Node -\> NodeIt.
952 NodeIt(const NodeSet& G, const Node &n) : Node(n) { }
957 //friend class NodeSet;
958 //template <typename T> friend class EdgeMap;
960 //template <typename T> friend class SymNodeSet::SymEdgeMap;
961 //friend Edge SymNodeSet::opposite(Edge) const;
963 // friend class Node;
964 // friend class NodeIt;
966 //friend int NodeSet::id(Edge e) const;
971 bool operator==(const Edge i) const {return true;}
972 bool operator!=(const Edge i) const {return false;}
973 bool operator<(const Edge i) const {return false;}
974 ///\bug This is a workaround until somebody tells me how to
975 ///make class \c SymNodeSet::SymEdgeMap friend of Edge
976 // int idref() {return -1;}
977 // int idref() const {return -1;}
980 class EdgeIt : public Edge {
981 //friend class NodeSet;
983 EdgeIt(const NodeSet& G) : Edge() { }
984 EdgeIt (Invalid i) : Edge(i) { }
985 EdgeIt() : Edge() { }
986 ///\bug This is a workaround until somebody tells me how to
987 ///make class \c SymNodeSet::SymEdgeMap friend of Edge
988 // int idref() {return -1;}
991 class OutEdgeIt : public Edge {
992 friend class NodeSet;
994 OutEdgeIt() : Edge() { }
995 OutEdgeIt (Invalid i) : Edge(i) { }
996 OutEdgeIt(const NodeSet& G,const Node v) : Edge() {}
999 class InEdgeIt : public Edge {
1000 friend class NodeSet;
1002 InEdgeIt() : Edge() { }
1003 InEdgeIt (Invalid i) : Edge(i) { }
1004 InEdgeIt(const NodeSet& G,Node v) :Edge() {}
1007 template <typename T> class NodeMap : public DynMapBase<Node>
1009 std::vector<T> container;
1012 typedef T ValueType;
1013 typedef Node KeyType;
1015 NodeMap(const NodeSet &_G) :
1016 DynMapBase<Node>(_G), container(_G.maxNodeId())
1018 G->dyn_node_maps.push_back(this);
1020 NodeMap(const NodeSet &_G,const T &t) :
1021 DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
1023 G->dyn_node_maps.push_back(this);
1026 NodeMap(const NodeMap<T> &m) :
1027 DynMapBase<Node>(*m.G), container(m.container)
1029 G->dyn_node_maps.push_back(this);
1032 template<typename TT> friend class NodeMap;
1034 ///\todo It can copy between different types.
1036 template<typename TT> NodeMap(const NodeMap<TT> &m) :
1037 DynMapBase<Node>(*m.G), container(m.container.size())
1039 G->dyn_node_maps.push_back(this);
1040 typename std::vector<TT>::const_iterator i;
1041 for(typename std::vector<TT>::const_iterator i=m.container.begin();
1042 i!=m.container.end();
1044 container.push_back(*i);
1049 std::vector<DynMapBase<Node>* >::iterator i;
1050 for(i=G->dyn_node_maps.begin();
1051 i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
1052 //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
1053 //A better way to do that: (Is this really important?)
1055 *i=G->dyn_node_maps.back();
1056 G->dyn_node_maps.pop_back();
1061 void add(const Node k)
1063 if(k.n>=int(container.size())) container.resize(k.n+1);
1066 void erase(const Node) { }
1068 void set(Node n, T a) { container[n.n]=a; }
1069 //'T& operator[](Node n)' would be wrong here
1070 typename std::vector<T>::reference
1071 operator[](Node n) { return container[n.n]; }
1072 //'const T& operator[](Node n)' would be wrong here
1073 typename std::vector<T>::const_reference
1074 operator[](Node n) const { return container[n.n]; }
1076 ///\warning There is no safety check at all!
1077 ///Using operator = between maps attached to different graph may
1078 ///cause serious problem.
1079 ///\todo Is this really so?
1080 ///\todo It can copy between different types.
1081 const NodeMap<T>& operator=(const NodeMap<T> &m)
1083 container = m.container;
1086 template<typename TT>
1087 const NodeMap<T>& operator=(const NodeMap<TT> &m)
1089 std::copy(m.container.begin(), m.container.end(), container.begin());
1093 void update() {} //Useless for Dynamic Maps
1094 void update(T a) {} //Useless for Dynamic Maps
1097 template <typename T> class EdgeMap
1100 typedef T ValueType;
1101 typedef Edge KeyType;
1103 EdgeMap(const NodeSet &) { }
1104 EdgeMap(const NodeSet &,const T &) { }
1105 EdgeMap(const EdgeMap<T> &) { }
1106 // template<typename TT> friend class EdgeMap;
1108 ///\todo It can copy between different types.
1110 template<typename TT> EdgeMap(const EdgeMap<TT> &) { }
1113 void add(const Edge ) { }
1114 void erase(const Edge) { }
1116 void set(Edge, T) { }
1117 //T get(Edge n) const { return container[n.n]; }
1118 ValueType &operator[](Edge) { return *((T*)(NULL)); }
1119 const ValueType &operator[](Edge) const { return *((T*)(NULL)); }
1121 const EdgeMap<T>& operator=(const EdgeMap<T> &) { return *this; }
1123 template<typename TT>
1124 const EdgeMap<T>& operator=(const EdgeMap<TT> &m) { return *this; }
1133 ///Graph structure using a node set of another graph.
1135 ///This structure can be used to establish another graph over a node set
1136 /// of an existing one. The node iterator will go through the nodes of the
1137 /// original graph, and the NodeMap's of both graphs will convert to
1140 ///\warning Adding or deleting nodes from the graph is not safe if an
1141 ///\ref EdgeSet is currently attached to it!
1143 ///\todo Make it possible to add/delete edges from the base graph
1144 ///(and from \ref EdgeSet, as well)
1146 ///\param GG The type of the graph which shares its node set with this class.
1147 ///Its interface must conform with \ref GraphSkeleton.
1149 ///It conforms to the graph interface documented under
1150 ///the description of \ref GraphSkeleton.
1151 ///\sa \ref GraphSkeleton.
1152 ///\sa \ref NodeSet.
1153 template<typename GG>
1156 typedef GG NodeGraphType;
1162 int id(Node v) const;
1164 class Node : public NodeGraphType::Node {
1165 friend class EdgeSet;
1166 // template <typename T> friend class NodeMap;
1169 friend class OutEdgeIt;
1170 friend class InEdgeIt;
1171 friend class SymEdge;
1174 friend int EdgeSet::id(Node v) const;
1175 // Node(int nn) {n=nn;}
1177 Node() : NodeGraphType::Node() {}
1178 Node (Invalid i) : NodeGraphType::Node(i) {}
1179 Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {}
1182 class NodeIt : public NodeGraphType::NodeIt {
1183 friend class EdgeSet;
1185 NodeIt() : NodeGraphType::NodeIt() { }
1186 NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {}
1187 NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { }
1188 NodeIt(const typename NodeGraphType::NodeIt &n)
1189 : NodeGraphType::NodeIt(n) {}
1190 ///\todo Undocumented conversion Node -\> NodeIt.
1191 NodeIt(const EdgeSet& _G, const Node &n)
1192 : NodeGraphType::NodeIt(_G.G,n) { }
1194 operator Node() { return Node(*this);}
1198 //Edges are double linked.
1199 //The free edges are only single linked using the "next_in" field.
1202 int first_in,first_out;
1203 NodeT() : first_in(-1), first_out(-1) { }
1209 int prev_in, prev_out;
1210 int next_in, next_out;
1214 typename NodeGraphType::template NodeMap<NodeT> nodes;
1216 std::vector<EdgeT> edges;
1217 //The first free edge
1218 int first_free_edge;
1222 template <typename Key> class DynMapBase
1227 virtual void add(const Key k) = 0;
1228 virtual void erase(const Key k) = 0;
1229 DynMapBase(const EdgeSet &_G) : G(&_G) {}
1230 virtual ~DynMapBase() {}
1231 friend class EdgeSet;
1235 //template <typename T> class NodeMap;
1236 template <typename T> class EdgeMap;
1244 // mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
1245 ///\bug It must be public because of SymEdgeMap.
1247 mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
1256 template <typename T> class NodeMap;
1257 template <typename T> class EdgeMap;
1263 ///Construates a new graph based on the nodeset of an existing one.
1264 ///\param _G the base graph.
1265 ///\todo It looks like a copy constructor, but it isn't.
1266 EdgeSet(NodeGraphType &_G) : G(_G),
1268 first_free_edge(-1) { }
1271 ///Makes a copy of an EdgeSet.
1272 ///It will be based on the same graph.
1273 EdgeSet(const EdgeSet &_g) : G(_g.G), nodes(_g.G), edges(_g.edges),
1274 first_free_edge(_g.first_free_edge) { }
1278 // for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
1279 // i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
1280 for(typename std::vector<DynMapBase<Edge> * >::iterator
1281 i=dyn_edge_maps.begin();
1282 i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
1285 int nodeNum() const { return G.nodeNum(); } //FIXME: What is this?
1286 int edgeNum() const { return edges.size(); } //FIXME: What is this?
1288 ///\bug This function does something different than
1289 ///its name would suggests...
1290 int maxNodeId() const { return G.maxNodeId(); } //FIXME: What is this?
1291 ///\bug This function does something different than
1292 ///its name would suggests...
1293 int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
1295 Node tail(Edge e) const { return edges[e.n].tail; }
1296 Node head(Edge e) const { return edges[e.n].head; }
1298 Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
1299 Node aNode(InEdgeIt e) const { return edges[e.n].head; }
1301 Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
1302 Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
1304 NodeIt& first(NodeIt& v) const {
1305 v=NodeIt(*this); return v; }
1306 EdgeIt& first(EdgeIt& e) const {
1307 e=EdgeIt(*this); return e; }
1308 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
1309 e=OutEdgeIt(*this,v); return e; }
1310 InEdgeIt& first(InEdgeIt& e, const Node v) const {
1311 e=InEdgeIt(*this,v); return e; }
1313 // template< typename It >
1314 // It first() const { It e; first(e); return e; }
1316 // template< typename It >
1317 // It first(Node v) const { It e; first(e,v); return e; }
1319 bool valid(Edge e) const { return e.n!=-1; }
1320 bool valid(Node n) const { return G.valid(n); }
1322 void setInvalid(Edge &e) { e.n=-1; }
1323 void setInvalid(Node &n) { G.setInvalid(n); }
1325 template <typename It> It getNext(It it) const
1326 { It tmp(it); return next(tmp); }
1328 NodeIt& next(NodeIt& it) const { G.next(it); return it; }
1329 OutEdgeIt& next(OutEdgeIt& it) const
1330 { it.n=edges[it.n].next_out; return it; }
1331 InEdgeIt& next(InEdgeIt& it) const
1332 { it.n=edges[it.n].next_in; return it; }
1333 EdgeIt& next(EdgeIt& it) const {
1334 if(edges[it.n].next_in!=-1) {
1335 it.n=edges[it.n].next_in;
1338 NodeIt n(*this,edges[it.n].head);
1340 valid(n) && nodes[n].first_in == -1;
1342 it.n = (valid(n))?-1:nodes[n].first_in;
1347 int id(Edge e) const { return e.n; }
1349 /// Adds a new node to the graph.
1350 Node addNode() { return G.addNode(); }
1352 Edge addEdge(Node u, Node v) {
1355 if(first_free_edge==-1)
1358 edges.push_back(EdgeT());
1361 n = first_free_edge;
1362 first_free_edge = edges[n].next_in;
1365 edges[n].tail = u; edges[n].head = v;
1367 edges[n].next_out = nodes[u].first_out;
1368 if(nodes[u].first_out != -1) edges[nodes[u].first_out].prev_out = n;
1369 edges[n].next_in = nodes[v].first_in;
1370 if(nodes[v].first_in != -1) edges[nodes[v].first_in].prev_in = n;
1371 edges[n].prev_in = edges[n].prev_out = -1;
1373 nodes[u].first_out = nodes[v].first_in = n;
1377 //Update dynamic maps
1378 for(typename std::vector<DynMapBase<Edge> * >::iterator
1379 i=dyn_edge_maps.begin();
1380 i!=dyn_edge_maps.end(); ++i) (**i).add(e);
1386 void eraseEdge(int n) {
1388 if(edges[n].next_in!=-1)
1389 edges[edges[n].next_in].prev_in = edges[n].prev_in;
1390 if(edges[n].prev_in!=-1)
1391 edges[edges[n].prev_in].next_in = edges[n].next_in;
1392 else nodes[edges[n].head].first_in = edges[n].next_in;
1394 if(edges[n].next_out!=-1)
1395 edges[edges[n].next_out].prev_out = edges[n].prev_out;
1396 if(edges[n].prev_out!=-1)
1397 edges[edges[n].prev_out].next_out = edges[n].next_out;
1398 else nodes[edges[n].tail].first_out = edges[n].next_out;
1400 edges[n].next_in = first_free_edge;
1401 first_free_edge = -1;
1403 //Update dynamic maps
1405 for(typename std::vector<DynMapBase<Edge> * >::iterator
1406 i=dyn_edge_maps.begin();
1407 i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
1412 // void erase(Node nn) {
1415 // while((m=nodes[n].first_in)!=-1) eraseEdge(m);
1416 // while((m=nodes[n].first_out)!=-1) eraseEdge(m);
1419 void erase(Edge e) { eraseEdge(e.n); }
1421 ///Clear all edges. (Doesn't clear the nodes!)
1428 // //\bug Dynamic maps must be updated!
1431 // nodes.clear();edges.clear();
1432 // first_node=first_free_node=first_free_edge=-1;
1436 template <typename T> class EdgeMap;
1441 friend class EdgeSet;
1442 template <typename T> friend class EdgeMap;
1445 friend class NodeIt;
1447 ///\bug It shoud be at least protected
1451 friend int EdgeSet::id(Edge e) const;
1453 Edge(int nn) {n=nn;}
1456 Edge (Invalid) { n=-1; }
1457 bool operator==(const Edge i) const {return n==i.n;}
1458 bool operator!=(const Edge i) const {return n!=i.n;}
1459 bool operator<(const Edge i) const {return n<i.n;}
1460 ///\bug This is a workaround until somebody tells me how to
1461 ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
1462 int &idref() {return n;}
1463 const int &idref() const {return n;}
1466 class EdgeIt : public Edge {
1467 friend class EdgeSet;
1468 template <typename T> friend class EdgeMap;
1472 EdgeIt(const EdgeSet& G) : Edge() {
1473 // typename NodeGraphType::Node m;
1476 G.valid(m) && G.nodes[m].first_in == -1; G.next(m));
1477 //AJJAJ! This is a non sense!!!!!!!
1478 this->n = G.valid(m)?-1:G.nodes[m].first_in;
1480 EdgeIt (Invalid i) : Edge(i) { }
1481 EdgeIt() : Edge() { }
1482 ///\bug This is a workaround until somebody tells me how to
1483 ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
1484 int &idref() {return this->n;}
1487 class OutEdgeIt : public Edge {
1488 friend class EdgeSet;
1490 OutEdgeIt() : Edge() { }
1491 OutEdgeIt (Invalid i) : Edge(i) { }
1493 OutEdgeIt(const EdgeSet& G,const Node v) : Edge(G.nodes[v].first_out) { }
1496 class InEdgeIt : public Edge {
1497 friend class EdgeSet;
1499 InEdgeIt() : Edge() { }
1500 InEdgeIt (Invalid i) : Edge(i) { }
1501 InEdgeIt(const EdgeSet& G,Node v) :Edge(G.nodes[v].first_in) { }
1504 template <typename T> class NodeMap :
1505 public NodeGraphType::template NodeMap<T>
1507 //This is a must, the constructors need it.
1508 typedef typename NodeGraphType::template NodeMap<T> ParentNodeMap;
1510 NodeMap(const EdgeSet &_G) : ParentNodeMap(_G.G) { }
1511 NodeMap(const EdgeSet &_G,const T &t) : ParentNodeMap(_G.G,t) { }
1513 NodeMap(const typename NodeGraphType::template NodeMap<T> &m) :
1514 ParentNodeMap(m) { }
1516 ///\todo It can copy between different types.
1518 template<typename TT>
1519 NodeMap(const typename NodeGraphType::template NodeMap<TT> &m)
1520 : ParentNodeMap(m) { }
1524 template <typename T> class EdgeMap : public DynMapBase<Edge>
1528 ///\bug It should be at least protected
1530 std::vector<T> container;
1533 typedef T ValueType;
1534 typedef Edge KeyType;
1536 EdgeMap(const EdgeSet &_G) :
1537 DynMapBase<Edge>(_G), container(_G.maxEdgeId())
1539 //FIXME: What if there are empty Id's?
1540 //FIXME: Can I use 'this' in a constructor?
1541 G->dyn_edge_maps.push_back(this);
1543 EdgeMap(const EdgeSet &_G,const T &t) :
1544 DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
1546 G->dyn_edge_maps.push_back(this);
1548 EdgeMap(const EdgeMap<T> &m) :
1549 DynMapBase<Edge>(*m.G), container(m.container)
1551 G->dyn_edge_maps.push_back(this);
1554 template<typename TT> friend class EdgeMap;
1556 ///\todo It can copy between different types.
1558 template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
1559 DynMapBase<Edge>(*m.G), container(m.container.size())
1561 G->dyn_edge_maps.push_back(this);
1562 typename std::vector<TT>::const_iterator i;
1563 for(typename std::vector<TT>::const_iterator i=m.container.begin();
1564 i!=m.container.end();
1566 container.push_back(*i);
1571 typename std::vector<DynMapBase<Edge>* >::iterator i;
1572 for(i=G->dyn_edge_maps.begin();
1573 i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
1574 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
1575 //A better way to do that: (Is this really important?)
1577 *i=G->dyn_edge_maps.back();
1578 G->dyn_edge_maps.pop_back();
1583 void add(const Edge k)
1585 if(k.n>=int(container.size())) container.resize(k.n+1);
1587 void erase(const Edge) { }
1589 ///\bug This doesn't work. Why?
1590 /// void set(Edge n, T a) { container[n.n]=a; }
1591 void set(Edge n, T a) { container[G->id(n)]=a; }
1592 //T get(Edge n) const { return container[n.n]; }
1593 typename std::vector<T>::reference
1594 ///\bug This doesn't work. Why?
1595 /// operator[](Edge n) { return container[n.n]; }
1596 operator[](Edge n) { return container[G->id(n)]; }
1597 typename std::vector<T>::const_reference
1598 ///\bug This doesn't work. Why?
1599 /// operator[](Edge n) const { return container[n.n]; }
1600 operator[](Edge n) const { return container[G->id(n)]; }
1602 ///\warning There is no safety check at all!
1603 ///Using operator = between maps attached to different graph may
1604 ///cause serious problem.
1605 ///\todo Is this really so?
1606 ///\todo It can copy between different types.
1607 const EdgeMap<T>& operator=(const EdgeMap<T> &m)
1609 container = m.container;
1613 template<typename TT> friend class EdgeMap;
1615 template<typename TT>
1616 const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
1618 std::copy(m.container.begin(), m.container.end(), container.begin());
1622 void update() {} //Useless for DynMaps
1623 void update(T a) {} //Useless for DynMaps
1628 template<typename GG>
1629 inline int EdgeSet<GG>::id(Node v) const { return G.id(v); }
1635 #endif //HUGO_LIST_GRAPH_H