equal
deleted
inserted
replaced
1 // -*- c++ -*- |
1 // -*- c++ -*- |
2 #ifndef HUGO_BFS_DFS_MISC_H |
2 #ifndef LEMON_BFS_DFS_MISC_H |
3 #define HUGO_BFS_DFS_MISC_H |
3 #define LEMON_BFS_DFS_MISC_H |
4 |
4 |
5 /// \ingroup galgs |
5 /// \ingroup galgs |
6 /// \file |
6 /// \file |
7 /// \brief Miscellaneous algorithms using bfs and dfs. |
7 /// \brief Miscellaneous algorithms using bfs and dfs. |
8 /// |
8 /// |
11 // ///\author Marton Makai |
11 // ///\author Marton Makai |
12 |
12 |
13 #include <bfs_dfs.h> |
13 #include <bfs_dfs.h> |
14 #include <for_each_macros.h> |
14 #include <for_each_macros.h> |
15 |
15 |
16 namespace hugo { |
16 namespace lemon { |
17 |
17 |
18 /// This function eats a read-write \c BoolMap& bool_map, |
18 /// This function eats a read-write \c BoolMap& bool_map, |
19 /// which have to work well up |
19 /// which have to work well up |
20 /// to its \c set and \c operator[]() method. Thus we have to deal |
20 /// to its \c set and \c operator[]() method. Thus we have to deal |
21 /// very carefully with an uninitialized \c IterableBoolMap. |
21 /// very carefully with an uninitialized \c IterableBoolMap. |
69 dfs.pushAndSetReached(n); |
69 dfs.pushAndSetReached(n); |
70 pred.set(n, INVALID); |
70 pred.set(n, INVALID); |
71 while (!dfs.finished()) { |
71 while (!dfs.finished()) { |
72 ++dfs; |
72 ++dfs; |
73 if (dfs.isBNodeNewlyReached()) { |
73 if (dfs.isBNodeNewlyReached()) { |
74 ///\bug hugo 0.2-ben Edge kell |
74 ///\bug lemon 0.2-ben Edge kell |
75 pred.set(dfs.aNode(), typename Graph::OutEdgeIt(dfs)); |
75 pred.set(dfs.aNode(), typename Graph::OutEdgeIt(dfs)); |
76 } else { |
76 } else { |
77 ///\bug ugyanaz |
77 ///\bug ugyanaz |
78 if (g.valid(typename Graph::OutEdgeIt(dfs)) && |
78 if (g.valid(typename Graph::OutEdgeIt(dfs)) && |
79 !examined[dfs.bNode()]) { |
79 !examined[dfs.bNode()]) { |
80 ///\bug hugo 0.2-ben Edge kell |
80 ///\bug lemon 0.2-ben Edge kell |
81 pred.set(dfs.bNode(), typename Graph::OutEdgeIt(dfs)); |
81 pred.set(dfs.bNode(), typename Graph::OutEdgeIt(dfs)); |
82 return dfs.aNode(); |
82 return dfs.aNode(); |
83 } |
83 } |
84 } |
84 } |
85 if (dfs.isANodeExamined()) { |
85 if (dfs.isANodeExamined()) { |
90 } |
90 } |
91 } |
91 } |
92 return INVALID; |
92 return INVALID; |
93 } |
93 } |
94 |
94 |
95 } //namespace hugo |
95 } //namespace lemon |
96 |
96 |
97 #endif //HUGO_BFS_DFS_MISC_H |
97 #endif //LEMON_BFS_DFS_MISC_H |