119 int maxEdgeId() const { return edges.size(); } //FIXME: What is this? |
119 int maxEdgeId() const { return edges.size(); } //FIXME: What is this? |
120 |
120 |
121 Node tail(Edge e) const { return edges[e.n].tail; } |
121 Node tail(Edge e) const { return edges[e.n].tail; } |
122 Node head(Edge e) const { return edges[e.n].head; } |
122 Node head(Edge e) const { return edges[e.n].head; } |
123 |
123 |
124 Node aNode(OutEdgeIt e) const { return edges[e.n].tail; } |
|
125 Node aNode(InEdgeIt e) const { return edges[e.n].head; } |
|
126 |
|
127 Node bNode(OutEdgeIt e) const { return edges[e.n].head; } |
|
128 Node bNode(InEdgeIt e) const { return edges[e.n].tail; } |
|
129 |
|
130 NodeIt& first(NodeIt& v) const { |
124 NodeIt& first(NodeIt& v) const { |
131 v=NodeIt(*this); return v; } |
125 v=NodeIt(*this); return v; } |
132 EdgeIt& first(EdgeIt& e) const { |
126 EdgeIt& first(EdgeIt& e) const { |
133 e=EdgeIt(*this); return e; } |
127 e=EdgeIt(*this); return e; } |
134 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { |
128 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { |
135 e=OutEdgeIt(*this,v); return e; } |
129 e=OutEdgeIt(*this,v); return e; } |
136 InEdgeIt& first(InEdgeIt& e, const Node v) const { |
130 InEdgeIt& first(InEdgeIt& e, const Node v) const { |
137 e=InEdgeIt(*this,v); return e; } |
131 e=InEdgeIt(*this,v); return e; } |
138 |
132 |
139 // template< typename It > |
|
140 // It first() const { It e; first(e); return e; } |
|
141 |
|
142 // template< typename It > |
|
143 // It first(Node v) const { It e; first(e,v); return e; } |
|
144 |
|
145 static bool valid(Edge e) { return e.n!=-1; } |
|
146 static bool valid(Node n) { return n.n!=-1; } |
|
147 |
|
148 ///\deprecated Use |
|
149 ///\code |
|
150 /// e=INVALID; |
|
151 ///\endcode |
|
152 ///instead. |
|
153 static void setInvalid(Edge &e) { e.n=-1; } |
|
154 ///\deprecated Use |
|
155 ///\code |
|
156 /// e=INVALID; |
|
157 ///\endcode |
|
158 ///instead. |
|
159 static void setInvalid(Node &n) { n.n=-1; } |
|
160 |
|
161 template <typename It> It getNext(It it) const |
|
162 { It tmp(it); return next(tmp); } |
|
163 |
|
164 NodeIt& next(NodeIt& it) const { |
|
165 it.n=(it.n+2)%(nodes.size()+1)-1; |
|
166 return it; |
|
167 } |
|
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 { --it.n; return it; } |
|
173 |
|
174 static int id(Node v) { return v.n; } |
133 static int id(Node v) { return v.n; } |
175 static int id(Edge e) { return e.n; } |
134 static int id(Edge e) { return e.n; } |
176 |
135 |
177 Node addNode() { |
136 Node addNode() { |
178 Node n; n.n=nodes.size(); |
137 Node n; n.n=nodes.size(); |
195 i!=dyn_edge_maps.end(); ++i) (**i).add(e); |
154 i!=dyn_edge_maps.end(); ++i) (**i).add(e); |
196 |
155 |
197 return e; |
156 return e; |
198 } |
157 } |
199 |
158 |
|
159 /// Finds an edge between two nodes. |
|
160 |
|
161 /// Finds an edge from node \c u to node \c v. |
|
162 /// |
|
163 /// If \c prev is \ref INVALID (this is the default value), then |
|
164 /// It finds the first edge from \c u to \c v. Otherwise it looks for |
|
165 /// the next edge from \c u to \c v after \c prev. |
|
166 /// \return The found edge or INVALID if there is no such an edge. |
|
167 Edge findEdge(Node u,Node v, Edge prev = INVALID) |
|
168 { |
|
169 int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out; |
|
170 while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out; |
|
171 prev.n=e; |
|
172 return prev; |
|
173 } |
|
174 |
200 void clear() {nodes.clear();edges.clear();} |
175 void clear() {nodes.clear();edges.clear();} |
201 |
176 |
202 class Node { |
177 class Node { |
203 friend class SmartGraph; |
178 friend class SmartGraph; |
204 template <typename T> friend class NodeMap; |
179 template <typename T> friend class NodeMap; |
216 Node() {} |
191 Node() {} |
217 Node (Invalid) { n=-1; } |
192 Node (Invalid) { n=-1; } |
218 bool operator==(const Node i) const {return n==i.n;} |
193 bool operator==(const Node i) const {return n==i.n;} |
219 bool operator!=(const Node i) const {return n!=i.n;} |
194 bool operator!=(const Node i) const {return n!=i.n;} |
220 bool operator<(const Node i) const {return n<i.n;} |
195 bool operator<(const Node i) const {return n<i.n;} |
|
196 // ///Validity check |
|
197 // operator bool() { return n!=-1; } |
221 }; |
198 }; |
222 |
199 |
223 class NodeIt : public Node { |
200 class NodeIt : public Node { |
|
201 const SmartGraph *G; |
224 friend class SmartGraph; |
202 friend class SmartGraph; |
225 public: |
203 public: |
226 NodeIt() : Node() { } |
204 NodeIt() : Node() { } |
|
205 NodeIt(const SmartGraph& _G,Node n) : Node(n), G(&_G) { } |
227 NodeIt(Invalid i) : Node(i) { } |
206 NodeIt(Invalid i) : Node(i) { } |
228 NodeIt(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { } |
207 NodeIt(const SmartGraph& _G) : Node(_G.nodes.size()?0:-1), G(&_G) { } |
229 ///\todo Undocumented conversion Node -\> NodeIt. |
208 NodeIt &operator++() { |
230 NodeIt(const SmartGraph& G, const Node &n) : Node(n) { } |
209 n=(n+2)%(G->nodes.size()+1)-1; |
|
210 return *this; |
|
211 } |
|
212 // ///Validity check |
|
213 // operator bool() { return Node::operator bool(); } |
231 }; |
214 }; |
232 |
215 |
233 class Edge { |
216 class Edge { |
234 friend class SmartGraph; |
217 friend class SmartGraph; |
235 template <typename T> friend class EdgeMap; |
218 template <typename T> friend class EdgeMap; |
255 bool operator!=(const Edge i) const {return n!=i.n;} |
238 bool operator!=(const Edge i) const {return n!=i.n;} |
256 bool operator<(const Edge i) const {return n<i.n;} |
239 bool operator<(const Edge i) const {return n<i.n;} |
257 ///\bug This is a workaround until somebody tells me how to |
240 ///\bug This is a workaround until somebody tells me how to |
258 ///make class \c SymSmartGraph::SymEdgeMap friend of Edge |
241 ///make class \c SymSmartGraph::SymEdgeMap friend of Edge |
259 int &idref() {return n;} |
242 int &idref() {return n;} |
260 const int &idref() const {return n;} |
243 const int &idref() const {return n;} |
261 }; |
244 // ///Validity check |
|
245 // operator bool() { return n!=-1; } |
|
246 }; |
262 |
247 |
263 class EdgeIt : public Edge { |
248 class EdgeIt : public Edge { |
|
249 const SmartGraph *G; |
264 friend class SmartGraph; |
250 friend class SmartGraph; |
265 public: |
251 public: |
266 EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { } |
252 EdgeIt(const SmartGraph& _G) : Edge(_G.edges.size()-1), G(&_G) { } |
|
253 EdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { } |
267 EdgeIt (Invalid i) : Edge(i) { } |
254 EdgeIt (Invalid i) : Edge(i) { } |
268 EdgeIt() : Edge() { } |
255 EdgeIt() : Edge() { } |
269 ///\bug This is a workaround until somebody tells me how to |
256 ///\bug This is a workaround until somebody tells me how to |
270 ///make class \c SymSmartGraph::SymEdgeMap friend of Edge |
257 ///make class \c SymSmartGraph::SymEdgeMap friend of Edge |
271 int &idref() {return n;} |
258 int &idref() {return n;} |
|
259 EdgeIt &operator++() { --n; return *this; } |
|
260 // ///Validity check |
|
261 // operator bool() { return Edge::operator bool(); } |
272 }; |
262 }; |
273 |
263 |
274 class OutEdgeIt : public Edge { |
264 class OutEdgeIt : public Edge { |
|
265 const SmartGraph *G; |
275 friend class SmartGraph; |
266 friend class SmartGraph; |
276 public: |
267 public: |
277 OutEdgeIt() : Edge() { } |
268 OutEdgeIt() : Edge() { } |
|
269 OutEdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { } |
278 OutEdgeIt (Invalid i) : Edge(i) { } |
270 OutEdgeIt (Invalid i) : Edge(i) { } |
279 |
271 |
280 OutEdgeIt(const SmartGraph& G,const Node v) |
272 OutEdgeIt(const SmartGraph& _G,const Node v) |
281 : Edge(G.nodes[v.n].first_out) {} |
273 : Edge(_G.nodes[v.n].first_out), G(&_G) {} |
|
274 OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; } |
|
275 // ///Validity check |
|
276 // operator bool() { return Edge::operator bool(); } |
282 }; |
277 }; |
283 |
278 |
284 class InEdgeIt : public Edge { |
279 class InEdgeIt : public Edge { |
|
280 const SmartGraph *G; |
285 friend class SmartGraph; |
281 friend class SmartGraph; |
286 public: |
282 public: |
287 InEdgeIt() : Edge() { } |
283 InEdgeIt() : Edge() { } |
|
284 InEdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { } |
288 InEdgeIt (Invalid i) : Edge(i) { } |
285 InEdgeIt (Invalid i) : Edge(i) { } |
289 InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){} |
286 InEdgeIt(const SmartGraph& _G,Node v) |
|
287 : Edge(_G.nodes[v.n].first_in), G(&_G) { } |
|
288 InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; } |
|
289 // ///Validity check |
|
290 // operator bool() { return Edge::operator bool(); } |
290 }; |
291 }; |
291 |
292 |
292 template <typename T> class NodeMap : public DynMapBase<Node> |
293 template <typename T> class NodeMap : public DynMapBase<Node> |
293 { |
294 { |
294 std::vector<T> container; |
295 std::vector<T> container; |