[301] | 1 | // -*- c++ -*- |
---|
| 2 | #ifndef HUGO_BFS_ITERATOR_H |
---|
| 3 | #define HUGO_BFS_ITERATOR_H |
---|
| 4 | |
---|
| 5 | #include <queue> |
---|
| 6 | #include <stack> |
---|
| 7 | #include <utility> |
---|
| 8 | |
---|
| 9 | namespace hugo { |
---|
| 10 | |
---|
[303] | 11 | template <typename Graph, /*typename OutEdgeIt,*/ |
---|
| 12 | typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > |
---|
[360] | 13 | class BfsIterator { |
---|
[303] | 14 | protected: |
---|
| 15 | typedef typename Graph::Node Node; |
---|
| 16 | typedef typename Graph::OutEdgeIt OutEdgeIt; |
---|
| 17 | const Graph* graph; |
---|
[301] | 18 | std::queue<Node> bfs_queue; |
---|
| 19 | ReachedMap& reached; |
---|
| 20 | bool b_node_newly_reached; |
---|
| 21 | OutEdgeIt actual_edge; |
---|
| 22 | bool own_reached_map; |
---|
| 23 | public: |
---|
[360] | 24 | BfsIterator(const Graph& _graph, ReachedMap& _reached) : |
---|
[303] | 25 | graph(&_graph), reached(_reached), |
---|
[301] | 26 | own_reached_map(false) { } |
---|
[360] | 27 | BfsIterator(const Graph& _graph) : |
---|
[303] | 28 | graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), |
---|
[301] | 29 | own_reached_map(true) { } |
---|
[360] | 30 | ~BfsIterator() { if (own_reached_map) delete &reached; } |
---|
[301] | 31 | void pushAndSetReached(Node s) { |
---|
| 32 | reached.set(s, true); |
---|
| 33 | if (bfs_queue.empty()) { |
---|
| 34 | bfs_queue.push(s); |
---|
[303] | 35 | graph->first(actual_edge, s); |
---|
| 36 | if (graph->valid(actual_edge)) { |
---|
| 37 | Node w=graph->bNode(actual_edge); |
---|
| 38 | if (!reached[w]) { |
---|
[301] | 39 | bfs_queue.push(w); |
---|
| 40 | reached.set(w, true); |
---|
| 41 | b_node_newly_reached=true; |
---|
| 42 | } else { |
---|
| 43 | b_node_newly_reached=false; |
---|
| 44 | } |
---|
| 45 | } |
---|
| 46 | } else { |
---|
| 47 | bfs_queue.push(s); |
---|
| 48 | } |
---|
| 49 | } |
---|
[360] | 50 | BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& |
---|
[301] | 51 | operator++() { |
---|
[303] | 52 | if (graph->valid(actual_edge)) { |
---|
| 53 | graph->next(actual_edge); |
---|
| 54 | if (graph->valid(actual_edge)) { |
---|
| 55 | Node w=graph->bNode(actual_edge); |
---|
| 56 | if (!reached[w]) { |
---|
[301] | 57 | bfs_queue.push(w); |
---|
| 58 | reached.set(w, true); |
---|
| 59 | b_node_newly_reached=true; |
---|
| 60 | } else { |
---|
| 61 | b_node_newly_reached=false; |
---|
| 62 | } |
---|
| 63 | } |
---|
| 64 | } else { |
---|
| 65 | bfs_queue.pop(); |
---|
| 66 | if (!bfs_queue.empty()) { |
---|
[303] | 67 | graph->first(actual_edge, bfs_queue.front()); |
---|
| 68 | if (graph->valid(actual_edge)) { |
---|
| 69 | Node w=graph->bNode(actual_edge); |
---|
| 70 | if (!reached[w]) { |
---|
[301] | 71 | bfs_queue.push(w); |
---|
| 72 | reached.set(w, true); |
---|
| 73 | b_node_newly_reached=true; |
---|
| 74 | } else { |
---|
| 75 | b_node_newly_reached=false; |
---|
| 76 | } |
---|
| 77 | } |
---|
| 78 | } |
---|
| 79 | } |
---|
| 80 | return *this; |
---|
| 81 | } |
---|
| 82 | bool finished() const { return bfs_queue.empty(); } |
---|
| 83 | operator OutEdgeIt () const { return actual_edge; } |
---|
| 84 | bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
---|
[303] | 85 | bool isANodeExamined() const { return !(graph->valid(actual_edge)); } |
---|
[301] | 86 | Node aNode() const { return bfs_queue.front(); } |
---|
[303] | 87 | Node bNode() const { return graph->bNode(actual_edge); } |
---|
[301] | 88 | const ReachedMap& getReachedMap() const { return reached; } |
---|
| 89 | const std::queue<Node>& getBfsQueue() const { return bfs_queue; } |
---|
| 90 | }; |
---|
| 91 | |
---|
[303] | 92 | template <typename Graph, /*typename OutEdgeIt,*/ |
---|
| 93 | typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > |
---|
[360] | 94 | class DfsIterator { |
---|
[303] | 95 | protected: |
---|
| 96 | typedef typename Graph::Node Node; |
---|
| 97 | typedef typename Graph::OutEdgeIt OutEdgeIt; |
---|
| 98 | const Graph* graph; |
---|
[301] | 99 | std::stack<OutEdgeIt> dfs_stack; |
---|
| 100 | bool b_node_newly_reached; |
---|
| 101 | OutEdgeIt actual_edge; |
---|
| 102 | Node actual_node; |
---|
| 103 | ReachedMap& reached; |
---|
| 104 | bool own_reached_map; |
---|
| 105 | public: |
---|
[360] | 106 | DfsIterator(const Graph& _graph, ReachedMap& _reached) : |
---|
[303] | 107 | graph(&_graph), reached(_reached), |
---|
[301] | 108 | own_reached_map(false) { } |
---|
[360] | 109 | DfsIterator(const Graph& _graph) : |
---|
[303] | 110 | graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), |
---|
[301] | 111 | own_reached_map(true) { } |
---|
[360] | 112 | ~DfsIterator() { if (own_reached_map) delete &reached; } |
---|
[301] | 113 | void pushAndSetReached(Node s) { |
---|
| 114 | actual_node=s; |
---|
| 115 | reached.set(s, true); |
---|
| 116 | OutEdgeIt e; |
---|
[303] | 117 | graph->first(e, s); |
---|
[301] | 118 | dfs_stack.push(e); |
---|
| 119 | } |
---|
[360] | 120 | DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& |
---|
[301] | 121 | operator++() { |
---|
| 122 | actual_edge=dfs_stack.top(); |
---|
| 123 | //actual_node=G.aNode(actual_edge); |
---|
[303] | 124 | if (graph->valid(actual_edge)/*.valid()*/) { |
---|
| 125 | Node w=graph->bNode(actual_edge); |
---|
[301] | 126 | actual_node=w; |
---|
[303] | 127 | if (!reached[w]) { |
---|
[301] | 128 | OutEdgeIt e; |
---|
[303] | 129 | graph->first(e, w); |
---|
[301] | 130 | dfs_stack.push(e); |
---|
| 131 | reached.set(w, true); |
---|
| 132 | b_node_newly_reached=true; |
---|
| 133 | } else { |
---|
[303] | 134 | actual_node=graph->aNode(actual_edge); |
---|
| 135 | graph->next(dfs_stack.top()); |
---|
[301] | 136 | b_node_newly_reached=false; |
---|
| 137 | } |
---|
| 138 | } else { |
---|
| 139 | //actual_node=G.aNode(dfs_stack.top()); |
---|
| 140 | dfs_stack.pop(); |
---|
| 141 | } |
---|
| 142 | return *this; |
---|
| 143 | } |
---|
| 144 | bool finished() const { return dfs_stack.empty(); } |
---|
| 145 | operator OutEdgeIt () const { return actual_edge; } |
---|
| 146 | bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
---|
[303] | 147 | bool isANodeExamined() const { return !(graph->valid(actual_edge)); } |
---|
[301] | 148 | Node aNode() const { return actual_node; /*FIXME*/} |
---|
[389] | 149 | Node bNode() const { return graph->bNode(actual_edge); } |
---|
[301] | 150 | const ReachedMap& getReachedMap() const { return reached; } |
---|
| 151 | const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; } |
---|
| 152 | }; |
---|
| 153 | |
---|
| 154 | } // namespace hugo |
---|
| 155 | |
---|
| 156 | #endif //HUGO_BFS_ITERATOR_H |
---|