EdgeSet is more or less working.
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 EdgeMap;
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;
243 Edge (Invalid) { n=-1; }
244 bool operator==(const Edge i) const {return n==i.n;}
245 bool operator!=(const Edge i) const {return n!=i.n;}
246 bool operator<(const Edge i) const {return n<i.n;}
247 ///\bug This is a workaround until somebody tells me how to
248 ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
249 int &idref() {return n;}
250 const int &idref() const {return n;}
253 class EdgeIt : public Edge {
254 friend class SmartGraph;
256 EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { }
257 EdgeIt (Invalid i) : Edge(i) { }
258 EdgeIt() : Edge() { }
259 ///\bug This is a workaround until somebody tells me how to
260 ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
261 int &idref() {return n;}
264 class OutEdgeIt : public Edge {
265 friend class SmartGraph;
267 OutEdgeIt() : Edge() { }
268 OutEdgeIt (Invalid i) : Edge(i) { }
270 OutEdgeIt(const SmartGraph& G,const Node v)
271 : Edge(G.nodes[v.n].first_out) {}
274 class InEdgeIt : public Edge {
275 friend class SmartGraph;
277 InEdgeIt() : Edge() { }
278 InEdgeIt (Invalid i) : Edge(i) { }
279 InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
282 template <typename T> class NodeMap : public DynMapBase<Node>
284 std::vector<T> container;
288 typedef Node KeyType;
290 NodeMap(const SmartGraph &_G) :
291 DynMapBase<Node>(_G), container(_G.maxNodeId())
293 G->dyn_node_maps.push_back(this);
295 NodeMap(const SmartGraph &_G,const T &t) :
296 DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
298 G->dyn_node_maps.push_back(this);
301 NodeMap(const NodeMap<T> &m) :
302 DynMapBase<Node>(*m.G), container(m.container)
304 G->dyn_node_maps.push_back(this);
307 template<typename TT> friend class NodeMap;
309 ///\todo It can copy between different types.
311 template<typename TT> NodeMap(const NodeMap<TT> &m) :
312 DynMapBase<Node>(*m.G)
314 G->dyn_node_maps.push_back(this);
315 typename std::vector<TT>::const_iterator i;
316 for(typename std::vector<TT>::const_iterator i=m.container.begin();
317 i!=m.container.end();
319 container.push_back(*i);
324 std::vector<DynMapBase<Node>* >::iterator i;
325 for(i=G->dyn_node_maps.begin();
326 i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
327 //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
328 //A better way to do that: (Is this really important?)
330 *i=G->dyn_node_maps.back();
331 G->dyn_node_maps.pop_back();
336 void add(const Node k)
338 if(k.n>=int(container.size())) container.resize(k.n+1);
341 void erase(const Node) { }
343 void set(Node n, T a) { container[n.n]=a; }
344 //'T& operator[](Node n)' would be wrong here
345 typename std::vector<T>::reference
346 operator[](Node n) { return container[n.n]; }
347 //'const T& operator[](Node n)' would be wrong here
348 typename std::vector<T>::const_reference
349 operator[](Node n) const { return container[n.n]; }
351 ///\warning There is no safety check at all!
352 ///Using operator = between maps attached to different graph may
353 ///cause serious problem.
354 ///\todo Is this really so?
355 ///\todo It can copy between different types.
356 const NodeMap<T>& operator=(const NodeMap<T> &m)
358 container = m.container;
361 template<typename TT>
362 const NodeMap<T>& operator=(const NodeMap<TT> &m)
364 std::copy(m.container.begin(), m.container.end(), container.begin());
368 void update() {} //Useless for Dynamic Maps
369 void update(T a) {} //Useless for Dynamic Maps
372 template <typename T> class EdgeMap : public DynMapBase<Edge>
374 std::vector<T> container;
378 typedef Edge KeyType;
380 EdgeMap(const SmartGraph &_G) :
381 DynMapBase<Edge>(_G), container(_G.maxEdgeId())
383 //FIXME: What if there are empty Id's?
384 //FIXME: Can I use 'this' in a constructor?
385 G->dyn_edge_maps.push_back(this);
387 EdgeMap(const SmartGraph &_G,const T &t) :
388 DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
390 G->dyn_edge_maps.push_back(this);
392 EdgeMap(const EdgeMap<T> &m) :
393 DynMapBase<Edge>(*m.G), container(m.container)
395 G->dyn_edge_maps.push_back(this);
398 template<typename TT> friend class EdgeMap;
400 ///\todo It can copy between different types.
402 template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
403 DynMapBase<Edge>(*m.G)
405 G->dyn_edge_maps.push_back(this);
406 typename std::vector<TT>::const_iterator i;
407 for(typename std::vector<TT>::const_iterator i=m.container.begin();
408 i!=m.container.end();
410 container.push_back(*i);
415 std::vector<DynMapBase<Edge>* >::iterator i;
416 for(i=G->dyn_edge_maps.begin();
417 i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
418 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
419 //A better way to do that: (Is this really important?)
421 *i=G->dyn_edge_maps.back();
422 G->dyn_edge_maps.pop_back();
427 void add(const Edge k)
429 if(k.n>=int(container.size())) container.resize(k.n+1);
431 void erase(const Edge) { }
433 void set(Edge n, T a) { container[n.n]=a; }
434 //T get(Edge n) const { return container[n.n]; }
435 typename std::vector<T>::reference
436 operator[](Edge n) { return container[n.n]; }
437 typename std::vector<T>::const_reference
438 operator[](Edge n) const { return container[n.n]; }
440 ///\warning There is no safety check at all!
441 ///Using operator = between maps attached to different graph may
442 ///cause serious problem.
443 ///\todo Is this really so?
444 ///\todo It can copy between different types.
445 const EdgeMap<T>& operator=(const EdgeMap<T> &m)
447 container = m.container;
450 template<typename TT>
451 const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
453 std::copy(m.container.begin(), m.container.end(), container.begin());
457 void update() {} //Useless for DynMaps
458 void update(T a) {} //Useless for DynMaps
463 ///Graph for bidirectional edges.
465 ///The purpose of this graph structure is to handle graphs
466 ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
467 ///of oppositely directed edges.
468 ///There is a new edge map type called
469 ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"
470 ///that complements this
472 ///storing shared values for the edge pairs. The usual
473 ///\ref GraphSkeleton::EdgeMap "EdgeMap"
477 ///The oppositely directed edge can also be obtained easily
478 ///using \ref opposite.
479 ///\warning It shares the similarity with \ref SmartGraph that
480 ///it is not possible to delete edges or nodes from the graph.
481 //\sa \ref SmartGraph.
483 class SymSmartGraph : public SmartGraph
486 template<typename T> class SymEdgeMap;
487 template<typename T> friend class SymEdgeMap;
489 SymSmartGraph() : SmartGraph() { }
490 SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
491 ///Adds a pair of oppositely directed edges to the graph.
492 Edge addEdge(Node u, Node v)
494 Edge e = SmartGraph::addEdge(u,v);
495 SmartGraph::addEdge(v,u);
499 ///The oppositely directed edge.
501 ///Returns the oppositely directed
502 ///pair of the edge \c e.
503 Edge opposite(Edge e) const
506 f.idref() = e.idref() - 2*(e.idref()%2) + 1;
510 ///Common data storage for the edge pairs.
512 ///This map makes it possible to store data shared by the oppositely
513 ///directed pairs of edges.
514 template <typename T> class SymEdgeMap : public DynMapBase<Edge>
516 std::vector<T> container;
520 typedef Edge KeyType;
522 SymEdgeMap(const SymSmartGraph &_G) :
523 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
525 static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.push_back(this);
527 SymEdgeMap(const SymSmartGraph &_G,const T &t) :
528 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
530 G->dyn_edge_maps.push_back(this);
533 SymEdgeMap(const SymEdgeMap<T> &m) :
534 DynMapBase<SymEdge>(*m.G), container(m.container)
536 G->dyn_node_maps.push_back(this);
539 // template<typename TT> friend class SymEdgeMap;
541 ///\todo It can copy between different types.
544 template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :
545 DynMapBase<SymEdge>(*m.G)
547 G->dyn_node_maps.push_back(this);
548 typename std::vector<TT>::const_iterator i;
549 for(typename std::vector<TT>::const_iterator i=m.container.begin();
550 i!=m.container.end();
552 container.push_back(*i);
558 std::vector<DynMapBase<Edge>* >::iterator i;
559 for(i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.begin();
560 i!=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.end()
562 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
563 //A better way to do that: (Is this really important?)
565 *i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.back();
566 static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.pop_back();
571 void add(const Edge k)
573 if(!k.idref()%2&&k.idref()/2>=int(container.size()))
574 container.resize(k.idref()/2+1);
576 void erase(const Edge k) { }
578 void set(Edge n, T a) { container[n.idref()/2]=a; }
579 //T get(Edge n) const { return container[n.idref()/2]; }
580 typename std::vector<T>::reference
581 operator[](Edge n) { return container[n.idref()/2]; }
582 typename std::vector<T>::const_reference
583 operator[](Edge n) const { return container[n.idref()/2]; }
585 ///\warning There is no safety check at all!
586 ///Using operator = between maps attached to different graph may
587 ///cause serious problem.
588 ///\todo Is this really so?
589 ///\todo It can copy between different types.
590 const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
592 container = m.container;
595 template<typename TT>
596 const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
598 std::copy(m.container.begin(), m.container.end(), container.begin());
602 void update() {} //Useless for DynMaps
603 void update(T a) {} //Useless for DynMaps
616 #endif //SMART_GRAPH_H