changeset 1705 | 3f63d9db307b |
parent 1695 | e6f99fe1723f |
child 1712 | 4fb435ad31cf |
22:1ef52a3eb8ab | 23:7b4eca91f158 |
---|---|
158 template <typename Graph> |
158 template <typename Graph> |
159 inline int countInEdges(const Graph& _g, const typename Graph::Node& _n) { |
159 inline int countInEdges(const Graph& _g, const typename Graph::Node& _n) { |
160 return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n); |
160 return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n); |
161 } |
161 } |
162 |
162 |
163 /// \brief Function to count the number of the in-edges to node \c n. |
163 /// \brief Function to count the number of the inc-edges to node \c n. |
164 /// |
164 /// |
165 /// This function counts the number of the in-edges to node \c n |
165 /// This function counts the number of the inc-edges to node \c n |
166 /// in the graph. |
166 /// in the graph. |
167 template <typename Graph> |
167 template <typename Graph> |
168 inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) { |
168 inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) { |
169 return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n); |
169 return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n); |
170 } |
170 } |
212 /// ... |
212 /// ... |
213 /// } |
213 /// } |
214 /// \endcode |
214 /// \endcode |
215 // /// \todo We may want to use the "GraphBase" |
215 // /// \todo We may want to use the "GraphBase" |
216 // /// interface here... |
216 // /// interface here... |
217 // /// It would not work with the undirected graphs. |
|
218 template <typename Graph> |
217 template <typename Graph> |
219 inline typename Graph::Edge findEdge(const Graph &g, |
218 inline typename Graph::Edge findEdge(const Graph &g, |
220 typename Graph::Node u, |
219 typename Graph::Node u, |
221 typename Graph::Node v, |
220 typename Graph::Node v, |
222 typename Graph::Edge prev = INVALID) { |
221 typename Graph::Edge prev = INVALID) { |
262 /// \brief Increment operator. |
261 /// \brief Increment operator. |
263 /// |
262 /// |
264 /// It increments the iterator and gives back the next edge. |
263 /// It increments the iterator and gives back the next edge. |
265 ConEdgeIt& operator++() { |
264 ConEdgeIt& operator++() { |
266 Parent::operator=(findEdge(graph, graph.source(*this), |
265 Parent::operator=(findEdge(graph, graph.source(*this), |
266 graph.target(*this), *this)); |
|
267 return *this; |
|
268 } |
|
269 private: |
|
270 const Graph& graph; |
|
271 }; |
|
272 |
|
273 template <typename Graph> |
|
274 inline |
|
275 typename enable_if< |
|
276 typename Graph::FindEdgeTag, |
|
277 typename Graph::UndirEdge>::type |
|
278 _findUndirEdge(const Graph &g, |
|
279 typename Graph::Node u, typename Graph::Node v, |
|
280 typename Graph::UndirEdge prev = INVALID) { |
|
281 return g.findUndirEdge(u, v, prev); |
|
282 } |
|
283 |
|
284 template <typename Graph> |
|
285 inline typename Graph::UndirEdge |
|
286 _findUndirEdge(Wrap<Graph> w, |
|
287 typename Graph::Node u, |
|
288 typename Graph::Node v, |
|
289 typename Graph::UndirEdge prev = INVALID) { |
|
290 const Graph& g = w.value; |
|
291 if (prev == INVALID) { |
|
292 typename Graph::OutEdgeIt e(g, u); |
|
293 while (e != INVALID && g.target(e) != v) ++e; |
|
294 return e; |
|
295 } else { |
|
296 typename Graph::OutEdgeIt e(g, g.direct(prev, u)); ++e; |
|
297 while (e != INVALID && g.target(e) != v) ++e; |
|
298 return e; |
|
299 } |
|
300 } |
|
301 |
|
302 /// \brief Finds an undir edge between two nodes of a graph. |
|
303 /// |
|
304 /// Finds an undir edge from node \c u to node \c v in graph \c g. |
|
305 /// |
|
306 /// If \c prev is \ref INVALID (this is the default value), then |
|
307 /// it finds the first edge from \c u to \c v. Otherwise it looks for |
|
308 /// the next edge from \c u to \c v after \c prev. |
|
309 /// \return The found edge or \ref INVALID if there is no such an edge. |
|
310 /// |
|
311 /// Thus you can iterate through each edge from \c u to \c v as it follows. |
|
312 /// \code |
|
313 /// for(UndirEdge e = findUndirEdge(g,u,v); e != INVALID; |
|
314 /// e = findUndirEdge(g,u,v,e)) { |
|
315 /// ... |
|
316 /// } |
|
317 /// \endcode |
|
318 // /// \todo We may want to use the "GraphBase" |
|
319 // /// interface here... |
|
320 template <typename Graph> |
|
321 inline typename Graph::UndirEdge |
|
322 findUndirEdge(const Graph &g, |
|
323 typename Graph::Node u, |
|
324 typename Graph::Node v, |
|
325 typename Graph::UndirEdge prev = INVALID) { |
|
326 return _findUndirEdge<Graph>(g, u, v, prev); |
|
327 } |
|
328 |
|
329 /// \brief Iterator for iterating on undir edges connected the same nodes. |
|
330 /// |
|
331 /// Iterator for iterating on undir edges connected the same nodes. It is |
|
332 /// higher level interface for the findUndirEdge() function. You can |
|
333 /// use it the following way: |
|
334 /// \code |
|
335 /// for (ConUndirEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) { |
|
336 /// ... |
|
337 /// } |
|
338 /// \endcode |
|
339 /// |
|
340 /// \author Balazs Dezso |
|
341 template <typename _Graph> |
|
342 class ConUndirEdgeIt : public _Graph::UndirEdge { |
|
343 public: |
|
344 |
|
345 typedef _Graph Graph; |
|
346 typedef typename Graph::UndirEdge Parent; |
|
347 |
|
348 typedef typename Graph::UndirEdge UndirEdge; |
|
349 typedef typename Graph::Node Node; |
|
350 |
|
351 /// \brief Constructor. |
|
352 /// |
|
353 /// Construct a new ConUndirEdgeIt iterating on the edges which |
|
354 /// connects the \c u and \c v node. |
|
355 ConUndirEdgeIt(const Graph& g, Node u, Node v) : graph(g) { |
|
356 Parent::operator=(findUndirEdge(graph, u, v)); |
|
357 } |
|
358 |
|
359 /// \brief Constructor. |
|
360 /// |
|
361 /// Construct a new ConUndirEdgeIt which continues the iterating from |
|
362 /// the \c e edge. |
|
363 ConUndirEdgeIt(const Graph& g, UndirEdge e) : Parent(e), graph(g) {} |
|
364 |
|
365 /// \brief Increment operator. |
|
366 /// |
|
367 /// It increments the iterator and gives back the next edge. |
|
368 ConUndirEdgeIt& operator++() { |
|
369 Parent::operator=(findUndirEdge(graph, graph.source(*this), |
|
267 graph.target(*this), *this)); |
370 graph.target(*this), *this)); |
268 return *this; |
371 return *this; |
269 } |
372 } |
270 private: |
373 private: |
271 const Graph& graph; |
374 const Graph& graph; |
550 typedef _Graph Graph; |
653 typedef _Graph Graph; |
551 typedef int Value; |
654 typedef int Value; |
552 typedef _Item Item; |
655 typedef _Item Item; |
553 typedef _Item Key; |
656 typedef _Item Key; |
554 |
657 |
555 typedef True NeedCopy; |
|
556 |
|
557 /// \brief Constructor. |
658 /// \brief Constructor. |
558 /// |
659 /// |
559 /// Constructor for creating id map. |
660 /// Constructor for creating id map. |
560 IdMap(const Graph& _graph) : graph(&_graph) {} |
661 IdMap(const Graph& _graph) : graph(&_graph) {} |
561 |
662 |
574 /// |
675 /// |
575 /// The class represents the inverse of its owner (IdMap). |
676 /// The class represents the inverse of its owner (IdMap). |
576 /// \see inverse() |
677 /// \see inverse() |
577 class InverseMap { |
678 class InverseMap { |
578 public: |
679 public: |
579 |
|
580 typedef True NeedCopy; |
|
581 |
680 |
582 /// \brief Constructor. |
681 /// \brief Constructor. |
583 /// |
682 /// |
584 /// Constructor for creating an id-to-item map. |
683 /// Constructor for creating an id-to-item map. |
585 InverseMap(const Graph& _graph) : graph(&_graph) {} |
684 InverseMap(const Graph& _graph) : graph(&_graph) {} |
904 /// \author Balazs Dezso |
1003 /// \author Balazs Dezso |
905 template <typename Graph> |
1004 template <typename Graph> |
906 class SourceMap { |
1005 class SourceMap { |
907 public: |
1006 public: |
908 |
1007 |
909 typedef True NeedCopy; |
|
910 |
|
911 typedef typename Graph::Node Value; |
1008 typedef typename Graph::Node Value; |
912 typedef typename Graph::Edge Key; |
1009 typedef typename Graph::Edge Key; |
913 |
1010 |
914 /// \brief Constructor |
1011 /// \brief Constructor |
915 /// |
1012 /// |
945 /// \author Balazs Dezso |
1042 /// \author Balazs Dezso |
946 template <typename Graph> |
1043 template <typename Graph> |
947 class TargetMap { |
1044 class TargetMap { |
948 public: |
1045 public: |
949 |
1046 |
950 typedef True NeedCopy; |
|
951 |
|
952 typedef typename Graph::Node Value; |
1047 typedef typename Graph::Node Value; |
953 typedef typename Graph::Edge Key; |
1048 typedef typename Graph::Edge Key; |
954 |
1049 |
955 /// \brief Constructor |
1050 /// \brief Constructor |
956 /// |
1051 /// |
986 /// \author Balazs Dezso |
1081 /// \author Balazs Dezso |
987 template <typename Graph> |
1082 template <typename Graph> |
988 class ForwardMap { |
1083 class ForwardMap { |
989 public: |
1084 public: |
990 |
1085 |
991 typedef True NeedCopy; |
|
992 |
|
993 typedef typename Graph::Edge Value; |
1086 typedef typename Graph::Edge Value; |
994 typedef typename Graph::UndirEdge Key; |
1087 typedef typename Graph::UndirEdge Key; |
995 |
1088 |
996 /// \brief Constructor |
1089 /// \brief Constructor |
997 /// |
1090 /// |
1026 /// Returns the "backward" directed edge view of an undirected edge. |
1119 /// Returns the "backward" directed edge view of an undirected edge. |
1027 /// \author Balazs Dezso |
1120 /// \author Balazs Dezso |
1028 template <typename Graph> |
1121 template <typename Graph> |
1029 class BackwardMap { |
1122 class BackwardMap { |
1030 public: |
1123 public: |
1031 typedef True NeedCopy; |
|
1032 |
1124 |
1033 typedef typename Graph::Edge Value; |
1125 typedef typename Graph::Edge Value; |
1034 typedef typename Graph::UndirEdge Key; |
1126 typedef typename Graph::UndirEdge Key; |
1035 |
1127 |
1036 /// \brief Constructor |
1128 /// \brief Constructor |
1294 RowMap rowMap(Node row) { return RowMap(*this, row); } |
1386 RowMap rowMap(Node row) { return RowMap(*this, row); } |
1295 |
1387 |
1296 protected: |
1388 protected: |
1297 |
1389 |
1298 static int index(int i, int j) { |
1390 static int index(int i, int j) { |
1299 int m = i > j ? i : j; |
|
1300 if (i < j) { |
1391 if (i < j) { |
1301 return m * m + i; |
1392 return j * j + i; |
1302 } else { |
1393 } else { |
1303 return m * m + m + j; |
1394 return i * i + i + j; |
1304 } |
1395 } |
1305 } |
1396 } |
1306 |
1397 |
1307 static int size(int s) { |
1398 static int size(int s) { |
1308 return s * s; |
1399 return s * s; |