Dynamic maps became the defaults.
Maps got copy constructors and operator=. Also work between different types.
SymSmartGraph added
smart_graph_demo.cc was extended.
3 #ifndef HUGO_SMART_GRAPH_H
4 #define HUGO_SMART_GRAPH_H
15 // template<typename T> class SymSmartGraph::SymEdgeMap;
21 int first_in,first_out;
22 NodeT() : first_in(-1), first_out(-1) {}
26 int head, tail, next_in, next_out;
27 //FIXME: is this necessary?
28 EdgeT() : next_in(-1), next_out(-1) {}
31 std::vector<NodeT> nodes;
33 std::vector<EdgeT> edges;
37 template <typename Key> class DynMapBase
42 virtual void add(const Key k) = NULL;
43 virtual void erase(const Key k) = NULL;
44 DynMapBase(const SmartGraph &_G) : G(&_G) {}
45 virtual ~DynMapBase() {}
46 friend class SmartGraph;
50 template <typename T> class EdgeMap;
51 template <typename T> class EdgeMap;
59 ///\bug It must be public because of SymEdgeMap.
61 mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
62 ///\bug It must be public because of SymEdgeMap.
64 mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
73 // class Node { int n; };
74 // class NodeIt : public Node { };
75 // class Edge { int n; };
76 // class EdgeIt : public Edge {};
77 // class OutEdgeIt : public Edge {};
78 // class InEdgeIt : public Edge {};
81 template <typename T> class NodeMap;
82 template <typename T> class EdgeMap;
86 /* default constructor */
88 SmartGraph() : nodes(), edges() { }
89 SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
93 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
94 i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
95 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
96 i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
99 int nodeNum() const { return nodes.size(); } //FIXME: What is this?
100 int edgeNum() const { return edges.size(); } //FIXME: What is this?
102 int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
103 int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
106 Node tail(Edge e) const { return edges[e.n].tail; }
107 Node head(Edge e) const { return edges[e.n].head; }
110 Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
111 Node aNode(InEdgeIt e) const { return edges[e.n].head; }
112 // //Node aNode(const SymEdge& e) const { return e.aNode(); }
115 Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
116 Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
117 // //Node bNode(const SymEdge& e) const { return e.bNode(); }
119 NodeIt& first(NodeIt& v) const {
120 v=NodeIt(*this); return v; }
121 EdgeIt& first(EdgeIt& e) const {
122 e=EdgeIt(*this); return e; }
123 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
124 e=OutEdgeIt(*this,v); return e; }
125 InEdgeIt& first(InEdgeIt& e, const Node v) const {
126 e=InEdgeIt(*this,v); return e; }
128 template< typename It >
129 It first() const { It e; first(e); return e; }
131 template< typename It >
132 It first(Node v) const { It e; first(e,v); return e; }
134 bool valid(Edge e) const { return e.n!=-1; }
135 bool valid(Node n) const { return n.n!=-1; }
137 void setInvalid(Edge &e) { e.n=-1; }
138 void setInvalid(Node &n) { n.n=-1; }
140 template <typename It> It getNext(It it) const
141 { It tmp(it); return next(tmp); }
143 NodeIt& next(NodeIt& it) const {
144 it.n=(it.n+2)%(nodes.size()+1)-1;
147 OutEdgeIt& next(OutEdgeIt& it) const
148 { it.n=edges[it.n].next_out; return it; }
149 InEdgeIt& next(InEdgeIt& it) const
150 { it.n=edges[it.n].next_in; return it; }
151 EdgeIt& next(EdgeIt& it) const { --it.n; return it; }
153 int id(Node v) const { return v.n; }
154 int id(Edge e) const { return e.n; }
157 Node n; n.n=nodes.size();
158 nodes.push_back(NodeT()); //FIXME: Hmmm...
160 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
161 i!=dyn_node_maps.end(); ++i) (**i).add(n.n);
166 Edge addEdge(Node u, Node v) {
167 Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
168 edges[e.n].tail=u.n; edges[e.n].head=v.n;
169 edges[e.n].next_out=nodes[u.n].first_out;
170 edges[e.n].next_in=nodes[v.n].first_in;
171 nodes[u.n].first_out=nodes[v.n].first_in=e.n;
173 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
174 i!=dyn_edge_maps.end(); ++i) (**i).add(e);
179 void clear() {nodes.clear();edges.clear();}
182 friend class SmartGraph;
183 template <typename T> friend class NodeMap;
186 friend class OutEdgeIt;
187 friend class InEdgeIt;
188 friend class SymEdge;
192 friend int SmartGraph::id(Node v) const;
196 Node (Invalid i) { n=-1; }
197 bool operator==(const Node i) const {return n==i.n;}
198 bool operator!=(const Node i) const {return n!=i.n;}
199 bool operator<(const Node i) const {return n<i.n;}
202 class NodeIt : public Node {
203 friend class SmartGraph;
205 NodeIt(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { }
206 NodeIt() : Node() { }
210 friend class SmartGraph;
211 template <typename T> friend class EdgeMap;
213 //template <typename T> friend class SymSmartGraph::SymEdgeMap;
214 //friend Edge SymSmartGraph::opposite(Edge) const;
220 friend int SmartGraph::id(Edge e) const;
225 Edge (Invalid) { n=-1; }
226 bool operator==(const Edge i) const {return n==i.n;}
227 bool operator!=(const Edge i) const {return n!=i.n;}
228 bool operator<(const Edge i) const {return n<i.n;}
229 ///\bug This is a workaround until somebody tells me how to
230 ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
231 int &idref() {return n;}
232 const int &idref() const {return n;}
235 class EdgeIt : public Edge {
236 friend class SmartGraph;
238 EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { }
239 EdgeIt (Invalid i) : Edge(i) { }
240 EdgeIt() : Edge() { }
241 ///\bug This is a workaround until somebody tells me how to
242 ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
243 int &idref() {return n;}
246 class OutEdgeIt : public Edge {
247 friend class SmartGraph;
249 OutEdgeIt() : Edge() { }
250 OutEdgeIt (Invalid i) : Edge(i) { }
252 OutEdgeIt(const SmartGraph& G,const Node v)
253 : Edge(G.nodes[v.n].first_out) {}
256 class InEdgeIt : public Edge {
257 friend class SmartGraph;
259 InEdgeIt() : Edge() { }
260 InEdgeIt (Invalid i) : Edge(i) { }
261 InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
266 // // Static Maps are not necessary.
267 // template <typename T>
269 // const SmartGraph& G;
270 // std::vector<T> container;
272 // typedef T ValueType;
273 // typedef Node KeyType;
274 // NodeMap(const SmartGraph& _G) : G(_G), container(G.maxNodeId()) { }
275 // NodeMap(const SmartGraph& _G, T a) :
276 // G(_G), container(G.maxNodeId(), a) { }
277 // void set(Node n, T a) { container[n.n]=a; }
278 // T get(Node n) const { return container[n.n]; }
279 // T& operator[](Node n) { return container[n.n]; }
280 // const T& operator[](Node n) const { return container[n.n]; }
281 // void update() { container.resize(G.maxNodeId()); }
282 // void update(T a) { container.resize(G.maxNodeId(), a); }
285 // template <typename T>
287 // const SmartGraph& G;
288 // std::vector<T> container;
290 // typedef T ValueType;
291 // typedef Edge KeyType;
292 // EdgeMap(const SmartGraph& _G) : G(_G), container(G.maxEdgeId()) { }
293 // EdgeMap(const SmartGraph& _G, T a) :
294 // G(_G), container(G.maxEdgeId(), a) { }
295 // void set(Edge e, T a) { container[e.n]=a; }
296 // T get(Edge e) const { return container[e.n]; }
297 // T& operator[](Edge e) { return container[e.n]; }
298 // const T& operator[](Edge e) const { return container[e.n]; }
299 // void update() { container.resize(G.maxEdgeId()); }
300 // void update(T a) { container.resize(G.maxEdgeId(), a); }
303 template <typename T> class NodeMap : public DynMapBase<Node>
305 std::vector<T> container;
309 typedef Node KeyType;
311 NodeMap(const SmartGraph &_G) :
312 DynMapBase<Node>(_G), container(_G.maxNodeId())
314 G->dyn_node_maps.push_back(this);
316 NodeMap(const SmartGraph &_G,const T &t) :
317 DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
319 G->dyn_node_maps.push_back(this);
322 NodeMap(const NodeMap<T> &m) :
323 DynMapBase<Node>(*m.G), container(m.container)
325 G->dyn_node_maps.push_back(this);
328 template<typename TT> friend class NodeMap;
330 ///\todo It can copy between different types.
332 template<typename TT> NodeMap(const NodeMap<TT> &m) :
333 DynMapBase<Node>(*m.G)
335 G->dyn_node_maps.push_back(this);
336 typename std::vector<TT>::const_iterator i;
337 for(typename std::vector<TT>::const_iterator i=m.container.begin();
338 i!=m.container.end();
340 container.push_back(*i);
345 std::vector<DynMapBase<Node>* >::iterator i;
346 for(i=G->dyn_node_maps.begin();
347 i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
348 //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
349 //A better way to do that: (Is this really important?)
351 *i=G->dyn_node_maps.back();
352 G->dyn_node_maps.pop_back();
357 void add(const Node k)
359 if(k.n>=int(container.size())) container.resize(k.n+1);
362 void erase(const Node k) { }
364 void set(Node n, T a) { container[n.n]=a; }
365 T get(Node n) const { return container[n.n]; }
366 T& operator[](Node n) { return container[n.n]; }
367 const T& operator[](Node n) const { return container[n.n]; }
369 ///\warning There is no safety check at all!
370 ///Using operator = between maps attached to different graph may
371 ///cause serious problem.
372 ///\todo Is this really so?
373 ///\todo It can copy between different types.
374 const NodeMap<T>& operator=(const NodeMap<T> &m)
376 container = m.container;
379 template<typename TT>
380 const NodeMap<T>& operator=(const NodeMap<TT> &m)
382 copy(m.container.begin(), m.container.end(), container.begin());
386 void update() {} //Useless for DynMaps
387 void update(T a) {} //Useless for DynMaps
390 template <typename T> class EdgeMap : public DynMapBase<Edge>
392 std::vector<T> container;
396 typedef Edge KeyType;
398 EdgeMap(const SmartGraph &_G) :
399 DynMapBase<Edge>(_G), container(_G.maxEdgeId())
401 //FIXME: What if there are empty Id's?
402 //FIXME: Can I use 'this' in a constructor?
403 G->dyn_edge_maps.push_back(this);
405 EdgeMap(const SmartGraph &_G,const T &t) :
406 DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
408 G->dyn_edge_maps.push_back(this);
410 EdgeMap(const EdgeMap<T> &m) :
411 DynMapBase<Edge>(*m.G), container(m.container)
413 G->dyn_node_maps.push_back(this);
416 template<typename TT> friend class EdgeMap;
418 ///\todo It can copy between different types.
420 template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
421 DynMapBase<Edge>(*m.G)
423 G->dyn_node_maps.push_back(this);
424 typename std::vector<TT>::const_iterator i;
425 for(typename std::vector<TT>::const_iterator i=m.container.begin();
426 i!=m.container.end();
428 container.push_back(*i);
433 std::vector<DynMapBase<Edge>* >::iterator i;
434 for(i=G->dyn_edge_maps.begin();
435 i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
436 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
437 //A better way to do that: (Is this really important?)
439 *i=G->dyn_edge_maps.back();
440 G->dyn_edge_maps.pop_back();
445 void add(const Edge k)
447 if(k.n>=int(container.size())) container.resize(k.n+1);
449 void erase(const Edge k) { }
451 void set(Edge n, T a) { container[n.n]=a; }
452 T get(Edge n) const { return container[n.n]; }
453 T& operator[](Edge n) { return container[n.n]; }
454 const T& operator[](Edge n) const { return container[n.n]; }
456 ///\warning There is no safety check at all!
457 ///Using operator = between maps attached to different graph may
458 ///cause serious problem.
459 ///\todo Is this really so?
460 ///\todo It can copy between different types.
461 const EdgeMap<T>& operator=(const EdgeMap<T> &m)
463 container = m.container;
466 template<typename TT>
467 const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
469 copy(m.container.begin(), m.container.end(), container.begin());
473 void update() {} //Useless for DynMaps
474 void update(T a) {} //Useless for DynMaps
479 ///Graph for bidirectional edges.
481 ///The purpose of this graph structure is to handle graphs
482 ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
483 ///of oppositely directed edges. You can define edge maps which
484 ///stores a common value for the edge pairs. The usual edge maps can be used
487 ///The oppositely directed edge can also be obtained easily.
489 class SymSmartGraph : public SmartGraph
492 SymSmartGraph() : SmartGraph() { }
493 SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
494 Edge addEdge(Node u, Node v)
496 Edge e = SmartGraph::addEdge(u,v);
497 SmartGraph::addEdge(v,u);
501 Edge opposite(Edge e) const
504 f.idref() = e.idref() - 2*(e.idref()%2) + 1;
508 template <typename T> class SymEdgeMap : public DynMapBase<Edge>
510 std::vector<T> container;
514 typedef Edge KeyType;
516 SymEdgeMap(const SmartGraph &_G) :
517 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
519 G->dyn_edge_maps.push_back(this);
521 SymEdgeMap(const SmartGraph &_G,const T &t) :
522 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
524 G->dyn_edge_maps.push_back(this);
527 SymEdgeMap(const SymEdgeMap<T> &m) :
528 DynMapBase<SymEdge>(*m.G), container(m.container)
530 G->dyn_node_maps.push_back(this);
533 // template<typename TT> friend class SymEdgeMap;
535 ///\todo It can copy between different types.
538 template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :
539 DynMapBase<SymEdge>(*m.G)
541 G->dyn_node_maps.push_back(this);
542 typename std::vector<TT>::const_iterator i;
543 for(typename std::vector<TT>::const_iterator i=m.container.begin();
544 i!=m.container.end();
546 container.push_back(*i);
552 std::vector<DynMapBase<Edge>* >::iterator i;
553 for(i=G->dyn_edge_maps.begin();
554 i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
555 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
556 //A better way to do that: (Is this really important?)
558 *i=G->dyn_edge_maps.back();
559 G->dyn_edge_maps.pop_back();
564 void add(const Edge k)
566 if(!k.idref()%2&&k.idref()/2>=int(container.size()))
567 container.resize(k.idref()/2+1);
569 void erase(const Edge k) { }
571 void set(Edge n, T a) { container[n.idref()/2]=a; }
572 T get(Edge n) const { return container[n.idref()/2]; }
573 T& operator[](Edge n) { return container[n.idref()/2]; }
574 const T& operator[](Edge n) const { return container[n.idref()/2]; }
576 ///\warning There is no safety check at all!
577 ///Using operator = between maps attached to different graph may
578 ///cause serious problem.
579 ///\todo Is this really so?
580 ///\todo It can copy between different types.
581 const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
583 container = m.container;
586 template<typename TT>
587 const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
589 copy(m.container.begin(), m.container.end(), container.begin());
593 void update() {} //Useless for DynMaps
594 void update(T a) {} //Useless for DynMaps
606 #endif //SMART_GRAPH_H