Temporal change: public Edge constructor with given ID.
3 #ifndef HUGO_SMART_GRAPH_H
4 #define HUGO_SMART_GRAPH_H
8 ///\brief SmartGraph and SymSmartGraph classes.
13 #include <hugo/invalid.h>
17 /// \addtogroup graphs
21 ///A smart graph class.
23 ///This is a simple and fast graph implementation.
24 ///It is also quite memory efficient, but at the price
25 ///that <b> it does not support node and edge deletion</b>.
26 ///It conforms to the graph interface documented under
27 ///the description of \ref GraphSkeleton.
28 ///\sa \ref GraphSkeleton.
30 ///\todo Some member functions could be \c static.
31 ///\author Alpar Juttner
36 int first_in,first_out;
37 NodeT() : first_in(-1), first_out(-1) {}
41 int head, tail, next_in, next_out;
42 //FIXME: is this necessary?
43 EdgeT() : next_in(-1), next_out(-1) {}
46 std::vector<NodeT> nodes;
48 std::vector<EdgeT> edges;
52 template <typename Key> class DynMapBase
57 virtual void add(const Key k) = 0;
58 virtual void erase(const Key k) = 0;
59 DynMapBase(const SmartGraph &_G) : G(&_G) {}
60 virtual ~DynMapBase() {}
61 friend class SmartGraph;
65 template <typename T> class EdgeMap;
66 template <typename T> class NodeMap;
74 ///\bug It must be public because of SymEdgeMap.
76 mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
77 ///\bug It must be public because of SymEdgeMap.
79 mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
89 template <typename T> class NodeMap;
90 template <typename T> class EdgeMap;
94 SmartGraph() : nodes(), edges() { }
95 SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
99 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
100 i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
101 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
102 i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
105 int nodeNum() const { return nodes.size(); } //FIXME: What is this?
106 int edgeNum() const { return edges.size(); } //FIXME: What is this?
108 ///\bug This function does something different than
109 ///its name would suggests...
110 int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
111 ///\bug This function does something different than
112 ///its name would suggests...
113 int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
115 Node tail(Edge e) const { return edges[e.n].tail; }
116 Node head(Edge e) const { return edges[e.n].head; }
118 Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
119 Node aNode(InEdgeIt e) const { return edges[e.n].head; }
121 Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
122 Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
124 NodeIt& first(NodeIt& v) const {
125 v=NodeIt(*this); return v; }
126 EdgeIt& first(EdgeIt& e) const {
127 e=EdgeIt(*this); return e; }
128 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
129 e=OutEdgeIt(*this,v); return e; }
130 InEdgeIt& first(InEdgeIt& e, const Node v) const {
131 e=InEdgeIt(*this,v); return e; }
133 // template< typename It >
134 // It first() const { It e; first(e); return e; }
136 // template< typename It >
137 // It first(Node v) const { It e; first(e,v); return e; }
139 bool valid(Edge e) const { return e.n!=-1; }
140 bool valid(Node n) const { return n.n!=-1; }
147 void setInvalid(Edge &e) { e.n=-1; }
153 void setInvalid(Node &n) { n.n=-1; }
155 template <typename It> It getNext(It it) const
156 { It tmp(it); return next(tmp); }
158 NodeIt& next(NodeIt& it) const {
159 it.n=(it.n+2)%(nodes.size()+1)-1;
162 OutEdgeIt& next(OutEdgeIt& it) const
163 { it.n=edges[it.n].next_out; return it; }
164 InEdgeIt& next(InEdgeIt& it) const
165 { it.n=edges[it.n].next_in; return it; }
166 EdgeIt& next(EdgeIt& it) const { --it.n; return it; }
168 int id(Node v) const { return v.n; }
169 int id(Edge e) const { return e.n; }
172 Node n; n.n=nodes.size();
173 nodes.push_back(NodeT()); //FIXME: Hmmm...
175 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
176 i!=dyn_node_maps.end(); ++i) (**i).add(n);
181 Edge addEdge(Node u, Node v) {
182 Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
183 edges[e.n].tail=u.n; edges[e.n].head=v.n;
184 edges[e.n].next_out=nodes[u.n].first_out;
185 edges[e.n].next_in=nodes[v.n].first_in;
186 nodes[u.n].first_out=nodes[v.n].first_in=e.n;
188 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
189 i!=dyn_edge_maps.end(); ++i) (**i).add(e);
194 void clear() {nodes.clear();edges.clear();}
197 friend class SmartGraph;
198 template <typename T> friend class NodeMap;
201 friend class OutEdgeIt;
202 friend class InEdgeIt;
203 friend class SymEdge;
207 friend int SmartGraph::id(Node v) const;
211 Node (Invalid) { n=-1; }
212 bool operator==(const Node i) const {return n==i.n;}
213 bool operator!=(const Node i) const {return n!=i.n;}
214 bool operator<(const Node i) const {return n<i.n;}
217 class NodeIt : public Node {
218 friend class SmartGraph;
220 NodeIt() : Node() { }
221 NodeIt(Invalid i) : Node(i) { }
222 NodeIt(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { }
223 ///\todo Undocumented conversion Node -\> NodeIt.
224 NodeIt(const SmartGraph& G, const Node &n) : Node(n) { }
228 friend class SmartGraph;
229 template <typename T> friend class EdgeMap;
231 //template <typename T> friend class SymSmartGraph::SymEdgeMap;
232 //friend Edge SymSmartGraph::opposite(Edge) const;
238 friend int SmartGraph::id(Edge e) const;
241 /// An Edge with id \c n.
243 /// \bug It should be
244 /// obtained by a member function of the Graph.
247 Edge (Invalid) { n=-1; }
248 bool operator==(const Edge i) const {return n==i.n;}
249 bool operator!=(const Edge i) const {return n!=i.n;}
250 bool operator<(const Edge i) const {return n<i.n;}
251 ///\bug This is a workaround until somebody tells me how to
252 ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
253 int &idref() {return n;}
254 const int &idref() const {return n;}
257 class EdgeIt : public Edge {
258 friend class SmartGraph;
260 EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { }
261 EdgeIt (Invalid i) : Edge(i) { }
262 EdgeIt() : Edge() { }
263 ///\bug This is a workaround until somebody tells me how to
264 ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
265 int &idref() {return n;}
268 class OutEdgeIt : public Edge {
269 friend class SmartGraph;
271 OutEdgeIt() : Edge() { }
272 OutEdgeIt (Invalid i) : Edge(i) { }
274 OutEdgeIt(const SmartGraph& G,const Node v)
275 : Edge(G.nodes[v.n].first_out) {}
278 class InEdgeIt : public Edge {
279 friend class SmartGraph;
281 InEdgeIt() : Edge() { }
282 InEdgeIt (Invalid i) : Edge(i) { }
283 InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
286 template <typename T> class NodeMap : public DynMapBase<Node>
288 std::vector<T> container;
292 typedef Node KeyType;
294 NodeMap(const SmartGraph &_G) :
295 DynMapBase<Node>(_G), container(_G.maxNodeId())
297 G->dyn_node_maps.push_back(this);
299 NodeMap(const SmartGraph &_G,const T &t) :
300 DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
302 G->dyn_node_maps.push_back(this);
305 NodeMap(const NodeMap<T> &m) :
306 DynMapBase<Node>(*m.G), container(m.container)
308 G->dyn_node_maps.push_back(this);
311 template<typename TT> friend class NodeMap;
313 ///\todo It can copy between different types.
314 ///\todo We could use 'copy'
315 template<typename TT> NodeMap(const NodeMap<TT> &m) :
316 DynMapBase<Node>(*m.G), container(m.container.size())
318 G->dyn_node_maps.push_back(this);
319 typename std::vector<TT>::const_iterator i;
320 for(typename std::vector<TT>::const_iterator i=m.container.begin();
321 i!=m.container.end();
323 container.push_back(*i);
328 std::vector<DynMapBase<Node>* >::iterator i;
329 for(i=G->dyn_node_maps.begin();
330 i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
331 //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
332 //A better way to do that: (Is this really important?)
334 *i=G->dyn_node_maps.back();
335 G->dyn_node_maps.pop_back();
340 void add(const Node k)
342 if(k.n>=int(container.size())) container.resize(k.n+1);
345 void erase(const Node) { }
347 void set(Node n, T a) { container[n.n]=a; }
348 //'T& operator[](Node n)' would be wrong here
349 typename std::vector<T>::reference
350 operator[](Node n) { return container[n.n]; }
351 //'const T& operator[](Node n)' would be wrong here
352 typename std::vector<T>::const_reference
353 operator[](Node n) const { return container[n.n]; }
355 ///\warning There is no safety check at all!
356 ///Using operator = between maps attached to different graph may
357 ///cause serious problem.
358 ///\todo Is this really so?
359 ///\todo It can copy between different types.
360 const NodeMap<T>& operator=(const NodeMap<T> &m)
362 container = m.container;
365 template<typename TT>
366 const NodeMap<T>& operator=(const NodeMap<TT> &m)
368 std::copy(m.container.begin(), m.container.end(), container.begin());
372 void update() {} //Useless for Dynamic Maps
373 void update(T a) {} //Useless for Dynamic Maps
376 template <typename T> class EdgeMap : public DynMapBase<Edge>
378 std::vector<T> container;
382 typedef Edge KeyType;
384 EdgeMap(const SmartGraph &_G) :
385 DynMapBase<Edge>(_G), container(_G.maxEdgeId())
387 //FIXME: What if there are empty Id's?
388 //FIXME: Can I use 'this' in a constructor?
389 G->dyn_edge_maps.push_back(this);
391 EdgeMap(const SmartGraph &_G,const T &t) :
392 DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
394 G->dyn_edge_maps.push_back(this);
396 EdgeMap(const EdgeMap<T> &m) :
397 DynMapBase<Edge>(*m.G), container(m.container)
399 G->dyn_edge_maps.push_back(this);
402 template<typename TT> friend class EdgeMap;
404 ///\todo It can copy between different types.
405 template<typename TT> EdgeMap(const EdgeMap<TT> &m)
406 : DynMapBase<Edge>(*m.G), container(m.container.size())
408 G->dyn_edge_maps.push_back(this);
409 typename std::vector<TT>::const_iterator i;
410 for(typename std::vector<TT>::const_iterator i=m.container.begin();
411 i!=m.container.end();
413 container.push_back(*i);
418 std::vector<DynMapBase<Edge>* >::iterator i;
419 for(i=G->dyn_edge_maps.begin();
420 i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
421 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
422 //A better way to do that: (Is this really important?)
424 *i=G->dyn_edge_maps.back();
425 G->dyn_edge_maps.pop_back();
430 void add(const Edge k)
432 if(k.n>=int(container.size())) container.resize(k.n+1);
434 void erase(const Edge) { }
436 void set(Edge n, T a) { container[n.n]=a; }
437 //T get(Edge n) const { return container[n.n]; }
438 typename std::vector<T>::reference
439 operator[](Edge n) { return container[n.n]; }
440 typename std::vector<T>::const_reference
441 operator[](Edge n) const { return container[n.n]; }
443 ///\warning There is no safety check at all!
444 ///Using operator = between maps attached to different graph may
445 ///cause serious problem.
446 ///\todo Is this really so?
447 ///\todo It can copy between different types.
448 const EdgeMap<T>& operator=(const EdgeMap<T> &m)
450 container = m.container;
453 template<typename TT>
454 const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
456 std::copy(m.container.begin(), m.container.end(), container.begin());
460 void update() {} //Useless for DynMaps
461 void update(T a) {} //Useless for DynMaps
466 ///Graph for bidirectional edges.
468 ///The purpose of this graph structure is to handle graphs
469 ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
470 ///of oppositely directed edges.
471 ///There is a new edge map type called
472 ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"
473 ///that complements this
475 ///storing shared values for the edge pairs. The usual
476 ///\ref GraphSkeleton::EdgeMap "EdgeMap"
480 ///The oppositely directed edge can also be obtained easily
481 ///using \ref opposite.
482 ///\warning It shares the similarity with \ref SmartGraph that
483 ///it is not possible to delete edges or nodes from the graph.
484 //\sa \ref SmartGraph.
486 class SymSmartGraph : public SmartGraph
489 template<typename T> class SymEdgeMap;
490 template<typename T> friend class SymEdgeMap;
492 SymSmartGraph() : SmartGraph() { }
493 SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
494 ///Adds a pair of oppositely directed edges to the graph.
495 Edge addEdge(Node u, Node v)
497 Edge e = SmartGraph::addEdge(u,v);
498 SmartGraph::addEdge(v,u);
502 ///The oppositely directed edge.
504 ///Returns the oppositely directed
505 ///pair of the edge \c e.
506 Edge opposite(Edge e) const
509 f.idref() = e.idref() - 2*(e.idref()%2) + 1;
513 ///Common data storage for the edge pairs.
515 ///This map makes it possible to store data shared by the oppositely
516 ///directed pairs of edges.
517 template <typename T> class SymEdgeMap : public DynMapBase<Edge>
519 std::vector<T> container;
523 typedef Edge KeyType;
525 SymEdgeMap(const SymSmartGraph &_G) :
526 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
528 static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.push_back(this);
530 SymEdgeMap(const SymSmartGraph &_G,const T &t) :
531 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
533 G->dyn_edge_maps.push_back(this);
536 SymEdgeMap(const SymEdgeMap<T> &m) :
537 DynMapBase<SymEdge>(*m.G), container(m.container)
539 G->dyn_node_maps.push_back(this);
542 // template<typename TT> friend class SymEdgeMap;
544 ///\todo It can copy between different types.
547 template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m)
548 : DynMapBase<SymEdge>(*m.G), container(m.container.size())
550 G->dyn_node_maps.push_back(this);
551 typename std::vector<TT>::const_iterator i;
552 for(typename std::vector<TT>::const_iterator i=m.container.begin();
553 i!=m.container.end();
555 container.push_back(*i);
561 std::vector<DynMapBase<Edge>* >::iterator i;
562 for(i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.begin();
563 i!=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.end()
565 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
566 //A better way to do that: (Is this really important?)
568 *i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.back();
569 static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.pop_back();
574 void add(const Edge k)
576 if(!k.idref()%2&&k.idref()/2>=int(container.size()))
577 container.resize(k.idref()/2+1);
579 void erase(const Edge k) { }
581 void set(Edge n, T a) { container[n.idref()/2]=a; }
582 //T get(Edge n) const { return container[n.idref()/2]; }
583 typename std::vector<T>::reference
584 operator[](Edge n) { return container[n.idref()/2]; }
585 typename std::vector<T>::const_reference
586 operator[](Edge n) const { return container[n.idref()/2]; }
588 ///\warning There is no safety check at all!
589 ///Using operator = between maps attached to different graph may
590 ///cause serious problem.
591 ///\todo Is this really so?
592 ///\todo It can copy between different types.
593 const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
595 container = m.container;
598 template<typename TT>
599 const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
601 std::copy(m.container.begin(), m.container.end(), container.begin());
605 void update() {} //Useless for DynMaps
606 void update(T a) {} //Useless for DynMaps
619 #endif //HUGO_SMART_GRAPH_H