1.1 --- a/src/work/marci/bfs_iterator.h Mon Apr 05 15:31:21 2004 +0000
1.2 +++ b/src/work/marci/bfs_iterator.h Mon Apr 05 16:52:46 2004 +0000
1.3 @@ -5,7 +5,6 @@
1.4 #include <queue>
1.5 #include <stack>
1.6 #include <utility>
1.7 -#include <graph_wrapper.h>
1.8
1.9 namespace hugo {
1.10
1.11 @@ -630,40 +629,34 @@
1.12 // };
1.13
1.14
1.15 - template <typename GraphWrapper, /*typename OutEdgeIt,*/
1.16 - typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
1.17 + template <typename Graph, /*typename OutEdgeIt,*/
1.18 + typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
1.19 class BfsIterator5 {
1.20 - typedef typename GraphWrapper::Node Node;
1.21 - typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
1.22 - GraphWrapper G;
1.23 + protected:
1.24 + typedef typename Graph::Node Node;
1.25 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.26 + const Graph* graph;
1.27 std::queue<Node> bfs_queue;
1.28 ReachedMap& reached;
1.29 bool b_node_newly_reached;
1.30 OutEdgeIt actual_edge;
1.31 bool own_reached_map;
1.32 public:
1.33 - BfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
1.34 - G(_G), reached(_reached),
1.35 + BfsIterator5(const Graph& _graph, ReachedMap& _reached) :
1.36 + graph(&_graph), reached(_reached),
1.37 own_reached_map(false) { }
1.38 - BfsIterator5(const GraphWrapper& _G) :
1.39 - G(_G), reached(*(new ReachedMap(G /*, false*/))),
1.40 + BfsIterator5(const Graph& _graph) :
1.41 + graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
1.42 own_reached_map(true) { }
1.43 -// BfsIterator5(const typename GraphWrapper::BaseGraph& _G,
1.44 -// ReachedMap& _reached) :
1.45 -// G(_G), reached(_reached),
1.46 -// own_reached_map(false) { }
1.47 -// BfsIterator5(const typename GraphWrapper::BaseGraph& _G) :
1.48 -// G(_G), reached(*(new ReachedMap(G /*, false*/))),
1.49 -// own_reached_map(true) { }
1.50 ~BfsIterator5() { if (own_reached_map) delete &reached; }
1.51 void pushAndSetReached(Node s) {
1.52 reached.set(s, true);
1.53 if (bfs_queue.empty()) {
1.54 bfs_queue.push(s);
1.55 - G./*getF*/first(actual_edge, s);
1.56 - if (G.valid(actual_edge)/*.valid()*/) {
1.57 - Node w=G.bNode(actual_edge);
1.58 - if (!reached.get(w)) {
1.59 + graph->first(actual_edge, s);
1.60 + if (graph->valid(actual_edge)) {
1.61 + Node w=graph->bNode(actual_edge);
1.62 + if (!reached[w]) {
1.63 bfs_queue.push(w);
1.64 reached.set(w, true);
1.65 b_node_newly_reached=true;
1.66 @@ -675,13 +668,13 @@
1.67 bfs_queue.push(s);
1.68 }
1.69 }
1.70 - BfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>&
1.71 + BfsIterator5<Graph, /*OutEdgeIt,*/ ReachedMap>&
1.72 operator++() {
1.73 - if (G.valid(actual_edge)/*.valid()*/) {
1.74 - /*++*/G.next(actual_edge);
1.75 - if (G.valid(actual_edge)/*.valid()*/) {
1.76 - Node w=G.bNode(actual_edge);
1.77 - if (!reached.get(w)) {
1.78 + if (graph->valid(actual_edge)) {
1.79 + graph->next(actual_edge);
1.80 + if (graph->valid(actual_edge)) {
1.81 + Node w=graph->bNode(actual_edge);
1.82 + if (!reached[w]) {
1.83 bfs_queue.push(w);
1.84 reached.set(w, true);
1.85 b_node_newly_reached=true;
1.86 @@ -692,10 +685,10 @@
1.87 } else {
1.88 bfs_queue.pop();
1.89 if (!bfs_queue.empty()) {
1.90 - G./*getF*/first(actual_edge, bfs_queue.front());
1.91 - if (G.valid(actual_edge)/*.valid()*/) {
1.92 - Node w=G.bNode(actual_edge);
1.93 - if (!reached.get(w)) {
1.94 + graph->first(actual_edge, bfs_queue.front());
1.95 + if (graph->valid(actual_edge)) {
1.96 + Node w=graph->bNode(actual_edge);
1.97 + if (!reached[w]) {
1.98 bfs_queue.push(w);
1.99 reached.set(w, true);
1.100 b_node_newly_reached=true;
1.101 @@ -710,9 +703,9 @@
1.102 bool finished() const { return bfs_queue.empty(); }
1.103 operator OutEdgeIt () const { return actual_edge; }
1.104 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.105 - bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
1.106 + bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
1.107 Node aNode() const { return bfs_queue.front(); }
1.108 - Node bNode() const { return G.bNode(actual_edge); }
1.109 + Node bNode() const { return graph->bNode(actual_edge); }
1.110 const ReachedMap& getReachedMap() const { return reached; }
1.111 const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
1.112 };
1.113 @@ -773,12 +766,13 @@
1.114 // const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
1.115 // };
1.116
1.117 - template <typename GraphWrapper, /*typename OutEdgeIt,*/
1.118 - typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
1.119 + template <typename Graph, /*typename OutEdgeIt,*/
1.120 + typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
1.121 class DfsIterator5 {
1.122 - typedef typename GraphWrapper::Node Node;
1.123 - typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
1.124 - GraphWrapper G;
1.125 + protected:
1.126 + typedef typename Graph::Node Node;
1.127 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.128 + const Graph* graph;
1.129 std::stack<OutEdgeIt> dfs_stack;
1.130 bool b_node_newly_reached;
1.131 OutEdgeIt actual_edge;
1.132 @@ -786,36 +780,36 @@
1.133 ReachedMap& reached;
1.134 bool own_reached_map;
1.135 public:
1.136 - DfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
1.137 - G(_G), reached(_reached),
1.138 + DfsIterator5(const Graph& _graph, ReachedMap& _reached) :
1.139 + graph(&_graph), reached(_reached),
1.140 own_reached_map(false) { }
1.141 - DfsIterator5(const GraphWrapper& _G) :
1.142 - G(_G), reached(*(new ReachedMap(G /*, false*/))),
1.143 + DfsIterator5(const Graph& _graph) :
1.144 + graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
1.145 own_reached_map(true) { }
1.146 ~DfsIterator5() { if (own_reached_map) delete &reached; }
1.147 void pushAndSetReached(Node s) {
1.148 actual_node=s;
1.149 reached.set(s, true);
1.150 OutEdgeIt e;
1.151 - G.first(e, s);
1.152 + graph->first(e, s);
1.153 dfs_stack.push(e);
1.154 }
1.155 - DfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>&
1.156 + DfsIterator5<Graph, /*OutEdgeIt,*/ ReachedMap>&
1.157 operator++() {
1.158 actual_edge=dfs_stack.top();
1.159 //actual_node=G.aNode(actual_edge);
1.160 - if (G.valid(actual_edge)/*.valid()*/) {
1.161 - Node w=G.bNode(actual_edge);
1.162 + if (graph->valid(actual_edge)/*.valid()*/) {
1.163 + Node w=graph->bNode(actual_edge);
1.164 actual_node=w;
1.165 - if (!reached.get(w)) {
1.166 + if (!reached[w]) {
1.167 OutEdgeIt e;
1.168 - G.first(e, w);
1.169 + graph->first(e, w);
1.170 dfs_stack.push(e);
1.171 reached.set(w, true);
1.172 b_node_newly_reached=true;
1.173 } else {
1.174 - actual_node=G.aNode(actual_edge);
1.175 - /*++*/G.next(dfs_stack.top());
1.176 + actual_node=graph->aNode(actual_edge);
1.177 + graph->next(dfs_stack.top());
1.178 b_node_newly_reached=false;
1.179 }
1.180 } else {
1.181 @@ -827,7 +821,7 @@
1.182 bool finished() const { return dfs_stack.empty(); }
1.183 operator OutEdgeIt () const { return actual_edge; }
1.184 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.185 - bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
1.186 + bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
1.187 Node aNode() const { return actual_node; /*FIXME*/}
1.188 Node bNode() const { return G.bNode(actual_edge); }
1.189 const ReachedMap& getReachedMap() const { return reached; }