129 nodes[u.n].first_out=nodes[v.n].first_in=e.n; |
133 nodes[u.n].first_out=nodes[v.n].first_in=e.n; |
130 |
134 |
131 return e; |
135 return e; |
132 } |
136 } |
133 |
137 |
134 /// Finds an edge between two nodes. |
|
135 |
|
136 /// Finds an edge from node \c u to node \c v. |
|
137 /// |
|
138 /// If \c prev is \ref INVALID (this is the default value), then |
|
139 /// It finds the first edge from \c u to \c v. Otherwise it looks for |
|
140 /// the next edge from \c u to \c v after \c prev. |
|
141 /// \return The found edge or INVALID if there is no such an edge. |
|
142 Edge findEdge(Node u,Node v, Edge prev = INVALID) |
|
143 { |
|
144 int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out; |
|
145 while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out; |
|
146 prev.n=e; |
|
147 return prev; |
|
148 } |
|
149 |
|
150 void clear() { |
138 void clear() { |
151 edges.clear(); |
139 edges.clear(); |
152 nodes.clear(); |
140 nodes.clear(); |
153 } |
141 } |
154 |
142 |
212 |
200 |
213 void nextIn(Edge& edge) const { |
201 void nextIn(Edge& edge) const { |
214 edge.n = edges[edge.n].next_in; |
202 edge.n = edges[edge.n].next_in; |
215 } |
203 } |
216 |
204 |
|
205 Edge _findEdge(Node u,Node v, Edge prev = INVALID) |
|
206 { |
|
207 int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out; |
|
208 while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out; |
|
209 prev.n=e; |
|
210 return prev; |
|
211 } |
217 }; |
212 }; |
218 |
213 |
219 typedef AlterableGraphExtender<SmartGraphBase> AlterableSmartGraphBase; |
214 typedef AlterableGraphExtender<SmartGraphBase> AlterableSmartGraphBase; |
220 typedef IterableGraphExtender<AlterableSmartGraphBase> IterableSmartGraphBase; |
215 typedef IterableGraphExtender<AlterableSmartGraphBase> IterableSmartGraphBase; |
221 typedef IdMappableGraphExtender<IterableSmartGraphBase> IdMappableSmartGraphBase; |
216 typedef IdMappableGraphExtender<IterableSmartGraphBase> IdMappableSmartGraphBase; |
240 ///(or rollBack() ) |
235 ///(or rollBack() ) |
241 ///would remove the nodes and edges added after the call of saveState(). |
236 ///would remove the nodes and edges added after the call of saveState(). |
242 ///Of course it should be used as a stack. (Maybe X is not necessary.) |
237 ///Of course it should be used as a stack. (Maybe X is not necessary.) |
243 /// |
238 /// |
244 ///\author Alpar Juttner |
239 ///\author Alpar Juttner |
245 class SmartGraph :public ClearableSmartGraphBase { }; |
240 class SmartGraph :public ClearableSmartGraphBase { |
|
241 public: |
|
242 /// Finds an edge between two nodes. |
|
243 |
|
244 /// Finds an edge from node \c u to node \c v. |
|
245 /// |
|
246 /// If \c prev is \ref INVALID (this is the default value), then |
|
247 /// it finds the first edge from \c u to \c v. Otherwise it looks for |
|
248 /// the next edge from \c u to \c v after \c prev. |
|
249 /// \return The found edge or \ref INVALID if there is no such an edge. |
|
250 /// |
|
251 /// Thus you can iterate through each edge from \c u to \c v as it follows. |
|
252 /// \code |
|
253 /// for(Edge e=G.findEdge(u,v);e!=INVALID;e=G.findEdge(u,v,e)) { |
|
254 /// ... |
|
255 /// } |
|
256 /// \endcode |
|
257 /// \todo Possibly it should be a global function. |
|
258 Edge findEdge(Node u,Node v, Edge prev = INVALID) |
|
259 { |
|
260 return _findEdge(u,v,prev); |
|
261 } |
|
262 }; |
246 |
263 |
247 template <> |
264 template <> |
248 int countNodes<SmartGraph>(const SmartGraph& graph) { |
265 int countNodes<SmartGraph>(const SmartGraph& graph) { |
249 return graph.nodeNum(); |
266 return graph.nodeNum(); |
250 } |
267 } |