1.1 --- a/src/work/bfs_iterator.hh Sun Mar 07 19:33:34 2004 +0000
1.2 +++ b/src/work/bfs_iterator.hh Mon Mar 08 12:29:07 2004 +0000
1.3 @@ -623,10 +623,11 @@
1.4 };
1.5
1.6
1.7 - template <typename GraphWrapper, typename OutEdgeIt,
1.8 + template <typename GraphWrapper, /*typename OutEdgeIt,*/
1.9 typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
1.10 class BfsIterator5 {
1.11 typedef typename GraphWrapper::NodeIt NodeIt;
1.12 + typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
1.13 GraphWrapper G;
1.14 std::queue<NodeIt> bfs_queue;
1.15 ReachedMap& reached;
1.16 @@ -640,6 +641,13 @@
1.17 BfsIterator5(const GraphWrapper& _G) :
1.18 G(_G), reached(*(new ReachedMap(G /*, false*/))),
1.19 own_reached_map(true) { }
1.20 +// BfsIterator5(const typename GraphWrapper::BaseGraph& _G,
1.21 +// ReachedMap& _reached) :
1.22 +// G(_G), reached(_reached),
1.23 +// own_reached_map(false) { }
1.24 +// BfsIterator5(const typename GraphWrapper::BaseGraph& _G) :
1.25 +// G(_G), reached(*(new ReachedMap(G /*, false*/))),
1.26 +// own_reached_map(true) { }
1.27 ~BfsIterator5() { if (own_reached_map) delete &reached; }
1.28 void pushAndSetReached(NodeIt s) {
1.29 reached.set(s, true);
1.30 @@ -660,7 +668,7 @@
1.31 bfs_queue.push(s);
1.32 }
1.33 }
1.34 - BfsIterator5<GraphWrapper, OutEdgeIt, ReachedMap>&
1.35 + BfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>&
1.36 operator++() {
1.37 if (G.valid(actual_edge)/*.valid()*/) {
1.38 /*++*/G.next(actual_edge);
1.39 @@ -758,10 +766,11 @@
1.40 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
1.41 };
1.42
1.43 - template <typename GraphWrapper, typename OutEdgeIt,
1.44 + template <typename GraphWrapper, /*typename OutEdgeIt,*/
1.45 typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
1.46 class DfsIterator5 {
1.47 typedef typename GraphWrapper::NodeIt NodeIt;
1.48 + typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
1.49 GraphWrapper G;
1.50 std::stack<OutEdgeIt> dfs_stack;
1.51 bool b_node_newly_reached;
1.52 @@ -782,7 +791,7 @@
1.53 reached.set(s, true);
1.54 dfs_stack.push(G.template first<OutEdgeIt>(s));
1.55 }
1.56 - DfsIterator5<GraphWrapper, OutEdgeIt, ReachedMap>&
1.57 + DfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>&
1.58 operator++() {
1.59 actual_edge=dfs_stack.top();
1.60 //actual_node=G.aNode(actual_edge);
2.1 --- a/src/work/iterator_bfs_demo.cc Sun Mar 07 19:33:34 2004 +0000
2.2 +++ b/src/work/iterator_bfs_demo.cc Mon Mar 08 12:29:07 2004 +0000
2.3 @@ -7,16 +7,32 @@
2.4 #include <graph_wrapper.h>
2.5
2.6 using namespace hugo;
2.7 +using std::cout;
2.8 +using std::endl;
2.9 +using std::string;
2.10 +
2.11 +template <typename Graph, typename NodeNameMap>
2.12 +class EdgeNameMap {
2.13 + Graph& graph;
2.14 + NodeNameMap& node_name_map;
2.15 +public:
2.16 + EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) :
2.17 + graph(_graph), node_name_map(_node_name_map) { }
2.18 + string get(typename Graph::EdgeIt e) const {
2.19 + return
2.20 + (node_name_map.get(graph.tail(e))+"->"+node_name_map.get(graph.head(e)));
2.21 + }
2.22 +};
2.23
2.24 int main (int, char*[])
2.25 {
2.26 typedef ListGraph::NodeIt NodeIt;
2.27 typedef ListGraph::EdgeIt EdgeIt;
2.28 - typedef ListGraph::EachNodeIt EachNodeIt;
2.29 - typedef ListGraph::EachEdgeIt EachEdgeIt;
2.30 - typedef ListGraph::OutEdgeIt OutEdgeIt;
2.31 - typedef ListGraph::InEdgeIt InEdgeIt;
2.32 - typedef ListGraph::SymEdgeIt SymEdgeIt;
2.33 + //typedef ListGraph::EachNodeIt EachNodeIt;
2.34 + //typedef ListGraph::EachEdgeIt EachEdgeIt;
2.35 + //typedef ListGraph::OutEdgeIt OutEdgeIt;
2.36 + //typedef ListGraph::InEdgeIt InEdgeIt;
2.37 + //typedef ListGraph::SymEdgeIt SymEdgeIt;
2.38
2.39 ListGraph G;
2.40
2.41 @@ -27,6 +43,14 @@
2.42 NodeIt v4=G.addNode();
2.43 NodeIt t=G.addNode();
2.44
2.45 + ListGraph::NodeMap<string> node_name(G);
2.46 + node_name.set(s, "s");
2.47 + node_name.set(v1, "v1");
2.48 + node_name.set(v2, "v2");
2.49 + node_name.set(v3, "v3");
2.50 + node_name.set(v4, "v4");
2.51 + node_name.set(t, "t");
2.52 +
2.53 G.addEdge(s, v1);
2.54 G.addEdge(s, v2);
2.55 G.addEdge(v1, v2);
2.56 @@ -38,123 +62,317 @@
2.57 G.addEdge(v3, t);
2.58 G.addEdge(v4, t);
2.59
2.60 - std::cout << "bfs and dfs demo on the directed graph" << std::endl;
2.61 - for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
2.62 - std::cout << i << ": ";
2.63 - std::cout << "out edges: ";
2.64 - for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j)
2.65 - std::cout << j << " ";
2.66 - std::cout << "in edges: ";
2.67 - for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j)
2.68 - std::cout << j << " ";
2.69 - std::cout << std::endl;
2.70 + cout << " /--> -------------> "<< endl;
2.71 + cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
2.72 + cout << " / | | / /-> \\ "<< endl;
2.73 + cout << " / | | / | ^ \\ "<< endl;
2.74 + cout << "s | | / | | \\-> t "<< endl;
2.75 + cout << " \\ | | / | | /-> "<< endl;
2.76 + cout << " \\ | --/ / | | / "<< endl;
2.77 + cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
2.78 + cout << " \\--> -------------> "<< endl;
2.79 +
2.80 +/*
2.81 + {
2.82 + cout << "iterator bfs demo 4 ..." << endl;
2.83 + BfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G);
2.84 + bfs.pushAndSetReached(s);
2.85 + while (!bfs.finished()) {
2.86 + if (OutEdgeIt(bfs).valid()) {
2.87 + cout << "OutEdgeIt: " << bfs;
2.88 + cout << " aNode: " << G.aNode(bfs);
2.89 + cout << " bNode: " << G.bNode(bfs) << " ";
2.90 + } else {
2.91 + cout << "OutEdgeIt: " << "invalid";
2.92 + cout << " aNode: " << bfs.aNode();
2.93 + cout << " bNode: " << "invalid" << " ";
2.94 }
2.95 -
2.96 + if (bfs.isBNodeNewlyReached()) {
2.97 + cout << "bNodeIsNewlyReached ";
2.98 + } else {
2.99 + cout << "bNodeIsNotNewlyReached ";
2.100 + }
2.101 + if (bfs.isANodeExamined()) {
2.102 + cout << "aNodeIsExamined ";
2.103 + } else {
2.104 + cout << "aNodeIsNotExamined ";
2.105 + }
2.106 + cout << endl;
2.107 + ++bfs;
2.108 + }
2.109 + }
2.110 +
2.111 {
2.112 - std::cout << "iterator bfs demo 4 ..." << std::endl;
2.113 - BfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G);
2.114 + cout << "iterator dfs demo 4 ..." << endl;
2.115 + DfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > dfs(G);
2.116 + dfs.pushAndSetReached(s);
2.117 + while (!dfs.finished()) {
2.118 + ++dfs;
2.119 + if (OutEdgeIt(dfs).valid()) {
2.120 + cout << "OutEdgeIt: " << dfs;
2.121 + cout << " aNode: " << G.aNode(dfs);
2.122 + cout << " bNode: " << G.bNode(dfs) << " ";
2.123 + } else {
2.124 + cout << "OutEdgeIt: " << "invalid";
2.125 + cout << " aNode: " << dfs.aNode();
2.126 + cout << " bNode: " << "invalid" << " ";
2.127 + }
2.128 + if (dfs.isBNodeNewlyReached()) {
2.129 + cout << "bNodeIsNewlyReached ";
2.130 + } else {
2.131 + cout << "bNodeIsNotNewlyReached ";
2.132 + }
2.133 + if (dfs.isANodeExamined()) {
2.134 + cout << "aNodeIsExamined ";
2.135 + } else {
2.136 + cout << "aNodeIsNotExamined ";
2.137 + }
2.138 + cout << endl;
2.139 + //++dfs;
2.140 + }
2.141 + }
2.142 +*/
2.143 +
2.144 +// typedef TrivGraphWrapper<const ListGraph> CGW;
2.145 +// CGW wG(G);
2.146 +
2.147 +// cout << "bfs and dfs demo on the directed graph" << endl;
2.148 +// for(CGW::EachNodeIt n=wG.first<CGW::EachNodeIt>(); n.valid(); ++n) {
2.149 +// cout << n << ": ";
2.150 +// cout << "out edges: ";
2.151 +// for(CGW::OutEdgeIt e=wG.first<CGW::OutEdgeIt>(n); e.valid(); ++e)
2.152 +// cout << e << " ";
2.153 +// cout << "in edges: ";
2.154 +// for(CGW::InEdgeIt e=wG.first<CGW::InEdgeIt>(n); e.valid(); ++e)
2.155 +// cout << e << " ";
2.156 +// cout << endl;
2.157 +// }
2.158 +
2.159 + {
2.160 + typedef TrivGraphWrapper<const ListGraph> GW;
2.161 + GW wG(G);
2.162 +
2.163 + EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);
2.164 +
2.165 + cout << "bfs and dfs iterator demo on the directed graph" << endl;
2.166 + for(GW::EachNodeIt n=wG.first<GW::EachNodeIt>(); wG.valid(n); wG.next(n)) {
2.167 + cout << node_name.get(n) << ": ";
2.168 + cout << "out edges: ";
2.169 + for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e))
2.170 + cout << edge_name.get(e) << " ";
2.171 + cout << "in edges: ";
2.172 + for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e))
2.173 + cout << edge_name.get(e) << " ";
2.174 + cout << endl;
2.175 + }
2.176 +
2.177 + cout << "bfs from s ..." << endl;
2.178 + BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG);
2.179 bfs.pushAndSetReached(s);
2.180 while (!bfs.finished()) {
2.181 - if (OutEdgeIt(bfs).valid()) {
2.182 - std::cout << "OutEdgeIt: " << bfs;
2.183 - std::cout << " aNode: " << G.aNode(bfs);
2.184 - std::cout << " bNode: " << G.bNode(bfs) << " ";
2.185 + //cout << "edge: ";
2.186 + if (wG.valid(bfs)) {
2.187 + cout << edge_name.get(bfs) << /*endl*/", " <<
2.188 + /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) <<
2.189 + (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
2.190 + /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) <<
2.191 + (bfs.isBNodeNewlyReached() ? ": is newly reached." :
2.192 + ": is not newly reached.");
2.193 } else {
2.194 - std::cout << "OutEdgeIt: " << "invalid";
2.195 - std::cout << " aNode: " << bfs.aNode();
2.196 - std::cout << " bNode: " << "invalid" << " ";
2.197 + cout << "invalid" << /*endl*/", " <<
2.198 + /*" aNode: " <<*/ node_name.get(bfs.aNode()) <<
2.199 + (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
2.200 + /*" bNode: " <<*/
2.201 + "invalid.";
2.202 }
2.203 - if (bfs.isBNodeNewlyReached()) {
2.204 - std::cout << "bNodeIsNewlyReached ";
2.205 + cout << endl;
2.206 + ++bfs;
2.207 + }
2.208 +
2.209 + cout << " /--> -------------> "<< endl;
2.210 + cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
2.211 + cout << " / | | / /-> \\ "<< endl;
2.212 + cout << " / | | / | ^ \\ "<< endl;
2.213 + cout << "s | | / | | \\-> t "<< endl;
2.214 + cout << " \\ | | / | | /-> "<< endl;
2.215 + cout << " \\ | --/ / | | / "<< endl;
2.216 + cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
2.217 + cout << " \\--> -------------> "<< endl;
2.218 +
2.219 + cout << "dfs from s ..." << endl;
2.220 + DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG);
2.221 + dfs.pushAndSetReached(s);
2.222 + while (!dfs.finished()) {
2.223 + ++dfs;
2.224 + //cout << "edge: ";
2.225 + if (wG.valid(dfs)) {
2.226 + cout << edge_name.get(dfs) << /*endl*/", " <<
2.227 + /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) <<
2.228 + (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
2.229 + /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) <<
2.230 + (dfs.isBNodeNewlyReached() ? ": is newly reached." :
2.231 + ": is not newly reached.");
2.232 } else {
2.233 - std::cout << "bNodeIsNotNewlyReached ";
2.234 - }
2.235 - if (bfs.isANodeExamined()) {
2.236 - std::cout << "aNodeIsExamined ";
2.237 + cout << "invalid" << /*endl*/", " <<
2.238 + /*" aNode: " <<*/ node_name.get(dfs.aNode()) <<
2.239 + (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
2.240 + /*" bNode: " <<*/
2.241 + "invalid.";
2.242 + }
2.243 + cout << endl;
2.244 + }
2.245 + }
2.246 +
2.247 +
2.248 + {
2.249 + typedef RevGraphWrapper<const ListGraph> GW;
2.250 + GW wG(G);
2.251 +
2.252 + EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);
2.253 +
2.254 + cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;
2.255 + for(GW::EachNodeIt n=wG.first<GW::EachNodeIt>(); wG.valid(n); wG.next(n)) {
2.256 + cout << node_name.get(n) << ": ";
2.257 + cout << "out edges: ";
2.258 + for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e))
2.259 + cout << edge_name.get(e) << " ";
2.260 + cout << "in edges: ";
2.261 + for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e))
2.262 + cout << edge_name.get(e) << " ";
2.263 + cout << endl;
2.264 + }
2.265 +
2.266 + cout << "bfs from t ..." << endl;
2.267 + BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG);
2.268 + bfs.pushAndSetReached(t);
2.269 + while (!bfs.finished()) {
2.270 + //cout << "edge: ";
2.271 + if (wG.valid(bfs)) {
2.272 + cout << edge_name.get(bfs) << /*endl*/", " <<
2.273 + /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) <<
2.274 + (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
2.275 + /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) <<
2.276 + (bfs.isBNodeNewlyReached() ? ": is newly reached." :
2.277 + ": is not newly reached.");
2.278 } else {
2.279 - std::cout << "aNodeIsNotExamined ";
2.280 - }
2.281 - std::cout<<std::endl;
2.282 + cout << "invalid" << /*endl*/", " <<
2.283 + /*" aNode: " <<*/ node_name.get(bfs.aNode()) <<
2.284 + (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
2.285 + /*" bNode: " <<*/
2.286 + "invalid.";
2.287 + }
2.288 + cout << endl;
2.289 ++bfs;
2.290 }
2.291 +
2.292 + cout << " /--> -------------> "<< endl;
2.293 + cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
2.294 + cout << " / | | / /-> \\ "<< endl;
2.295 + cout << " / | | / | ^ \\ "<< endl;
2.296 + cout << "s | | / | | \\-> t "<< endl;
2.297 + cout << " \\ | | / | | /-> "<< endl;
2.298 + cout << " \\ | --/ / | | / "<< endl;
2.299 + cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
2.300 + cout << " \\--> -------------> "<< endl;
2.301 +
2.302 + cout << "dfs from t ..." << endl;
2.303 + DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG);
2.304 + dfs.pushAndSetReached(t);
2.305 + while (!dfs.finished()) {
2.306 + ++dfs;
2.307 + //cout << "edge: ";
2.308 + if (wG.valid(dfs)) {
2.309 + cout << edge_name.get(dfs) << /*endl*/", " <<
2.310 + /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) <<
2.311 + (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
2.312 + /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) <<
2.313 + (dfs.isBNodeNewlyReached() ? ": is newly reached." :
2.314 + ": is not newly reached.");
2.315 + } else {
2.316 + cout << "invalid" << /*endl*/", " <<
2.317 + /*" aNode: " <<*/ node_name.get(dfs.aNode()) <<
2.318 + (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
2.319 + /*" bNode: " <<*/
2.320 + "invalid.";
2.321 + }
2.322 + cout << endl;
2.323 + }
2.324 }
2.325
2.326 {
2.327 - std::cout << "iterator dfs demo 4 ..." << std::endl;
2.328 - DfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > dfs(G);
2.329 - dfs.pushAndSetReached(s);
2.330 + typedef UndirGraphWrapper<const ListGraph> GW;
2.331 + GW wG(G);
2.332 +
2.333 + EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);
2.334 +
2.335 + cout << "bfs and dfs iterator demo on the undirected graph" << endl;
2.336 + for(GW::EachNodeIt n=wG.first<GW::EachNodeIt>(); wG.valid(n); wG.next(n)) {
2.337 + cout << node_name.get(n) << ": ";
2.338 + cout << "out edges: ";
2.339 + for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e))
2.340 + cout << edge_name.get(e) << " ";
2.341 + cout << "in edges: ";
2.342 + for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e))
2.343 + cout << edge_name.get(e) << " ";
2.344 + cout << endl;
2.345 + }
2.346 +
2.347 + cout << "bfs from t ..." << endl;
2.348 + BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG);
2.349 + bfs.pushAndSetReached(t);
2.350 + while (!bfs.finished()) {
2.351 + //cout << "edge: ";
2.352 + if (wG.valid(GW::OutEdgeIt(bfs))) {
2.353 + cout << edge_name.get(GW::OutEdgeIt(bfs)) << /*endl*/", " <<
2.354 + /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) <<
2.355 + (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
2.356 + /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) <<
2.357 + (bfs.isBNodeNewlyReached() ? ": is newly reached." :
2.358 + ": is not newly reached.");
2.359 + } else {
2.360 + cout << "invalid" << /*endl*/", " <<
2.361 + /*" aNode: " <<*/ node_name.get(bfs.aNode()) <<
2.362 + (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
2.363 + /*" bNode: " <<*/
2.364 + "invalid.";
2.365 + }
2.366 + cout << endl;
2.367 + ++bfs;
2.368 + }
2.369 +
2.370 + cout << " /--> -------------> "<< endl;
2.371 + cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
2.372 + cout << " / | | / /-> \\ "<< endl;
2.373 + cout << " / | | / | ^ \\ "<< endl;
2.374 + cout << "s | | / | | \\-> t "<< endl;
2.375 + cout << " \\ | | / | | /-> "<< endl;
2.376 + cout << " \\ | --/ / | | / "<< endl;
2.377 + cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
2.378 + cout << " \\--> -------------> "<< endl;
2.379 +
2.380 + cout << "dfs from t ..." << endl;
2.381 + DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG);
2.382 + dfs.pushAndSetReached(t);
2.383 while (!dfs.finished()) {
2.384 ++dfs;
2.385 - if (OutEdgeIt(dfs).valid()) {
2.386 - std::cout << "OutEdgeIt: " << dfs;
2.387 - std::cout << " aNode: " << G.aNode(dfs);
2.388 - std::cout << " bNode: " << G.bNode(dfs) << " ";
2.389 + //cout << "edge: ";
2.390 + if (wG.valid(GW::OutEdgeIt(dfs))) {
2.391 + cout << edge_name.get(GW::OutEdgeIt(dfs)) << /*endl*/", " <<
2.392 + /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) <<
2.393 + (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
2.394 + /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) <<
2.395 + (dfs.isBNodeNewlyReached() ? ": is newly reached." :
2.396 + ": is not newly reached.");
2.397 } else {
2.398 - std::cout << "OutEdgeIt: " << "invalid";
2.399 - std::cout << " aNode: " << dfs.aNode();
2.400 - std::cout << " bNode: " << "invalid" << " ";
2.401 + cout << "invalid" << /*endl*/", " <<
2.402 + /*" aNode: " <<*/ node_name.get(dfs.aNode()) <<
2.403 + (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
2.404 + /*" bNode: " <<*/
2.405 + "invalid.";
2.406 }
2.407 - if (dfs.isBNodeNewlyReached()) {
2.408 - std::cout << "bNodeIsNewlyReached ";
2.409 - } else {
2.410 - std::cout << "bNodeIsNotNewlyReached ";
2.411 - }
2.412 - if (dfs.isANodeExamined()) {
2.413 - std::cout << "aNodeIsExamined ";
2.414 - } else {
2.415 - std::cout << "aNodeIsNotExamined ";
2.416 - }
2.417 - std::cout<<std::endl;
2.418 - //++dfs;
2.419 + cout << endl;
2.420 }
2.421 }
2.422
2.423 -
2.424 - typedef ConstTrivGraphWrapper<ListGraph> CTGW;
2.425 - CTGW wG(G);
2.426 -
2.427 - std::cout << "bfs and dfs demo on the directed graph" << std::endl;
2.428 - for(CTGW::EachNodeIt i=wG.first<CTGW::EachNodeIt>(); i.valid(); ++i) {
2.429 - std::cout << i << ": ";
2.430 - std::cout << "out edges: ";
2.431 - for(CTGW::OutEdgeIt j=wG.first<CTGW::OutEdgeIt>(i); j.valid(); ++j)
2.432 - std::cout << j << " ";
2.433 - std::cout << "in edges: ";
2.434 - for(CTGW::InEdgeIt j=wG.first<CTGW::InEdgeIt>(i); j.valid(); ++j)
2.435 - std::cout << j << " ";
2.436 - std::cout << std::endl;
2.437 - }
2.438 -
2.439 -
2.440 - {
2.441 - std::cout << "iterator bfs demo 5 ..." << std::endl;
2.442 - BfsIterator5< CTGW, CTGW::NodeMap<bool> > bfs(wG);
2.443 - bfs.pushAndSetReached(s);
2.444 - while (!bfs.finished()) {
2.445 - if (OutEdgeIt(bfs).valid()) {
2.446 - std::cout << "OutEdgeIt: " << bfs;
2.447 - std::cout << " aNode: " << wG.aNode(bfs);
2.448 - std::cout << " bNode: " << wG.bNode(bfs) << " ";
2.449 - } else {
2.450 - std::cout << "OutEdgeIt: " << "invalid";
2.451 - std::cout << " aNode: " << bfs.aNode();
2.452 - std::cout << " bNode: " << "invalid" << " ";
2.453 - }
2.454 - if (bfs.isBNodeNewlyReached()) {
2.455 - std::cout << "bNodeIsNewlyReached ";
2.456 - } else {
2.457 - std::cout << "bNodeIsNotNewlyReached ";
2.458 - }
2.459 - if (bfs.isANodeExamined()) {
2.460 - std::cout << "aNodeIsExamined ";
2.461 - } else {
2.462 - std::cout << "aNodeIsNotExamined ";
2.463 - }
2.464 - std::cout<<std::endl;
2.465 - ++bfs;
2.466 - }
2.467 - }
2.468 -
2.469 -
2.470 return 0;
2.471 }
3.1 --- a/src/work/marci/graph_wrapper.h Sun Mar 07 19:33:34 2004 +0000
3.2 +++ b/src/work/marci/graph_wrapper.h Mon Mar 08 12:29:07 2004 +0000
3.3 @@ -62,16 +62,16 @@
3.4 template<typename T> class NodeMap : public Graph::NodeMap<T> {
3.5 public:
3.6 NodeMap(const TrivGraphWrapper<Graph>& _G) :
3.7 - Graph::NodeMap<T>(*(_G.G)) { }
3.8 + Graph::NodeMap<T>(_G.getGraph()) { }
3.9 NodeMap(const TrivGraphWrapper<Graph>& _G, T a) :
3.10 - Graph::NodeMap<T>(*(_G.G), a) { }
3.11 + Graph::NodeMap<T>(_G.getGraph(), a) { }
3.12 };
3.13 template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
3.14 public:
3.15 EdgeMap(const TrivGraphWrapper<Graph>& _G) :
3.16 - Graph::EdgeMap<T>(*(_G.G)) { }
3.17 + Graph::EdgeMap<T>(_G.getGraph()) { }
3.18 EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) :
3.19 - Graph::EdgeMap<T>(*(_G.G), a) { }
3.20 + Graph::EdgeMap<T>(_G.getGraph(), a) { }
3.21 };
3.22
3.23 void setGraph(Graph& _graph) { graph = &_graph; }
3.24 @@ -140,16 +140,16 @@
3.25 template<typename T> class NodeMap : public Graph::NodeMap<T> {
3.26 public:
3.27 NodeMap(const RevGraphWrapper<Graph>& _G) :
3.28 - Graph::NodeMap<T>(*(_G.G)) { }
3.29 + Graph::NodeMap<T>(_G.getGraph()) { }
3.30 NodeMap(const RevGraphWrapper<Graph>& _G, T a) :
3.31 - Graph::NodeMap<T>(*(_G.G), a) { }
3.32 + Graph::NodeMap<T>(_G.getGraph(), a) { }
3.33 };
3.34 template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
3.35 public:
3.36 EdgeMap(const RevGraphWrapper<Graph>& _G) :
3.37 - Graph::EdgeMap<T>(*(_G.G)) { }
3.38 + Graph::EdgeMap<T>(_G.getGraph()) { }
3.39 EdgeMap(const RevGraphWrapper<Graph>& _G, T a) :
3.40 - Graph::EdgeMap<T>(*(_G.G), a) { }
3.41 + Graph::EdgeMap<T>(_G.getGraph(), a) { }
3.42 };
3.43
3.44 void setGraph(Graph& _graph) { graph = &_graph; }
3.45 @@ -160,6 +160,150 @@
3.46 };
3.47
3.48
3.49 + template<typename Graph>
3.50 + class UndirGraphWrapper {
3.51 + Graph* graph;
3.52 +
3.53 + public:
3.54 + typedef Graph BaseGraph;
3.55 +
3.56 + typedef typename Graph::NodeIt NodeIt;
3.57 + typedef typename Graph::EachNodeIt EachNodeIt;
3.58 +
3.59 + //typedef typename Graph::EdgeIt EdgeIt;
3.60 + //typedef typename Graph::OutEdgeIt OutEdgeIt;
3.61 + //typedef typename Graph::InEdgeIt InEdgeIt;
3.62 + //typedef typename Graph::SymEdgeIt SymEdgeIt;
3.63 + //typedef typename Graph::EachEdgeIt EachEdgeIt;
3.64 +
3.65 + //private:
3.66 + typedef typename Graph::EdgeIt GraphEdgeIt;
3.67 + typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
3.68 + typedef typename Graph::InEdgeIt GraphInEdgeIt;
3.69 + //public:
3.70 +
3.71 + class EdgeIt {
3.72 + friend class UndirGraphWrapper<Graph>;
3.73 + bool out_or_in; //true iff out
3.74 + GraphOutEdgeIt out;
3.75 + GraphInEdgeIt in;
3.76 + public:
3.77 + EdgeIt() : out_or_in(true), out(), in() { }
3.78 + operator GraphEdgeIt() const {
3.79 + if (out_or_in) return(out); else return(in);
3.80 + }
3.81 + };
3.82 +
3.83 + class OutEdgeIt : public EdgeIt {
3.84 + friend class UndirGraphWrapper<Graph>;
3.85 + //bool out_or_in; //true iff out
3.86 + //GraphOutEdgeIt out;
3.87 + //GraphInEdgeIt in;
3.88 + public:
3.89 + OutEdgeIt() : EdgeIt() { }
3.90 + OutEdgeIt(const UndirGraphWrapper& _G, const NodeIt& n) : EdgeIt() {
3.91 + _G.graph->getFirst(out, n);
3.92 + if (!(_G.graph->valid(out))) {
3.93 + out_or_in=false;
3.94 + _G.graph->getFirst(in, n);
3.95 + }
3.96 + }
3.97 + };
3.98 +
3.99 + OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const {
3.100 + e.out_or_in=true;
3.101 + graph->getFirst(e.out, n);
3.102 + if (!(graph->valid(e.out))) {
3.103 + e.out_or_in=false;
3.104 + graph->getFirst(e.in, n);
3.105 + }
3.106 + return e;
3.107 + }
3.108 +
3.109 + OutEdgeIt& next(OutEdgeIt& e) const {
3.110 + if (e.out_or_in) {
3.111 + NodeIt n=graph->tail(e.out);
3.112 + graph->next(e.out);
3.113 + if (!graph->valid(e.out)) {
3.114 + e.out_or_in=false;
3.115 + graph->getFirst(e.in, n);
3.116 + }
3.117 + } else {
3.118 + graph->next(e.in);
3.119 + }
3.120 + return e;
3.121 + }
3.122 +
3.123 + NodeIt aNode(const OutEdgeIt& e) const {
3.124 + if (e.out_or_in) return graph->tail(e); else return graph->head(e); }
3.125 + NodeIt bNode(const OutEdgeIt& e) const {
3.126 + if (e.out_or_in) return graph->head(e); else return graph->tail(e); }
3.127 +
3.128 + typedef OutEdgeIt InEdgeIt;
3.129 +
3.130 + template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
3.131 +// template<typename I, typename P> I& getFirst(I& i, const P& p) const {
3.132 +// return graph->getFirst(i, p); }
3.133 +
3.134 + template<typename I> I getNext(const I& i) const {
3.135 + return graph->getNext(i); }
3.136 + template<typename I> I& next(I &i) const { return graph->next(i); }
3.137 +
3.138 + template< typename It > It first() const {
3.139 + It e; getFirst(e); return e; }
3.140 +
3.141 + template< typename It > It first(const NodeIt& v) const {
3.142 + It e; getFirst(e, v); return e; }
3.143 +
3.144 + NodeIt head(const EdgeIt& e) const { return graph->head(e); }
3.145 + NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
3.146 +
3.147 + template<typename I> bool valid(const I& i) const
3.148 + { return graph->valid(i); }
3.149 +
3.150 + //template<typename I> void setInvalid(const I &i);
3.151 + //{ return graph->setInvalid(i); }
3.152 +
3.153 + int nodeNum() const { return graph->nodeNum(); }
3.154 + int edgeNum() const { return graph->edgeNum(); }
3.155 +
3.156 +// template<typename I> NodeIt aNode(const I& e) const {
3.157 +// return graph->aNode(e); }
3.158 +// template<typename I> NodeIt bNode(const I& e) const {
3.159 +// return graph->bNode(e); }
3.160 +
3.161 + NodeIt addNode() const { return graph->addNode(); }
3.162 + EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
3.163 + return graph->addEdge(tail, head); }
3.164 +
3.165 + template<typename I> void erase(const I& i) const { graph->erase(i); }
3.166 +
3.167 + void clear() const { graph->clear(); }
3.168 +
3.169 + template<typename T> class NodeMap : public Graph::NodeMap<T> {
3.170 + public:
3.171 + NodeMap(const UndirGraphWrapper<Graph>& _G) :
3.172 + Graph::NodeMap<T>(_G.getGraph()) { }
3.173 + NodeMap(const UndirGraphWrapper<Graph>& _G, T a) :
3.174 + Graph::NodeMap<T>(_G.getGraph(), a) { }
3.175 + };
3.176 + template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
3.177 + public:
3.178 + EdgeMap(const UndirGraphWrapper<Graph>& _G) :
3.179 + Graph::EdgeMap<T>(_G.getGraph()) { }
3.180 + EdgeMap(const UndirGraphWrapper<Graph>& _G, T a) :
3.181 + Graph::EdgeMap<T>(_G.getGraph(), a) { }
3.182 + };
3.183 +
3.184 + void setGraph(Graph& _graph) { graph = &_graph; }
3.185 + Graph& getGraph() const { return (*graph); }
3.186 +
3.187 + //TrivGraphWrapper() : graph(0) { }
3.188 + UndirGraphWrapper(Graph& _graph) : graph(&_graph) { }
3.189 + };
3.190 +
3.191 +
3.192 +
3.193 // template<typename Graph>
3.194 // class SymGraphWrapper
3.195 // {
3.196 @@ -247,6 +391,8 @@
3.197 G(&_G), flow(&_flow), capacity(&_capacity) { }
3.198 // ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) :
3.199 // G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { }
3.200 + void setGraph(Graph& _graph) { graph = &_graph; }
3.201 + Graph& getGraph() const { return (*graph); }
3.202 class EdgeIt;
3.203 class OutEdgeIt;
3.204 friend class EdgeIt;
3.205 @@ -499,9 +645,9 @@
3.206 template<typename T> class NodeMap : public Graph::NodeMap<T> {
3.207 public:
3.208 NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
3.209 - : Graph::NodeMap<T>(*(_G.G)) { }
3.210 + : Graph::NodeMap<T>(_G.getGraph()) { }
3.211 NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,
3.212 - T a) : Graph::NodeMap<T>(*(_G.G), a) { }
3.213 + T a) : Graph::NodeMap<T>(_G.getGraph(), a) { }
3.214 };
3.215
3.216 // template <typename T>
3.217 @@ -518,8 +664,8 @@
3.218 class EdgeMap {
3.219 typename Graph::EdgeMap<T> forward_map, backward_map;
3.220 public:
3.221 - EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.G)), backward_map(*(_G.G)) { }
3.222 - EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.G), a), backward_map(*(_G.G), a) { }
3.223 + EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.getGraph()), backward_map(_G.getGraph()) { }
3.224 + EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.getGraph(), a), backward_map(_G.getGraph(), a) { }
3.225 void set(EdgeIt e, T a) {
3.226 if (e.out_or_in)
3.227 forward_map.set(e.out, a);