Oops: "static" and "const" does not like each other.
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 ///Set the expected number of edges
119 ///With this function, it is possible to set the expected number of edges.
120 ///The use of this fasten the building of the graph and makes
121 ///it possible to avoid the superfluous memory allocation.
122 void reserveEdge(int n) { edges.reserve(n); };
124 ///\bug This function does something different than
125 ///its name would suggests...
126 int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
127 ///\bug This function does something different than
128 ///its name would suggests...
129 int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
131 Node tail(Edge e) const { return edges[e.n].tail; }
132 Node head(Edge e) const { return edges[e.n].head; }
134 Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
135 Node aNode(InEdgeIt e) const { return edges[e.n].head; }
137 Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
138 Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
140 NodeIt& first(NodeIt& v) const {
141 v=NodeIt(*this); return v; }
142 EdgeIt& first(EdgeIt& e) const {
143 e=EdgeIt(*this); return e; }
144 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
145 e=OutEdgeIt(*this,v); return e; }
146 InEdgeIt& first(InEdgeIt& e, const Node v) const {
147 e=InEdgeIt(*this,v); return e; }
149 // template< typename It >
150 // It first() const { It e; first(e); return e; }
152 // template< typename It >
153 // It first(Node v) const { It e; first(e,v); return e; }
155 static bool valid(Edge e) { return e.n!=-1; }
156 static bool valid(Node n) { return n.n!=-1; }
158 static void setInvalid(Edge &e) { e.n=-1; }
159 static void setInvalid(Node &n) { n.n=-1; }
161 template <typename It> static It getNext(It it)
162 { It tmp(it); return next(tmp); }
164 NodeIt& next(NodeIt& it) const {
165 it.n=nodes[it.n].next;
168 OutEdgeIt& next(OutEdgeIt& it) const
169 { it.n=edges[it.n].next_out; return it; }
170 InEdgeIt& next(InEdgeIt& it) const
171 { it.n=edges[it.n].next_in; return it; }
172 EdgeIt& next(EdgeIt& it) const {
173 if(edges[it.n].next_in!=-1) {
174 it.n=edges[it.n].next_in;
178 for(n=nodes[edges[it.n].head].next;
179 n!=-1 && nodes[n].first_in == -1;
181 it.n = (n==-1)?-1:nodes[n].first_in;
186 static int id(Node v) { return v.n; }
187 static int id(Edge e) { return e.n; }
189 /// Adds a new node to the graph.
191 /// \todo It adds the nodes in a reversed order.
192 /// (i.e. the lastly added node becomes the first.)
196 if(first_free_node==-1)
199 nodes.push_back(NodeT());
203 first_free_node = nodes[n].next;
206 nodes[n].next = first_node;
207 if(first_node != -1) nodes[first_node].prev = n;
211 nodes[n].first_in = nodes[n].first_out = -1;
215 //Update dynamic maps
216 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
217 i!=dyn_node_maps.end(); ++i) (**i).add(nn);
222 Edge addEdge(Node u, Node v) {
225 if(first_free_edge==-1)
228 edges.push_back(EdgeT());
232 first_free_edge = edges[n].next_in;
235 edges[n].tail = u.n; edges[n].head = v.n;
237 edges[n].next_out = nodes[u.n].first_out;
238 if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n;
239 edges[n].next_in = nodes[v.n].first_in;
240 if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n;
241 edges[n].prev_in = edges[n].prev_out = -1;
243 nodes[u.n].first_out = nodes[v.n].first_in = n;
247 //Update dynamic maps
248 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
249 i!=dyn_edge_maps.end(); ++i) (**i).add(e);
255 void eraseEdge(int n) {
257 if(edges[n].next_in!=-1)
258 edges[edges[n].next_in].prev_in = edges[n].prev_in;
259 if(edges[n].prev_in!=-1)
260 edges[edges[n].prev_in].next_in = edges[n].next_in;
261 else nodes[edges[n].head].first_in = edges[n].next_in;
263 if(edges[n].next_out!=-1)
264 edges[edges[n].next_out].prev_out = edges[n].prev_out;
265 if(edges[n].prev_out!=-1)
266 edges[edges[n].prev_out].next_out = edges[n].next_out;
267 else nodes[edges[n].tail].first_out = edges[n].next_out;
269 edges[n].next_in = first_free_edge;
272 //Update dynamic maps
274 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
275 i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
280 void erase(Node nn) {
284 while((m=nodes[n].first_in)!=-1) eraseEdge(m);
285 while((m=nodes[n].first_out)!=-1) eraseEdge(m);
287 if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
288 if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
289 else first_node = nodes[n].next;
291 nodes[n].next = first_free_node;
294 //Update dynamic maps
295 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
296 i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
299 void erase(Edge e) { eraseEdge(e.n); }
301 ///\bug Dynamic maps must be updated!
304 nodes.clear();edges.clear();
305 first_node=first_free_node=first_free_edge=-1;
309 friend class ListGraph;
310 template <typename T> friend class NodeMap;
313 friend class OutEdgeIt;
314 friend class InEdgeIt;
315 friend class SymEdge;
319 friend int ListGraph::id(Node v) const;
323 Node (Invalid) { n=-1; }
324 bool operator==(const Node i) const {return n==i.n;}
325 bool operator!=(const Node i) const {return n!=i.n;}
326 bool operator<(const Node i) const {return n<i.n;}
329 class NodeIt : public Node {
330 friend class ListGraph;
332 NodeIt() : Node() { }
333 NodeIt(Invalid i) : Node(i) { }
334 NodeIt(const ListGraph& G) : Node(G.first_node) { }
335 ///\todo Undocumented conversion Node -\> NodeIt.
336 NodeIt(const ListGraph& G, const Node &n) : Node(n) { }
340 friend class ListGraph;
341 template <typename T> friend class EdgeMap;
343 //template <typename T> friend class SymListGraph::SymEdgeMap;
344 //friend Edge SymListGraph::opposite(Edge) const;
350 friend int ListGraph::id(Edge e) const;
353 /// An Edge with id \c n.
355 /// \bug It should be
356 /// obtained by a member function of the Graph.
360 Edge (Invalid) { n=-1; }
361 bool operator==(const Edge i) const {return n==i.n;}
362 bool operator!=(const Edge i) const {return n!=i.n;}
363 bool operator<(const Edge i) const {return n<i.n;}
364 ///\bug This is a workaround until somebody tells me how to
365 ///make class \c SymListGraph::SymEdgeMap friend of Edge
366 int &idref() {return n;}
367 const int &idref() const {return n;}
370 class EdgeIt : public Edge {
371 friend class ListGraph;
373 EdgeIt(const ListGraph& G) : Edge() {
376 m!=-1 && G.nodes[m].first_in == -1; m = G.nodes[m].next);
377 n = (m==-1)?-1:G.nodes[m].first_in;
379 EdgeIt (Invalid i) : Edge(i) { }
380 EdgeIt() : Edge() { }
381 ///\bug This is a workaround until somebody tells me how to
382 ///make class \c SymListGraph::SymEdgeMap friend of Edge
383 int &idref() {return n;}
386 class OutEdgeIt : public Edge {
387 friend class ListGraph;
389 OutEdgeIt() : Edge() { }
390 OutEdgeIt (Invalid i) : Edge(i) { }
392 OutEdgeIt(const ListGraph& G,const Node v)
393 : Edge(G.nodes[v.n].first_out) {}
396 class InEdgeIt : public Edge {
397 friend class ListGraph;
399 InEdgeIt() : Edge() { }
400 InEdgeIt (Invalid i) : Edge(i) { }
401 InEdgeIt(const ListGraph& G,Node v) :Edge(G.nodes[v.n].first_in) {}
404 template <typename T> class NodeMap : public DynMapBase<Node>
406 std::vector<T> container;
410 typedef Node KeyType;
412 NodeMap(const ListGraph &_G) :
413 DynMapBase<Node>(_G), container(_G.maxNodeId())
415 G->dyn_node_maps.push_back(this);
417 NodeMap(const ListGraph &_G,const T &t) :
418 DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
420 G->dyn_node_maps.push_back(this);
423 NodeMap(const NodeMap<T> &m) :
424 DynMapBase<Node>(*m.G), container(m.container)
426 G->dyn_node_maps.push_back(this);
429 template<typename TT> friend class NodeMap;
431 ///\todo It can copy between different types.
433 template<typename TT> NodeMap(const NodeMap<TT> &m) :
434 DynMapBase<Node>(*m.G), container(m.container.size())
437 G->dyn_node_maps.push_back(this);
438 typename std::vector<TT>::const_iterator i;
439 for(typename std::vector<TT>::const_iterator i=m.container.begin();
440 i!=m.container.end();
442 container.push_back(*i);
447 std::vector<DynMapBase<Node>* >::iterator i;
448 for(i=G->dyn_node_maps.begin();
449 i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
450 //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
451 //A better way to do that: (Is this really important?)
453 *i=G->dyn_node_maps.back();
454 G->dyn_node_maps.pop_back();
459 void add(const Node k)
461 if(k.n>=int(container.size())) container.resize(k.n+1);
464 void erase(const Node) { }
466 void set(Node n, T a) { container[n.n]=a; }
467 //'T& operator[](Node n)' would be wrong here
468 typename std::vector<T>::reference
469 operator[](Node n) { return container[n.n]; }
470 //'const T& operator[](Node n)' would be wrong here
471 typename std::vector<T>::const_reference
472 operator[](Node n) const { return container[n.n]; }
474 ///\warning There is no safety check at all!
475 ///Using operator = between maps attached to different graph may
476 ///cause serious problem.
477 ///\todo Is this really so?
478 ///\todo It can copy between different types.
479 const NodeMap<T>& operator=(const NodeMap<T> &m)
481 container = m.container;
484 template<typename TT>
485 const NodeMap<T>& operator=(const NodeMap<TT> &m)
487 std::copy(m.container.begin(), m.container.end(), container.begin());
491 void update() {} //Useless for Dynamic Maps
492 void update(T a) {} //Useless for Dynamic Maps
495 template <typename T> class EdgeMap : public DynMapBase<Edge>
498 std::vector<T> container;
502 typedef Edge KeyType;
504 EdgeMap(const ListGraph &_G) :
505 DynMapBase<Edge>(_G), container(_G.maxEdgeId())
507 //FIXME: What if there are empty Id's?
508 //FIXME: Can I use 'this' in a constructor?
509 G->dyn_edge_maps.push_back(this);
511 EdgeMap(const ListGraph &_G,const T &t) :
512 DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
514 G->dyn_edge_maps.push_back(this);
516 EdgeMap(const EdgeMap<T> &m) :
517 DynMapBase<Edge>(*m.G), container(m.container)
519 G->dyn_edge_maps.push_back(this);
522 template<typename TT> friend class EdgeMap;
524 ///\todo It can copy between different types.
526 template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
527 DynMapBase<Edge>(*m.G), container(m.container.size())
529 G->dyn_edge_maps.push_back(this);
530 typename std::vector<TT>::const_iterator i;
531 for(typename std::vector<TT>::const_iterator i=m.container.begin();
532 i!=m.container.end();
534 container.push_back(*i);
539 std::vector<DynMapBase<Edge>* >::iterator i;
540 for(i=G->dyn_edge_maps.begin();
541 i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
542 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
543 //A better way to do that: (Is this really important?)
545 *i=G->dyn_edge_maps.back();
546 G->dyn_edge_maps.pop_back();
551 void add(const Edge k)
553 if(k.n>=int(container.size())) container.resize(k.n+1);
555 void erase(const Edge) { }
557 void set(Edge n, T a) { container[n.n]=a; }
558 //T get(Edge n) const { return container[n.n]; }
559 typename std::vector<T>::reference
560 operator[](Edge n) { return container[n.n]; }
561 typename std::vector<T>::const_reference
562 operator[](Edge n) const { return container[n.n]; }
564 ///\warning There is no safety check at all!
565 ///Using operator = between maps attached to different graph may
566 ///cause serious problem.
567 ///\todo Is this really so?
568 ///\todo It can copy between different types.
569 const EdgeMap<T>& operator=(const EdgeMap<T> &m)
571 container = m.container;
574 template<typename TT>
575 const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
577 std::copy(m.container.begin(), m.container.end(), container.begin());
581 void update() {} //Useless for DynMaps
582 void update(T a) {} //Useless for DynMaps
587 ///Graph for bidirectional edges.
589 ///The purpose of this graph structure is to handle graphs
590 ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
591 ///of oppositely directed edges.
592 ///There is a new edge map type called
593 ///\ref SymListGraph::SymEdgeMap "SymEdgeMap"
594 ///that complements this
596 ///storing shared values for the edge pairs. The usual
597 ///\ref GraphSkeleton::EdgeMap "EdgeMap"
601 ///The oppositely directed edge can also be obtained easily
602 ///using \ref opposite.
604 ///Here erase(Edge) deletes a pair of edges.
606 ///\todo this date structure need some reconsiderations. Maybe it
607 ///should be implemented independently from ListGraph.
609 class SymListGraph : public ListGraph
612 template<typename T> class SymEdgeMap;
613 template<typename T> friend class SymEdgeMap;
615 SymListGraph() : ListGraph() { }
616 SymListGraph(const ListGraph &_g) : ListGraph(_g) { }
617 ///Adds a pair of oppositely directed edges to the graph.
618 Edge addEdge(Node u, Node v)
620 Edge e = ListGraph::addEdge(u,v);
621 ListGraph::addEdge(v,u);
625 void erase(Node n) { ListGraph::erase(n); }
626 ///The oppositely directed edge.
628 ///Returns the oppositely directed
629 ///pair of the edge \c e.
630 static Edge opposite(Edge e)
633 f.idref() = e.idref() - 2*(e.idref()%2) + 1;
637 ///Removes a pair of oppositely directed edges to the graph.
639 ListGraph::erase(opposite(e));
643 ///Common data storage for the edge pairs.
645 ///This map makes it possible to store data shared by the oppositely
646 ///directed pairs of edges.
647 template <typename T> class SymEdgeMap : public DynMapBase<Edge>
649 std::vector<T> container;
653 typedef Edge KeyType;
655 SymEdgeMap(const SymListGraph &_G) :
656 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
658 static_cast<const SymListGraph*>(G)->dyn_edge_maps.push_back(this);
660 SymEdgeMap(const SymListGraph &_G,const T &t) :
661 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
663 G->dyn_edge_maps.push_back(this);
666 SymEdgeMap(const SymEdgeMap<T> &m) :
667 DynMapBase<SymEdge>(*m.G), container(m.container)
669 G->dyn_node_maps.push_back(this);
672 // template<typename TT> friend class SymEdgeMap;
674 ///\todo It can copy between different types.
677 template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :
678 DynMapBase<SymEdge>(*m.G), container(m.container.size())
680 G->dyn_node_maps.push_back(this);
681 typename std::vector<TT>::const_iterator i;
682 for(typename std::vector<TT>::const_iterator i=m.container.begin();
683 i!=m.container.end();
685 container.push_back(*i);
691 std::vector<DynMapBase<Edge>* >::iterator i;
692 for(i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.begin();
693 i!=static_cast<const SymListGraph*>(G)->dyn_edge_maps.end()
695 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
696 //A better way to do that: (Is this really important?)
698 *i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.back();
699 static_cast<const SymListGraph*>(G)->dyn_edge_maps.pop_back();
704 void add(const Edge k)
706 if(!k.idref()%2&&k.idref()/2>=int(container.size()))
707 container.resize(k.idref()/2+1);
709 void erase(const Edge k) { }
711 void set(Edge n, T a) { container[n.idref()/2]=a; }
712 //T get(Edge n) const { return container[n.idref()/2]; }
713 typename std::vector<T>::reference
714 operator[](Edge n) { return container[n.idref()/2]; }
715 typename std::vector<T>::const_reference
716 operator[](Edge n) const { return container[n.idref()/2]; }
718 ///\warning There is no safety check at all!
719 ///Using operator = between maps attached to different graph may
720 ///cause serious problem.
721 ///\todo Is this really so?
722 ///\todo It can copy between different types.
723 const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
725 container = m.container;
728 template<typename TT>
729 const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
731 std::copy(m.container.begin(), m.container.end(), container.begin());
735 void update() {} //Useless for DynMaps
736 void update(T a) {} //Useless for DynMaps
743 ///A graph class containing only nodes.
745 ///This class implements a graph structure without edges.
746 ///The most useful application of this class is to be the node set of an
747 ///\ref EdgeSet class.
749 ///It conforms to the graph interface documented under
750 ///the description of \ref GraphSkeleton with the exception that you cannot
751 ///add (or delete) edges. The usual edge iterators are exists, but they are
752 ///always \ref INVALID.
753 ///\sa \ref GraphSkeleton
757 //Nodes are double linked.
758 //The free nodes are only single linked using the "next" field.
761 int first_in,first_out;
766 std::vector<NodeT> nodes;
769 //The first free node
774 template <typename Key> class DynMapBase
779 virtual void add(const Key k) = 0;
780 virtual void erase(const Key k) = 0;
781 DynMapBase(const NodeSet &_G) : G(&_G) {}
782 virtual ~DynMapBase() {}
783 friend class NodeSet;
787 template <typename T> class EdgeMap;
788 template <typename T> class NodeMap;
796 ///\bug It must be public because of SymEdgeMap.
798 mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
799 //mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
808 template <typename T> class NodeMap;
809 template <typename T> class EdgeMap;
813 ///Default constructor
814 NodeSet() : nodes(), first_node(-1),
815 first_free_node(-1) {}
817 NodeSet(const NodeSet &_g) : nodes(_g.nodes), first_node(_g.first_node),
818 first_free_node(_g.first_free_node) {}
822 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
823 i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
824 //for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
825 // i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
828 int nodeNum() const { return nodes.size(); } //FIXME: What is this?
829 int edgeNum() const { return 0; } //FIXME: What is this?
831 ///\bug This function does something different than
832 ///its name would suggests...
833 int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
834 ///\bug This function does something different than
835 ///its name would suggests...
836 int maxEdgeId() const { return 0; } //FIXME: What is this?
838 Node tail(Edge e) const { return INVALID; }
839 Node head(Edge e) const { return INVALID; }
841 Node aNode(OutEdgeIt e) const { return INVALID; }
842 Node aNode(InEdgeIt e) const { return INVALID; }
844 Node bNode(OutEdgeIt e) const { return INVALID; }
845 Node bNode(InEdgeIt e) const { return INVALID; }
847 NodeIt& first(NodeIt& v) const {
848 v=NodeIt(*this); return v; }
849 EdgeIt& first(EdgeIt& e) const {
850 e=EdgeIt(*this); return e; }
851 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
852 e=OutEdgeIt(*this,v); return e; }
853 InEdgeIt& first(InEdgeIt& e, const Node v) const {
854 e=InEdgeIt(*this,v); return e; }
856 // template< typename It >
857 // It first() const { It e; first(e); return e; }
859 // template< typename It >
860 // It first(Node v) const { It e; first(e,v); return e; }
862 bool valid(Edge e) const { return false; }
863 bool valid(Node n) const { return n.n!=-1; }
865 void setInvalid(Edge &e) { }
866 void setInvalid(Node &n) { n.n=-1; }
868 template <typename It> It getNext(It it) const
869 { It tmp(it); return next(tmp); }
871 NodeIt& next(NodeIt& it) const {
872 it.n=nodes[it.n].next;
875 OutEdgeIt& next(OutEdgeIt& it) const { return it; }
876 InEdgeIt& next(InEdgeIt& it) const { return it; }
877 EdgeIt& next(EdgeIt& it) const { return it; }
879 int id(Node v) const { return v.n; }
880 int id(Edge e) const { return -1; }
882 /// Adds a new node to the graph.
884 /// \todo It adds the nodes in a reversed order.
885 /// (i.e. the lastly added node becomes the first.)
889 if(first_free_node==-1)
892 nodes.push_back(NodeT());
896 first_free_node = nodes[n].next;
899 nodes[n].next = first_node;
900 if(first_node != -1) nodes[first_node].prev = n;
904 nodes[n].first_in = nodes[n].first_out = -1;
908 //Update dynamic maps
909 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
910 i!=dyn_node_maps.end(); ++i) (**i).add(nn);
915 void erase(Node nn) {
918 if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
919 if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
920 else first_node = nodes[n].next;
922 nodes[n].next = first_free_node;
925 //Update dynamic maps
926 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
927 i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
930 ///\bug Dynamic maps must be updated!
934 first_node = first_free_node = -1;
938 friend class NodeSet;
939 template <typename T> friend class NodeMap;
942 friend class OutEdgeIt;
943 friend class InEdgeIt;
947 friend int NodeSet::id(Node v) const;
951 Node (Invalid i) { n=-1; }
952 bool operator==(const Node i) const {return n==i.n;}
953 bool operator!=(const Node i) const {return n!=i.n;}
954 bool operator<(const Node i) const {return n<i.n;}
957 class NodeIt : public Node {
958 friend class NodeSet;
960 NodeIt() : Node() { }
961 NodeIt(Invalid i) : Node(i) { }
962 NodeIt(const NodeSet& G) : Node(G.first_node) { }
963 ///\todo Undocumented conversion Node -\> NodeIt.
964 NodeIt(const NodeSet& G, const Node &n) : Node(n) { }
969 //friend class NodeSet;
970 //template <typename T> friend class EdgeMap;
972 //template <typename T> friend class SymNodeSet::SymEdgeMap;
973 //friend Edge SymNodeSet::opposite(Edge) const;
975 // friend class Node;
976 // friend class NodeIt;
978 //friend int NodeSet::id(Edge e) const;
983 bool operator==(const Edge i) const {return true;}
984 bool operator!=(const Edge i) const {return false;}
985 bool operator<(const Edge i) const {return false;}
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;}
989 // int idref() const {return -1;}
992 class EdgeIt : public Edge {
993 //friend class NodeSet;
995 EdgeIt(const NodeSet& G) : Edge() { }
996 EdgeIt (Invalid i) : Edge(i) { }
997 EdgeIt() : Edge() { }
998 ///\bug This is a workaround until somebody tells me how to
999 ///make class \c SymNodeSet::SymEdgeMap friend of Edge
1000 // int idref() {return -1;}
1003 class OutEdgeIt : public Edge {
1004 friend class NodeSet;
1006 OutEdgeIt() : Edge() { }
1007 OutEdgeIt (Invalid i) : Edge(i) { }
1008 OutEdgeIt(const NodeSet& G,const Node v) : Edge() {}
1011 class InEdgeIt : public Edge {
1012 friend class NodeSet;
1014 InEdgeIt() : Edge() { }
1015 InEdgeIt (Invalid i) : Edge(i) { }
1016 InEdgeIt(const NodeSet& G,Node v) :Edge() {}
1019 template <typename T> class NodeMap : public DynMapBase<Node>
1021 std::vector<T> container;
1024 typedef T ValueType;
1025 typedef Node KeyType;
1027 NodeMap(const NodeSet &_G) :
1028 DynMapBase<Node>(_G), container(_G.maxNodeId())
1030 G->dyn_node_maps.push_back(this);
1032 NodeMap(const NodeSet &_G,const T &t) :
1033 DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
1035 G->dyn_node_maps.push_back(this);
1038 NodeMap(const NodeMap<T> &m) :
1039 DynMapBase<Node>(*m.G), container(m.container)
1041 G->dyn_node_maps.push_back(this);
1044 template<typename TT> friend class NodeMap;
1046 ///\todo It can copy between different types.
1048 template<typename TT> NodeMap(const NodeMap<TT> &m) :
1049 DynMapBase<Node>(*m.G), container(m.container.size())
1051 G->dyn_node_maps.push_back(this);
1052 typename std::vector<TT>::const_iterator i;
1053 for(typename std::vector<TT>::const_iterator i=m.container.begin();
1054 i!=m.container.end();
1056 container.push_back(*i);
1061 std::vector<DynMapBase<Node>* >::iterator i;
1062 for(i=G->dyn_node_maps.begin();
1063 i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
1064 //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
1065 //A better way to do that: (Is this really important?)
1067 *i=G->dyn_node_maps.back();
1068 G->dyn_node_maps.pop_back();
1073 void add(const Node k)
1075 if(k.n>=int(container.size())) container.resize(k.n+1);
1078 void erase(const Node) { }
1080 void set(Node n, T a) { container[n.n]=a; }
1081 //'T& operator[](Node n)' would be wrong here
1082 typename std::vector<T>::reference
1083 operator[](Node n) { return container[n.n]; }
1084 //'const T& operator[](Node n)' would be wrong here
1085 typename std::vector<T>::const_reference
1086 operator[](Node n) const { return container[n.n]; }
1088 ///\warning There is no safety check at all!
1089 ///Using operator = between maps attached to different graph may
1090 ///cause serious problem.
1091 ///\todo Is this really so?
1092 ///\todo It can copy between different types.
1093 const NodeMap<T>& operator=(const NodeMap<T> &m)
1095 container = m.container;
1098 template<typename TT>
1099 const NodeMap<T>& operator=(const NodeMap<TT> &m)
1101 std::copy(m.container.begin(), m.container.end(), container.begin());
1105 void update() {} //Useless for Dynamic Maps
1106 void update(T a) {} //Useless for Dynamic Maps
1109 template <typename T> class EdgeMap
1112 typedef T ValueType;
1113 typedef Edge KeyType;
1115 EdgeMap(const NodeSet &) { }
1116 EdgeMap(const NodeSet &,const T &) { }
1117 EdgeMap(const EdgeMap<T> &) { }
1118 // template<typename TT> friend class EdgeMap;
1120 ///\todo It can copy between different types.
1122 template<typename TT> EdgeMap(const EdgeMap<TT> &) { }
1125 void add(const Edge ) { }
1126 void erase(const Edge) { }
1128 void set(Edge, T) { }
1129 //T get(Edge n) const { return container[n.n]; }
1130 ValueType &operator[](Edge) { return *((T*)(NULL)); }
1131 const ValueType &operator[](Edge) const { return *((T*)(NULL)); }
1133 const EdgeMap<T>& operator=(const EdgeMap<T> &) { return *this; }
1135 template<typename TT>
1136 const EdgeMap<T>& operator=(const EdgeMap<TT> &m) { return *this; }
1145 ///Graph structure using a node set of another graph.
1147 ///This structure can be used to establish another graph over a node set
1148 /// of an existing one. The node iterator will go through the nodes of the
1149 /// original graph, and the NodeMap's of both graphs will convert to
1152 ///\warning Adding or deleting nodes from the graph is not safe if an
1153 ///\ref EdgeSet is currently attached to it!
1155 ///\todo Make it possible to add/delete edges from the base graph
1156 ///(and from \ref EdgeSet, as well)
1158 ///\param GG The type of the graph which shares its node set with this class.
1159 ///Its interface must conform with \ref GraphSkeleton.
1161 ///It conforms to the graph interface documented under
1162 ///the description of \ref GraphSkeleton.
1163 ///\sa \ref GraphSkeleton.
1164 ///\sa \ref NodeSet.
1165 template<typename GG>
1168 typedef GG NodeGraphType;
1178 int id(Node v) const;
1180 class Node : public NodeGraphType::Node {
1181 friend class EdgeSet;
1182 // template <typename T> friend class NodeMap;
1185 friend class OutEdgeIt;
1186 friend class InEdgeIt;
1187 friend class SymEdge;
1190 friend int EdgeSet::id(Node v) const;
1191 // Node(int nn) {n=nn;}
1193 Node() : NodeGraphType::Node() {}
1194 Node (Invalid i) : NodeGraphType::Node(i) {}
1195 Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {}
1198 class NodeIt : public NodeGraphType::NodeIt {
1199 friend class EdgeSet;
1201 NodeIt() : NodeGraphType::NodeIt() { }
1202 NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {}
1203 NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { }
1204 NodeIt(const typename NodeGraphType::NodeIt &n)
1205 : NodeGraphType::NodeIt(n) {}
1206 ///\todo Undocumented conversion Node -\> NodeIt.
1207 NodeIt(const EdgeSet& _G, const Node &n)
1208 : NodeGraphType::NodeIt(_G.G,n) { }
1210 operator Node() { return Node(*this);}
1214 //Edges are double linked.
1215 //The free edges are only single linked using the "next_in" field.
1218 int first_in,first_out;
1219 NodeT() : first_in(-1), first_out(-1) { }
1225 int prev_in, prev_out;
1226 int next_in, next_out;
1230 typename NodeGraphType::template NodeMap<NodeT> nodes;
1232 std::vector<EdgeT> edges;
1233 //The first free edge
1234 int first_free_edge;
1238 template <typename Key> class DynMapBase
1243 virtual void add(const Key k) = 0;
1244 virtual void erase(const Key k) = 0;
1245 DynMapBase(const EdgeSet &_G) : G(&_G) {}
1246 virtual ~DynMapBase() {}
1247 friend class EdgeSet;
1251 //template <typename T> class NodeMap;
1252 template <typename T> class EdgeMap;
1260 // mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
1261 ///\bug It must be public because of SymEdgeMap.
1263 mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
1272 template <typename T> class NodeMap;
1273 template <typename T> class EdgeMap;
1279 ///Construates a new graph based on the nodeset of an existing one.
1280 ///\param _G the base graph.
1281 ///\todo It looks like a copy constructor, but it isn't.
1282 EdgeSet(NodeGraphType &_G) : G(_G),
1284 first_free_edge(-1) { }
1287 ///Makes a copy of an EdgeSet.
1288 ///It will be based on the same graph.
1289 EdgeSet(const EdgeSet &_g) : G(_g.G), nodes(_g.G), edges(_g.edges),
1290 first_free_edge(_g.first_free_edge) { }
1294 // for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
1295 // i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
1296 for(typename std::vector<DynMapBase<Edge> * >::iterator
1297 i=dyn_edge_maps.begin();
1298 i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
1301 int nodeNum() const { return G.nodeNum(); } //FIXME: What is this?
1302 int edgeNum() const { return edges.size(); } //FIXME: What is this?
1304 ///\bug This function does something different than
1305 ///its name would suggests...
1306 int maxNodeId() const { return G.maxNodeId(); } //FIXME: What is this?
1307 ///\bug This function does something different than
1308 ///its name would suggests...
1309 int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
1311 Node tail(Edge e) const { return edges[e.n].tail; }
1312 Node head(Edge e) const { return edges[e.n].head; }
1314 Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
1315 Node aNode(InEdgeIt e) const { return edges[e.n].head; }
1317 Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
1318 Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
1320 NodeIt& first(NodeIt& v) const {
1321 v=NodeIt(*this); return v; }
1322 EdgeIt& first(EdgeIt& e) const {
1323 e=EdgeIt(*this); return e; }
1324 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
1325 e=OutEdgeIt(*this,v); return e; }
1326 InEdgeIt& first(InEdgeIt& e, const Node v) const {
1327 e=InEdgeIt(*this,v); return e; }
1329 // template< typename It >
1330 // It first() const { It e; first(e); return e; }
1332 // template< typename It >
1333 // It first(Node v) const { It e; first(e,v); return e; }
1335 bool valid(Edge e) const { return e.n!=-1; }
1336 bool valid(Node n) const { return G.valid(n); }
1338 void setInvalid(Edge &e) { e.n=-1; }
1339 void setInvalid(Node &n) { G.setInvalid(n); }
1341 template <typename It> It getNext(It it) const
1342 { It tmp(it); return next(tmp); }
1344 NodeIt& next(NodeIt& it) const { G.next(it); return it; }
1345 OutEdgeIt& next(OutEdgeIt& it) const
1346 { it.n=edges[it.n].next_out; return it; }
1347 InEdgeIt& next(InEdgeIt& it) const
1348 { it.n=edges[it.n].next_in; return it; }
1349 EdgeIt& next(EdgeIt& it) const {
1350 if(edges[it.n].next_in!=-1) {
1351 it.n=edges[it.n].next_in;
1354 NodeIt n(*this,edges[it.n].head);
1356 valid(n) && nodes[n].first_in == -1;
1358 it.n = (valid(n))?-1:nodes[n].first_in;
1363 int id(Edge e) const { return e.n; }
1365 /// Adds a new node to the graph.
1366 Node addNode() { return G.addNode(); }
1368 Edge addEdge(Node u, Node v) {
1371 if(first_free_edge==-1)
1374 edges.push_back(EdgeT());
1377 n = first_free_edge;
1378 first_free_edge = edges[n].next_in;
1381 edges[n].tail = u; edges[n].head = v;
1383 edges[n].next_out = nodes[u].first_out;
1384 if(nodes[u].first_out != -1) edges[nodes[u].first_out].prev_out = n;
1385 edges[n].next_in = nodes[v].first_in;
1386 if(nodes[v].first_in != -1) edges[nodes[v].first_in].prev_in = n;
1387 edges[n].prev_in = edges[n].prev_out = -1;
1389 nodes[u].first_out = nodes[v].first_in = n;
1393 //Update dynamic maps
1394 for(typename std::vector<DynMapBase<Edge> * >::iterator
1395 i=dyn_edge_maps.begin();
1396 i!=dyn_edge_maps.end(); ++i) (**i).add(e);
1402 void eraseEdge(int n) {
1404 if(edges[n].next_in!=-1)
1405 edges[edges[n].next_in].prev_in = edges[n].prev_in;
1406 if(edges[n].prev_in!=-1)
1407 edges[edges[n].prev_in].next_in = edges[n].next_in;
1408 else nodes[edges[n].head].first_in = edges[n].next_in;
1410 if(edges[n].next_out!=-1)
1411 edges[edges[n].next_out].prev_out = edges[n].prev_out;
1412 if(edges[n].prev_out!=-1)
1413 edges[edges[n].prev_out].next_out = edges[n].next_out;
1414 else nodes[edges[n].tail].first_out = edges[n].next_out;
1416 edges[n].next_in = first_free_edge;
1417 first_free_edge = -1;
1419 //Update dynamic maps
1421 for(typename std::vector<DynMapBase<Edge> * >::iterator
1422 i=dyn_edge_maps.begin();
1423 i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
1428 // void erase(Node nn) {
1431 // while((m=nodes[n].first_in)!=-1) eraseEdge(m);
1432 // while((m=nodes[n].first_out)!=-1) eraseEdge(m);
1435 void erase(Edge e) { eraseEdge(e.n); }
1437 ///Clear all edges. (Doesn't clear the nodes!)
1444 // //\bug Dynamic maps must be updated!
1447 // nodes.clear();edges.clear();
1448 // first_node=first_free_node=first_free_edge=-1;
1452 template <typename T> class EdgeMap;
1457 friend class EdgeSet;
1458 template <typename T> friend class EdgeMap;
1461 friend class NodeIt;
1463 ///\bug It shoud be at least protected
1467 friend int EdgeSet::id(Edge e) const;
1469 Edge(int nn) {n=nn;}
1472 Edge (Invalid) { n=-1; }
1473 bool operator==(const Edge i) const {return n==i.n;}
1474 bool operator!=(const Edge i) const {return n!=i.n;}
1475 bool operator<(const Edge i) const {return n<i.n;}
1476 ///\bug This is a workaround until somebody tells me how to
1477 ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
1478 int &idref() {return n;}
1479 const int &idref() const {return n;}
1482 class EdgeIt : public Edge {
1483 friend class EdgeSet;
1484 template <typename T> friend class EdgeMap;
1488 EdgeIt(const EdgeSet& G) : Edge() {
1489 // typename NodeGraphType::Node m;
1492 G.valid(m) && G.nodes[m].first_in == -1; G.next(m));
1493 //AJJAJ! This is a non sense!!!!!!!
1494 this->n = G.valid(m)?-1:G.nodes[m].first_in;
1496 EdgeIt (Invalid i) : Edge(i) { }
1497 EdgeIt() : Edge() { }
1498 ///\bug This is a workaround until somebody tells me how to
1499 ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
1500 int &idref() {return this->n;}
1503 class OutEdgeIt : public Edge {
1504 friend class EdgeSet;
1506 OutEdgeIt() : Edge() { }
1507 OutEdgeIt (Invalid i) : Edge(i) { }
1509 OutEdgeIt(const EdgeSet& G,const Node v) : Edge(G.nodes[v].first_out) { }
1512 class InEdgeIt : public Edge {
1513 friend class EdgeSet;
1515 InEdgeIt() : Edge() { }
1516 InEdgeIt (Invalid i) : Edge(i) { }
1517 InEdgeIt(const EdgeSet& G,Node v) :Edge(G.nodes[v].first_in) { }
1520 template <typename T> class NodeMap :
1521 public NodeGraphType::template NodeMap<T>
1523 //This is a must, the constructors need it.
1524 typedef typename NodeGraphType::template NodeMap<T> ParentNodeMap;
1526 NodeMap(const EdgeSet &_G) : ParentNodeMap(_G.G) { }
1527 NodeMap(const EdgeSet &_G,const T &t) : ParentNodeMap(_G.G,t) { }
1529 NodeMap(const typename NodeGraphType::template NodeMap<T> &m) :
1530 ParentNodeMap(m) { }
1532 ///\todo It can copy between different types.
1534 template<typename TT>
1535 NodeMap(const typename NodeGraphType::template NodeMap<TT> &m)
1536 : ParentNodeMap(m) { }
1540 template <typename T> class EdgeMap : public DynMapBase<Edge>
1544 ///\bug It should be at least protected
1546 std::vector<T> container;
1549 typedef T ValueType;
1550 typedef Edge KeyType;
1552 EdgeMap(const EdgeSet &_G) :
1553 DynMapBase<Edge>(_G), container(_G.maxEdgeId())
1555 //FIXME: What if there are empty Id's?
1556 //FIXME: Can I use 'this' in a constructor?
1557 G->dyn_edge_maps.push_back(this);
1559 EdgeMap(const EdgeSet &_G,const T &t) :
1560 DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
1562 G->dyn_edge_maps.push_back(this);
1564 EdgeMap(const EdgeMap<T> &m) :
1565 DynMapBase<Edge>(*m.G), container(m.container)
1567 G->dyn_edge_maps.push_back(this);
1570 ///\todo It can copy between different types.
1572 template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
1573 DynMapBase<Edge>(*m.G), container(m.container.size())
1575 G->dyn_edge_maps.push_back(this);
1576 typename std::vector<TT>::const_iterator i;
1577 for(typename std::vector<TT>::const_iterator i=m.container.begin();
1578 i!=m.container.end();
1580 container.push_back(*i);
1585 typename std::vector<DynMapBase<Edge>* >::iterator i;
1586 for(i=G->dyn_edge_maps.begin();
1587 i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
1588 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
1589 //A better way to do that: (Is this really important?)
1591 *i=G->dyn_edge_maps.back();
1592 G->dyn_edge_maps.pop_back();
1597 void add(const Edge k)
1599 if(k.n>=int(container.size())) container.resize(k.n+1);
1601 void erase(const Edge) { }
1603 ///\bug This doesn't work. Why?
1604 /// void set(Edge n, T a) { container[n.n]=a; }
1605 void set(Edge n, T a) { container[G->id(n)]=a; }
1606 //T get(Edge n) const { return container[n.n]; }
1607 typename std::vector<T>::reference
1608 ///\bug This doesn't work. Why?
1609 /// operator[](Edge n) { return container[n.n]; }
1610 operator[](Edge n) { return container[G->id(n)]; }
1611 typename std::vector<T>::const_reference
1612 ///\bug This doesn't work. Why?
1613 /// operator[](Edge n) const { return container[n.n]; }
1614 operator[](Edge n) const { return container[G->id(n)]; }
1616 ///\warning There is no safety check at all!
1617 ///Using operator = between maps attached to different graph may
1618 ///cause serious problem.
1619 ///\todo Is this really so?
1620 ///\todo It can copy between different types.
1621 const EdgeMap<T>& operator=(const EdgeMap<T> &m)
1623 container = m.container;
1627 template<typename TT> friend class EdgeMap;
1629 template<typename TT>
1630 const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
1632 std::copy(m.container.begin(), m.container.end(), container.begin());
1636 void update() {} //Useless for DynMaps
1637 void update(T a) {} //Useless for DynMaps
1642 template<typename GG>
1643 inline int EdgeSet<GG>::id(Node v) const { return G.id(v); }
1649 #endif //HUGO_LIST_GRAPH_H