Changeset 1704:467d7927a901 in lemon-0.x for lemon/graph_utils.h
- Timestamp:
- 10/05/05 15:17:42 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2231
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/graph_utils.h
r1695 r1704 161 161 } 162 162 163 /// \brief Function to count the number of the in -edges to node \c n.164 /// 165 /// This function counts the number of the in -edges to node \c n163 /// \brief Function to count the number of the inc-edges to node \c n. 164 /// 165 /// This function counts the number of the inc-edges to node \c n 166 166 /// in the graph. 167 167 template <typename Graph> … … 215 215 // /// \todo We may want to use the "GraphBase" 216 216 // /// interface here... 217 // /// It would not work with the undirected graphs.218 217 template <typename Graph> 219 218 inline typename Graph::Edge findEdge(const Graph &g, … … 265 264 ConEdgeIt& operator++() { 266 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 370 graph.target(*this), *this)); 268 371 return *this; … … 553 656 typedef _Item Key; 554 657 555 typedef True NeedCopy;556 557 658 /// \brief Constructor. 558 659 /// … … 577 678 class InverseMap { 578 679 public: 579 580 typedef True NeedCopy;581 680 582 681 /// \brief Constructor. … … 907 1006 public: 908 1007 909 typedef True NeedCopy;910 911 1008 typedef typename Graph::Node Value; 912 1009 typedef typename Graph::Edge Key; … … 948 1045 public: 949 1046 950 typedef True NeedCopy;951 952 1047 typedef typename Graph::Node Value; 953 1048 typedef typename Graph::Edge Key; … … 989 1084 public: 990 1085 991 typedef True NeedCopy;992 993 1086 typedef typename Graph::Edge Value; 994 1087 typedef typename Graph::UndirEdge Key; … … 1029 1122 class BackwardMap { 1030 1123 public: 1031 typedef True NeedCopy;1032 1124 1033 1125 typedef typename Graph::Edge Value; … … 1297 1389 1298 1390 static int index(int i, int j) { 1299 int m = i > j ? i : j;1300 1391 if (i < j) { 1301 return m * m+ i;1392 return j * j + i; 1302 1393 } else { 1303 return m * m + m+ j;1394 return i * i + i + j; 1304 1395 } 1305 1396 }
Note: See TracChangeset
for help on using the changeset viewer.