158 inline int countInEdges(const Graph& _g, const typename Graph::Node& _n) { |
158 inline int countInEdges(const Graph& _g, const typename Graph::Node& _n) { |
159 return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n); |
159 return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n); |
160 } |
160 } |
161 |
161 |
162 |
162 |
163 /// Finds an edge between two nodes of a graph. |
163 template <typename Graph> |
164 |
164 inline |
|
165 typename enable_if<typename Graph::FindEdgeTag, typename Graph::Edge>::type |
|
166 _findEdge(const Graph &g, |
|
167 typename Graph::Node u, typename Graph::Node v, |
|
168 typename Graph::Edge prev = INVALID) { |
|
169 return g.findEdge(u, v, prev); |
|
170 } |
|
171 |
|
172 template <typename Graph> |
|
173 inline typename Graph::Edge |
|
174 _findEdge(Wrap<Graph> w, |
|
175 typename Graph::Node u, |
|
176 typename Graph::Node v, |
|
177 typename Graph::Edge prev = INVALID) { |
|
178 const Graph& g = w.value; |
|
179 if (prev == INVALID) { |
|
180 typename Graph::OutEdgeIt e(g, u); |
|
181 while (e != INVALID && g.target(e) != v) ++e; |
|
182 return e; |
|
183 } else { |
|
184 typename Graph::OutEdgeIt e(g, prev); ++e; |
|
185 while (e != INVALID && g.target(e) != v) ++e; |
|
186 return e; |
|
187 } |
|
188 } |
|
189 |
|
190 /// \brief Finds an edge between two nodes of a graph. |
|
191 /// |
165 /// Finds an edge from node \c u to node \c v in graph \c g. |
192 /// Finds an edge from node \c u to node \c v in graph \c g. |
166 /// |
193 /// |
167 /// If \c prev is \ref INVALID (this is the default value), then |
194 /// If \c prev is \ref INVALID (this is the default value), then |
168 /// it finds the first edge from \c u to \c v. Otherwise it looks for |
195 /// it finds the first edge from \c u to \c v. Otherwise it looks for |
169 /// the next edge from \c u to \c v after \c prev. |
196 /// the next edge from \c u to \c v after \c prev. |
173 /// \code |
200 /// \code |
174 /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) { |
201 /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) { |
175 /// ... |
202 /// ... |
176 /// } |
203 /// } |
177 /// \endcode |
204 /// \endcode |
178 /// \todo We may want to use the "GraphBase" |
205 // /// \todo We may want to use the "GraphBase" |
179 /// interface here... |
206 // /// interface here... |
180 /// \bug Untested ... |
207 // /// It would not work with the undirected graphs. |
181 template <typename Graph> |
208 template <typename Graph> |
182 typename Graph::Edge findEdge(const Graph &g, |
209 inline typename Graph::Edge findEdge(const Graph &g, |
183 typename Graph::Node u, typename Graph::Node v, |
210 typename Graph::Node u, |
184 typename Graph::Edge prev = INVALID) |
211 typename Graph::Node v, |
185 { |
212 typename Graph::Edge prev = INVALID) { |
186 typename Graph::OutEdgeIt e(g,prev); |
213 return _findEdge<Graph>(g, u, v, prev); |
187 // if(prev==INVALID) g.first(e,u); |
214 } |
188 if(prev==INVALID) e=typename Graph::OutEdgeIt(g,u); |
215 |
189 else ++e; |
216 /// \brief Iterator for iterating on edges connected the same nodes. |
190 while(e!=INVALID && g.target(e)!=v) ++e; |
217 /// |
191 return e; |
218 /// Iterator for iterating on edges connected the same nodes. It is |
192 } |
219 /// higher level interface for the findEdge() function. You can |
|
220 /// use it the next way: |
|
221 /// \code |
|
222 /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) { |
|
223 /// ... |
|
224 /// } |
|
225 /// \endcode |
|
226 /// |
|
227 /// \author Balazs Dezso |
|
228 template <typename _Graph> |
|
229 class ConEdgeIt : public _Graph::Edge { |
|
230 public: |
|
231 |
|
232 typedef _Graph Graph; |
|
233 typedef typename Graph::Edge Parent; |
|
234 |
|
235 typedef typename Graph::Edge Edge; |
|
236 typedef typename Graph::Node Node; |
|
237 |
|
238 /// \brief Constructor. |
|
239 /// |
|
240 /// Construct a new ConEdgeIt iterating on the edges which |
|
241 /// connects the \c u and \c v node. |
|
242 ConEdgeIt(const Graph& g, Node u, Node v) : graph(g) { |
|
243 Parent::operator=(findEdge(graph, u, v)); |
|
244 } |
|
245 |
|
246 /// \brief Constructor. |
|
247 /// |
|
248 /// Construct a new ConEdgeIt which continues the iterating from |
|
249 /// the \c e edge. |
|
250 ConEdgeIt(const Graph& g, Edge e) : Parent(e), graph(g) {} |
|
251 |
|
252 /// \brief Increment operator. |
|
253 /// |
|
254 /// It increments the iterator and gives back the next edge. |
|
255 ConEdgeIt& operator++() { |
|
256 Parent::operator=(findEdge(graph, graph.source(*this), |
|
257 graph.target(*this), *this)); |
|
258 return *this; |
|
259 } |
|
260 private: |
|
261 const Graph& graph; |
|
262 }; |
193 |
263 |
194 /// \brief Copy a map. |
264 /// \brief Copy a map. |
195 /// |
265 /// |
196 /// This function copies the \c source map to the \c target map. It uses the |
266 /// This function copies the \c source map to the \c target map. It uses the |
197 /// given iterator to iterate on the data structure and it uses the \c ref |
267 /// given iterator to iterate on the data structure and it uses the \c ref |