.
17 int first_in,first_out;
18 NodeT() : first_in(-1), first_out(-1) {}
22 int head, tail, next_in, next_out;
23 //FIXME: is this necessary?
24 EdgeT() : next_in(-1), next_out(-1) {}
27 std::vector<NodeT> nodes;
29 std::vector<EdgeT> edges;
31 template <typename Key> class DynMapBase
36 virtual void add(const Key k) = NULL;
37 virtual void erase(const Key k) = NULL;
38 DynMapBase(const SmartGraph &_G) : G(&_G) {}
39 virtual ~DynMapBase() {}
40 friend class SmartGraph;
43 template <typename T> class DynEdgeMap;
44 template <typename T> class DynEdgeMap;
50 mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
51 mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
60 // class Node { int n; };
61 // class NodeIt : public Node { };
62 // class Edge { int n; };
63 // class EdgeIt : public Edge {};
64 // class OutEdgeIt : public Edge {};
65 // class InEdgeIt : public Edge {};
68 template <typename T> class NodeMap;
69 template <typename T> class EdgeMap;
73 /* default constructor */
75 SmartGraph() : nodes(), edges() { }
76 SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
80 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
81 i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
82 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
83 i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
86 int nodeNum() const { return nodes.size(); } //FIXME: What is this?
87 int edgeNum() const { return edges.size(); } //FIXME: What is this?
89 int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
90 int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
93 Node tail(Edge e) const { return edges[e.n].tail; }
94 Node head(Edge e) const { return edges[e.n].head; }
97 Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
98 Node aNode(InEdgeIt e) const { return edges[e.n].head; }
99 // //Node aNode(const SymEdge& e) const { return e.aNode(); }
102 Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
103 Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
104 // //Node bNode(const SymEdge& e) const { return e.bNode(); }
106 NodeIt& first(NodeIt& v) const {
107 v=NodeIt(*this); return v; }
108 EdgeIt& first(EdgeIt& e) const {
109 e=EdgeIt(*this); return e; }
110 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
111 e=OutEdgeIt(*this,v); return e; }
112 InEdgeIt& first(InEdgeIt& e, const Node v) const {
113 e=InEdgeIt(*this,v); return e; }
115 template< typename It >
116 It first() const { It e; first(e); return e; }
118 template< typename It >
119 It first(Node v) const { It e; first(e,v); return e; }
121 bool valid(Edge e) const { return e.n!=-1; }
122 bool valid(Node n) const { return n.n!=-1; }
124 void setInvalid(Edge &e) { e.n=-1; }
125 void setInvalid(Node &n) { n.n=-1; }
127 template <typename It> It getNext(It it) const
128 { It tmp(it); return next(tmp); }
130 NodeIt& next(NodeIt& it) const {
131 it.n=(it.n+2)%(nodes.size()+1)-1;
134 OutEdgeIt& next(OutEdgeIt& it) const
135 { it.n=edges[it.n].next_out; return it; }
136 InEdgeIt& next(InEdgeIt& it) const
137 { it.n=edges[it.n].next_in; return it; }
138 EdgeIt& next(EdgeIt& it) const { --it.n; return it; }
140 int id(Node v) const { return v.n; }
141 int id(Edge e) const { return e.n; }
144 Node n; n.n=nodes.size();
145 nodes.push_back(NodeT()); //FIXME: Hmmm...
147 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
148 i!=dyn_node_maps.end(); ++i) (**i).add(n.n);
153 Edge addEdge(Node u, Node v) {
154 Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
155 edges[e.n].tail=u.n; edges[e.n].head=v.n;
156 edges[e.n].next_out=nodes[u.n].first_out;
157 edges[e.n].next_in=nodes[v.n].first_in;
158 nodes[u.n].first_out=nodes[v.n].first_in=e.n;
160 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
161 i!=dyn_edge_maps.end(); ++i) (**i).add(e);
166 void clear() {nodes.clear();edges.clear();}
169 friend class SmartGraph;
170 template <typename T> friend class NodeMap;
171 template <typename T> friend class DynNodeMap;
174 friend class OutEdgeIt;
175 friend class InEdgeIt;
176 friend class SymEdge;
180 friend int SmartGraph::id(Node v) const;
184 Node (Invalid i) { n=-1; }
185 bool operator==(const Node i) const {return n==i.n;}
186 bool operator!=(const Node i) const {return n!=i.n;}
187 bool operator<(const Node i) const {return n<i.n;}
190 class NodeIt : public Node {
191 friend class SmartGraph;
193 NodeIt(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { }
194 NodeIt() : Node() { }
198 friend class SmartGraph;
199 template <typename T> friend class EdgeMap;
200 template <typename T> friend class DynEdgeMap;
206 friend int SmartGraph::id(Edge e) const;
211 Edge (Invalid) { n=-1; }
212 bool operator==(const Edge i) const {return n==i.n;}
213 bool operator!=(const Edge i) const {return n!=i.n;}
214 bool operator<(const Edge i) const {return n<i.n;}
217 class EdgeIt : public Edge {
218 friend class SmartGraph;
220 EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { }
221 EdgeIt (Invalid i) : Edge(i) { }
222 EdgeIt() : Edge() { }
225 class OutEdgeIt : public Edge {
226 friend class SmartGraph;
228 OutEdgeIt() : Edge() { }
229 OutEdgeIt (Invalid i) : Edge(i) { }
231 OutEdgeIt(const SmartGraph& G,const Node v)
232 : Edge(G.nodes[v.n].first_out) {}
235 class InEdgeIt : public Edge {
236 friend class SmartGraph;
238 InEdgeIt() : Edge() { }
239 InEdgeIt (Invalid i) : Edge(i) { }
240 InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
245 template <typename T>
248 std::vector<T> container;
251 typedef Node KeyType;
252 NodeMap(const SmartGraph& _G) : G(_G), container(G.maxNodeId()) { }
253 NodeMap(const SmartGraph& _G, T a) :
254 G(_G), container(G.maxNodeId(), a) { }
255 void set(Node n, T a) { container[n.n]=a; }
256 T get(Node n) const { return container[n.n]; }
257 T& operator[](Node n) { return container[n.n]; }
258 const T& operator[](Node n) const { return container[n.n]; }
259 void update() { container.resize(G.maxNodeId()); }
260 void update(T a) { container.resize(G.maxNodeId(), a); }
263 template <typename T>
266 std::vector<T> container;
269 typedef Edge KeyType;
270 EdgeMap(const SmartGraph& _G) : G(_G), container(G.maxEdgeId()) { }
271 EdgeMap(const SmartGraph& _G, T a) :
272 G(_G), container(G.maxEdgeId(), a) { }
273 void set(Edge e, T a) { container[e.n]=a; }
274 T get(Edge e) const { return container[e.n]; }
275 T& operator[](Edge e) { return container[e.n]; }
276 const T& operator[](Edge e) const { return container[e.n]; }
277 void update() { container.resize(G.maxEdgeId()); }
278 void update(T a) { container.resize(G.maxEdgeId(), a); }
281 template <typename T> class DynNodeMap : public DynMapBase<Node>
283 std::vector<T> container;
287 typedef Node KeyType;
289 DynNodeMap(const SmartGraph &_G) :
290 DynMapBase<Node>(_G), container(_G.maxNodeId())
292 //FIXME: What if there are empty Id's?
293 //FIXME: Can I use 'this' in a constructor?
294 G->dyn_node_maps.push_back(this);
299 std::vector<DynMapBase<Node>* >::iterator i;
300 for(i=G->dyn_node_maps.begin();
301 i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
302 //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
303 //A better way to do that: (Is this really important?)
305 *i=G->dyn_node_maps.back();
306 G->dyn_node_maps.pop_back();
311 void add(const Node k)
313 if(k.n>=container.size()) container.resize(k.n+1);
316 // void erase(const Node k)
318 // //FIXME: Please implement me.
320 // void erase(const Edge k)
322 // //FIXME: Please implement me.
325 void set(Node n, T a) { container[n.n]=a; }
326 T get(Node n) const { return container[n.n]; }
327 T& operator[](Node n) { return container[n.n]; }
328 const T& operator[](Node n) const { return container[n.n]; }
330 void update() {} //Useless for DynMaps
331 void update(T a) {} //Useless for DynMaps
334 template <typename T> class DynEdgeMap : public DynMapBase<Edge>
336 std::vector<T> container;
340 typedef Edge KeyType;
342 DynEdgeMap(const SmartGraph &_G) :
343 DynMapBase<Edge>(_G), container(_G.maxEdgeId())
345 //FIXME: What if there are empty Id's?
346 //FIXME: Can I use 'this' in a constructor?
347 G->dyn_edge_maps.push_back(this);
352 std::vector<DynMapBase<Edge>* >::iterator i;
353 for(i=G->dyn_edge_maps.begin();
354 i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
355 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
356 //A better way to do that: (Is this really important?)
358 *i=G->dyn_edge_maps.back();
359 G->dyn_edge_maps.pop_back();
364 void add(const Edge k)
366 if(k.n>=int(container.size())) container.resize(k.n+1);
368 void erase(const Edge k)
370 //FIXME: Please implement me.
373 void set(Edge n, T a) { container[n.n]=a; }
374 T get(Edge n) const { return container[n.n]; }
375 T& operator[](Edge n) { return container[n.n]; }
376 const T& operator[](Edge n) const { return container[n.n]; }
378 void update() {} //Useless for DynMaps
379 void update(T a) {} //Useless for DynMaps
388 #endif //SMART_GRAPH_H