src/work/bfs_iterator.hh
author jacint
Tue, 17 Feb 2004 11:16:39 +0000
changeset 85 15362fafaf1a
parent 64 72bd463289a9
child 99 f26897fb91fd
permissions -rw-r--r--
*** empty log message ***
marci@58
     1
#ifndef BFS_ITERATOR_HH
marci@58
     2
#define BFS_ITERATOR_HH
marci@42
     3
marci@42
     4
#include <queue>
marci@42
     5
#include <stack>
marci@75
     6
#include <utility>
marci@75
     7
#include <graph_wrapper.h>
marci@42
     8
marci@42
     9
namespace marci {
marci@42
    10
marci@42
    11
  template <typename Graph>
marci@42
    12
  struct bfs {
marci@42
    13
    typedef typename Graph::NodeIt NodeIt;
marci@42
    14
    typedef typename Graph::EdgeIt EdgeIt;
marci@42
    15
    typedef typename Graph::EachNodeIt EachNodeIt;
marci@42
    16
    typedef typename Graph::OutEdgeIt OutEdgeIt;
marci@42
    17
    Graph& G;
marci@42
    18
    NodeIt s;
marci@42
    19
    typename Graph::NodeMap<bool> reached;
marci@42
    20
    typename Graph::NodeMap<EdgeIt> pred;
marci@42
    21
    typename Graph::NodeMap<int> dist;
marci@42
    22
    std::queue<NodeIt> bfs_queue;
marci@42
    23
    bfs(Graph& _G, NodeIt _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) { 
marci@42
    24
      bfs_queue.push(s); 
marci@42
    25
      for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) 
marci@42
    26
	reached.set(i, false);
marci@42
    27
      reached.set(s, true);
marci@42
    28
      dist.set(s, 0); 
marci@42
    29
    }
marci@42
    30
    
marci@42
    31
    void run() {
marci@42
    32
      while (!bfs_queue.empty()) {
marci@42
    33
	NodeIt v=bfs_queue.front();
marci@42
    34
	OutEdgeIt e=G.template first<OutEdgeIt>(v);
marci@42
    35
	bfs_queue.pop();
marci@42
    36
	for( ; e.valid(); ++e) {
marci@42
    37
	  NodeIt w=G.bNode(e);
marci@42
    38
	  std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;
marci@42
    39
	  if (!reached.get(w)) {
marci@42
    40
	    std::cout << G.id(w) << " is newly reached :-)" << std::endl;
marci@42
    41
	    bfs_queue.push(w);
marci@42
    42
	    dist.set(w, dist.get(v)+1);
marci@42
    43
	    pred.set(w, e);
marci@42
    44
	    reached.set(w, true);
marci@42
    45
	  } else {
marci@42
    46
	    std::cout << G.id(w) << " is already reached" << std::endl;
marci@42
    47
	  }
marci@42
    48
	}
marci@42
    49
      }
marci@42
    50
    }
marci@42
    51
  };
marci@42
    52
marci@42
    53
  template <typename Graph> 
marci@42
    54
  struct bfs_visitor {
marci@42
    55
    typedef typename Graph::NodeIt NodeIt;
marci@42
    56
    typedef typename Graph::EdgeIt EdgeIt;
marci@42
    57
    typedef typename Graph::OutEdgeIt OutEdgeIt;
marci@42
    58
    Graph& G;
marci@42
    59
    bfs_visitor(Graph& _G) : G(_G) { }
marci@42
    60
    void at_previously_reached(OutEdgeIt& e) { 
marci@42
    61
      //NodeIt v=G.aNode(e);
marci@42
    62
      NodeIt w=G.bNode(e);
marci@42
    63
      std::cout << G.id(w) << " is already reached" << std::endl;
marci@42
    64
   }
marci@42
    65
    void at_newly_reached(OutEdgeIt& e) { 
marci@42
    66
      //NodeIt v=G.aNode(e);
marci@42
    67
      NodeIt w=G.bNode(e);
marci@42
    68
      std::cout << G.id(w) << " is newly reached :-)" << std::endl;
marci@42
    69
    }
marci@42
    70
  };
marci@42
    71
marci@42
    72
  template <typename Graph, typename ReachedMap, typename visitor_type>
marci@42
    73
  struct bfs_iterator {
marci@42
    74
    typedef typename Graph::NodeIt NodeIt;
marci@42
    75
    typedef typename Graph::EdgeIt EdgeIt;
marci@42
    76
    typedef typename Graph::OutEdgeIt OutEdgeIt;
marci@42
    77
    Graph& G;
marci@42
    78
    std::queue<OutEdgeIt>& bfs_queue;
marci@42
    79
    ReachedMap& reached;
marci@42
    80
    visitor_type& visitor;
marci@42
    81
    void process() {
marci@42
    82
      while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
marci@42
    83
      if (bfs_queue.empty()) return;
marci@42
    84
      OutEdgeIt e=bfs_queue.front();
marci@42
    85
      //NodeIt v=G.aNode(e);
marci@42
    86
      NodeIt w=G.bNode(e);
marci@42
    87
      if (!reached.get(w)) {
marci@42
    88
	visitor.at_newly_reached(e);
marci@42
    89
	bfs_queue.push(G.template first<OutEdgeIt>(w));
marci@42
    90
	reached.set(w, true);
marci@42
    91
      } else {
marci@42
    92
	visitor.at_previously_reached(e);
marci@42
    93
      }
marci@42
    94
    }
marci@42
    95
    bfs_iterator(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached, visitor_type& _visitor) : G(_G), bfs_queue(_bfs_queue), reached(_reached), visitor(_visitor) { 
marci@42
    96
      //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
marci@42
    97
      valid();
marci@42
    98
    }
marci@42
    99
    bfs_iterator<Graph, ReachedMap, visitor_type>& operator++() { 
marci@42
   100
      //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
marci@42
   101
      //if (bfs_queue.empty()) return *this;
marci@42
   102
      if (!valid()) return *this;
marci@42
   103
      ++(bfs_queue.front());
marci@42
   104
      //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
marci@42
   105
      valid();
marci@42
   106
      return *this;
marci@42
   107
    }
marci@42
   108
    //void next() { 
marci@42
   109
    //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
marci@42
   110
    //  if (bfs_queue.empty()) return;
marci@42
   111
    //  ++(bfs_queue.front());
marci@42
   112
    //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
marci@42
   113
    //}
marci@42
   114
    bool valid() { 
marci@42
   115
      while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
marci@42
   116
      if (bfs_queue.empty()) return false; else return true;
marci@42
   117
    }
marci@42
   118
    //bool finished() { 
marci@42
   119
    //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
marci@42
   120
    //  if (bfs_queue.empty()) return true; else return false;
marci@42
   121
    //}
marci@42
   122
    operator EdgeIt () { return bfs_queue.front(); }
marci@42
   123
marci@42
   124
  };
marci@42
   125
marci@42
   126
  template <typename Graph, typename ReachedMap>
marci@42
   127
  struct bfs_iterator1 {
marci@42
   128
    typedef typename Graph::NodeIt NodeIt;
marci@42
   129
    typedef typename Graph::EdgeIt EdgeIt;
marci@42
   130
    typedef typename Graph::OutEdgeIt OutEdgeIt;
marci@42
   131
    Graph& G;
marci@42
   132
    std::queue<OutEdgeIt>& bfs_queue;
marci@42
   133
    ReachedMap& reached;
marci@42
   134
    bool _newly_reached;
marci@42
   135
    bfs_iterator1(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) { 
marci@42
   136
      valid();
marci@42
   137
      if (!bfs_queue.empty() && bfs_queue.front().valid()) { 
marci@42
   138
	OutEdgeIt e=bfs_queue.front();
marci@42
   139
	NodeIt w=G.bNode(e);
marci@42
   140
	if (!reached.get(w)) {
marci@42
   141
	  bfs_queue.push(G.template first<OutEdgeIt>(w));
marci@42
   142
	  reached.set(w, true);
marci@42
   143
	  _newly_reached=true;
marci@42
   144
	} else {
marci@42
   145
	  _newly_reached=false;
marci@42
   146
	}
marci@42
   147
      }
marci@42
   148
    }
marci@42
   149
    bfs_iterator1<Graph, ReachedMap>& operator++() { 
marci@42
   150
      if (!valid()) return *this;
marci@42
   151
      ++(bfs_queue.front());
marci@42
   152
      valid();
marci@42
   153
      if (!bfs_queue.empty() && bfs_queue.front().valid()) { 
marci@42
   154
	OutEdgeIt e=bfs_queue.front();
marci@42
   155
	NodeIt w=G.bNode(e);
marci@42
   156
	if (!reached.get(w)) {
marci@42
   157
	  bfs_queue.push(G.template first<OutEdgeIt>(w));
marci@42
   158
	  reached.set(w, true);
marci@42
   159
	  _newly_reached=true;
marci@42
   160
	} else {
marci@42
   161
	  _newly_reached=false;
marci@42
   162
	}
marci@42
   163
      }
marci@42
   164
      return *this;
marci@42
   165
    }
marci@42
   166
    bool valid() { 
marci@42
   167
      while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
marci@42
   168
      if (bfs_queue.empty()) return false; else return true;
marci@42
   169
    }
marci@42
   170
    operator OutEdgeIt() { return bfs_queue.front(); }
marci@42
   171
    //ize
marci@42
   172
    bool newly_reached() { return _newly_reached; }
marci@42
   173
marci@42
   174
  };
marci@42
   175
marci@42
   176
  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
marci@42
   177
  struct BfsIterator {
marci@42
   178
    typedef typename Graph::NodeIt NodeIt;
marci@42
   179
    Graph& G;
marci@42
   180
    std::queue<OutEdgeIt>& bfs_queue;
marci@42
   181
    ReachedMap& reached;
marci@42
   182
    bool b_node_newly_reached;
marci@42
   183
    OutEdgeIt actual_edge;
marci@42
   184
    BfsIterator(Graph& _G, 
marci@42
   185
		std::queue<OutEdgeIt>& _bfs_queue, 
marci@42
   186
		ReachedMap& _reached) : 
marci@42
   187
      G(_G), bfs_queue(_bfs_queue), reached(_reached) { 
marci@42
   188
      actual_edge=bfs_queue.front();
marci@42
   189
      if (actual_edge.valid()) { 
marci@42
   190
	NodeIt w=G.bNode(actual_edge);
marci@42
   191
	if (!reached.get(w)) {
marci@42
   192
	  bfs_queue.push(G.firstOutEdge(w));
marci@42
   193
	  reached.set(w, true);
marci@42
   194
	  b_node_newly_reached=true;
marci@42
   195
	} else {
marci@42
   196
	  b_node_newly_reached=false;
marci@42
   197
	}
marci@42
   198
      }
marci@42
   199
    }
marci@42
   200
    BfsIterator<Graph, OutEdgeIt, ReachedMap>& 
marci@42
   201
    operator++() { 
marci@42
   202
      if (bfs_queue.front().valid()) { 
marci@42
   203
	++(bfs_queue.front());
marci@42
   204
	actual_edge=bfs_queue.front();
marci@42
   205
	if (actual_edge.valid()) {
marci@42
   206
	  NodeIt w=G.bNode(actual_edge);
marci@42
   207
	  if (!reached.get(w)) {
marci@42
   208
	    bfs_queue.push(G.firstOutEdge(w));
marci@42
   209
	    reached.set(w, true);
marci@42
   210
	    b_node_newly_reached=true;
marci@42
   211
	  } else {
marci@42
   212
	    b_node_newly_reached=false;
marci@42
   213
	  }
marci@42
   214
	}
marci@42
   215
      } else {
marci@42
   216
	bfs_queue.pop(); 
marci@42
   217
	actual_edge=bfs_queue.front();
marci@42
   218
	if (actual_edge.valid()) {
marci@42
   219
	  NodeIt w=G.bNode(actual_edge);
marci@42
   220
	  if (!reached.get(w)) {
marci@42
   221
	    bfs_queue.push(G.firstOutEdge(w));
marci@42
   222
	    reached.set(w, true);
marci@42
   223
	    b_node_newly_reached=true;
marci@42
   224
	  } else {
marci@42
   225
	    b_node_newly_reached=false;
marci@42
   226
	  }
marci@42
   227
	}
marci@42
   228
      }
marci@42
   229
      return *this;
marci@42
   230
    }
marci@42
   231
    bool finished() { return bfs_queue.empty(); }
marci@42
   232
    operator OutEdgeIt () { return actual_edge; }
marci@42
   233
    bool bNodeIsNewlyReached() { return b_node_newly_reached; }
marci@42
   234
    bool aNodeIsExamined() { return !(actual_edge.valid()); }
marci@42
   235
  };
marci@42
   236
marci@42
   237
marci@42
   238
  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
marci@42
   239
  struct DfsIterator {
marci@42
   240
    typedef typename Graph::NodeIt NodeIt;
marci@42
   241
    Graph& G;
marci@42
   242
    std::stack<OutEdgeIt>& bfs_queue;
marci@42
   243
    ReachedMap& reached;
marci@42
   244
    bool b_node_newly_reached;
marci@42
   245
    OutEdgeIt actual_edge;
marci@42
   246
    DfsIterator(Graph& _G, 
marci@42
   247
		std::stack<OutEdgeIt>& _bfs_queue, 
marci@42
   248
		ReachedMap& _reached) : 
marci@42
   249
      G(_G), bfs_queue(_bfs_queue), reached(_reached) { 
marci@42
   250
      actual_edge=bfs_queue.top();
marci@42
   251
      if (actual_edge.valid()) { 
marci@42
   252
	NodeIt w=G.bNode(actual_edge);
marci@42
   253
	if (!reached.get(w)) {
marci@42
   254
	  bfs_queue.push(G.firstOutEdge(w));
marci@42
   255
	  reached.set(w, true);
marci@42
   256
	  b_node_newly_reached=true;
marci@42
   257
	} else {
marci@42
   258
	  ++(bfs_queue.top());
marci@42
   259
	  b_node_newly_reached=false;
marci@42
   260
	}
marci@42
   261
      } else {
marci@42
   262
	bfs_queue.pop();
marci@42
   263
      }
marci@42
   264
    }
marci@42
   265
    DfsIterator<Graph, OutEdgeIt, ReachedMap>& 
marci@42
   266
    operator++() { 
marci@42
   267
      actual_edge=bfs_queue.top();
marci@42
   268
      if (actual_edge.valid()) { 
marci@42
   269
	NodeIt w=G.bNode(actual_edge);
marci@42
   270
	if (!reached.get(w)) {
marci@42
   271
	  bfs_queue.push(G.firstOutEdge(w));
marci@42
   272
	  reached.set(w, true);
marci@42
   273
	  b_node_newly_reached=true;
marci@42
   274
	} else {
marci@42
   275
	  ++(bfs_queue.top());
marci@42
   276
	  b_node_newly_reached=false;
marci@42
   277
	}
marci@42
   278
      } else {
marci@42
   279
	bfs_queue.pop();
marci@42
   280
      }
marci@42
   281
      return *this;
marci@42
   282
    }
marci@42
   283
    bool finished() { return bfs_queue.empty(); }
marci@42
   284
    operator OutEdgeIt () { return actual_edge; }
marci@42
   285
    bool bNodeIsNewlyReached() { return b_node_newly_reached; }
marci@42
   286
    bool aNodeIsLeaved() { return !(actual_edge.valid()); }
marci@42
   287
  };
marci@42
   288
marci@42
   289
  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
marci@42
   290
  struct BfsIterator1 {
marci@42
   291
    typedef typename Graph::NodeIt NodeIt;
marci@42
   292
    Graph& G;
marci@42
   293
    std::queue<OutEdgeIt>& bfs_queue;
marci@42
   294
    ReachedMap& reached;
marci@42
   295
    bool b_node_newly_reached;
marci@42
   296
    OutEdgeIt actual_edge;
marci@42
   297
    BfsIterator1(Graph& _G, 
marci@42
   298
		std::queue<OutEdgeIt>& _bfs_queue, 
marci@42
   299
		ReachedMap& _reached) : 
marci@42
   300
      G(_G), bfs_queue(_bfs_queue), reached(_reached) { 
marci@42
   301
      actual_edge=bfs_queue.front();
marci@42
   302
      if (actual_edge.valid()) { 
marci@42
   303
      	NodeIt w=G.bNode(actual_edge);
marci@42
   304
	if (!reached.get(w)) {
marci@42
   305
	  bfs_queue.push(OutEdgeIt(G, w));
marci@42
   306
	  reached.set(w, true);
marci@42
   307
	  b_node_newly_reached=true;
marci@42
   308
	} else {
marci@42
   309
	  b_node_newly_reached=false;
marci@42
   310
	}
marci@42
   311
      }
marci@42
   312
    }
marci@42
   313
    void next() { 
marci@42
   314
      if (bfs_queue.front().valid()) { 
marci@42
   315
	++(bfs_queue.front());
marci@42
   316
	actual_edge=bfs_queue.front();
marci@42
   317
	if (actual_edge.valid()) {
marci@42
   318
	  NodeIt w=G.bNode(actual_edge);
marci@42
   319
	  if (!reached.get(w)) {
marci@42
   320
	    bfs_queue.push(OutEdgeIt(G, w));
marci@42
   321
	    reached.set(w, true);
marci@42
   322
	    b_node_newly_reached=true;
marci@42
   323
	  } else {
marci@42
   324
	    b_node_newly_reached=false;
marci@42
   325
	  }
marci@42
   326
	}
marci@42
   327
      } else {
marci@42
   328
	bfs_queue.pop(); 
marci@42
   329
	actual_edge=bfs_queue.front();
marci@42
   330
	if (actual_edge.valid()) {
marci@42
   331
	  NodeIt w=G.bNode(actual_edge);
marci@42
   332
	  if (!reached.get(w)) {
marci@42
   333
	    bfs_queue.push(OutEdgeIt(G, w));
marci@42
   334
	    reached.set(w, true);
marci@42
   335
	    b_node_newly_reached=true;
marci@42
   336
	  } else {
marci@42
   337
	    b_node_newly_reached=false;
marci@42
   338
	  }
marci@42
   339
	}
marci@42
   340
      }
marci@42
   341
      //return *this;
marci@42
   342
    }
marci@42
   343
    bool finished() { return bfs_queue.empty(); }
marci@42
   344
    operator OutEdgeIt () { return actual_edge; }
marci@42
   345
    bool bNodeIsNewlyReached() { return b_node_newly_reached; }
marci@42
   346
    bool aNodeIsExamined() { return !(actual_edge.valid()); }
marci@42
   347
  };
marci@42
   348
marci@42
   349
marci@42
   350
  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
marci@42
   351
  struct DfsIterator1 {
marci@42
   352
    typedef typename Graph::NodeIt NodeIt;
marci@42
   353
    Graph& G;
marci@42
   354
    std::stack<OutEdgeIt>& bfs_queue;
marci@42
   355
    ReachedMap& reached;
marci@42
   356
    bool b_node_newly_reached;
marci@42
   357
    OutEdgeIt actual_edge;
marci@42
   358
    DfsIterator1(Graph& _G, 
marci@42
   359
		std::stack<OutEdgeIt>& _bfs_queue, 
marci@42
   360
		ReachedMap& _reached) : 
marci@42
   361
      G(_G), bfs_queue(_bfs_queue), reached(_reached) { 
marci@42
   362
      //actual_edge=bfs_queue.top();
marci@42
   363
      //if (actual_edge.valid()) { 
marci@42
   364
      //	NodeIt w=G.bNode(actual_edge);
marci@42
   365
      //if (!reached.get(w)) {
marci@42
   366
      //  bfs_queue.push(OutEdgeIt(G, w));
marci@42
   367
      //  reached.set(w, true);
marci@42
   368
      //  b_node_newly_reached=true;
marci@42
   369
      //} else {
marci@42
   370
      //  ++(bfs_queue.top());
marci@42
   371
      //  b_node_newly_reached=false;
marci@42
   372
      //}
marci@42
   373
      //} else {
marci@42
   374
      //	bfs_queue.pop();
marci@42
   375
      //}
marci@42
   376
    }
marci@42
   377
    void next() { 
marci@42
   378
      actual_edge=bfs_queue.top();
marci@42
   379
      if (actual_edge.valid()) { 
marci@42
   380
	NodeIt w=G.bNode(actual_edge);
marci@42
   381
	if (!reached.get(w)) {
marci@42
   382
	  bfs_queue.push(OutEdgeIt(G, w));
marci@42
   383
	  reached.set(w, true);
marci@42
   384
	  b_node_newly_reached=true;
marci@42
   385
	} else {
marci@42
   386
	  ++(bfs_queue.top());
marci@42
   387
	  b_node_newly_reached=false;
marci@42
   388
	}
marci@42
   389
      } else {
marci@42
   390
	bfs_queue.pop();
marci@42
   391
      }
marci@42
   392
      //return *this;
marci@42
   393
    }
marci@42
   394
    bool finished() { return bfs_queue.empty(); }
marci@42
   395
    operator OutEdgeIt () { return actual_edge; }
marci@42
   396
    bool bNodeIsNewlyReached() { return b_node_newly_reached; }
marci@42
   397
    bool aNodeIsLeaved() { return !(actual_edge.valid()); }
marci@42
   398
  };
marci@42
   399
marci@58
   400
  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
marci@58
   401
  class BfsIterator2 {
marci@58
   402
    typedef typename Graph::NodeIt NodeIt;
marci@58
   403
    const Graph& G;
marci@58
   404
    std::queue<OutEdgeIt> bfs_queue;
marci@58
   405
    ReachedMap reached;
marci@58
   406
    bool b_node_newly_reached;
marci@58
   407
    OutEdgeIt actual_edge;
marci@58
   408
  public:
marci@58
   409
    BfsIterator2(const Graph& _G) : G(_G), reached(G, false) { }
marci@64
   410
    void pushAndSetReached(NodeIt s) { 
marci@58
   411
      reached.set(s, true);
marci@58
   412
      if (bfs_queue.empty()) {
marci@58
   413
	bfs_queue.push(G.template first<OutEdgeIt>(s));
marci@58
   414
	actual_edge=bfs_queue.front();
marci@58
   415
	if (actual_edge.valid()) { 
marci@58
   416
	  NodeIt w=G.bNode(actual_edge);
marci@58
   417
	  if (!reached.get(w)) {
marci@58
   418
	    bfs_queue.push(G.template first<OutEdgeIt>(w));
marci@58
   419
	    reached.set(w, true);
marci@58
   420
	    b_node_newly_reached=true;
marci@58
   421
	  } else {
marci@58
   422
	    b_node_newly_reached=false;
marci@58
   423
	  }
marci@58
   424
	} //else {
marci@58
   425
	//}
marci@58
   426
      } else {
marci@58
   427
	bfs_queue.push(G.template first<OutEdgeIt>(s));
marci@58
   428
      }
marci@58
   429
    }
marci@58
   430
    BfsIterator2<Graph, OutEdgeIt, ReachedMap>& 
marci@58
   431
    operator++() { 
marci@58
   432
      if (bfs_queue.front().valid()) { 
marci@58
   433
	++(bfs_queue.front());
marci@58
   434
	actual_edge=bfs_queue.front();
marci@58
   435
	if (actual_edge.valid()) {
marci@58
   436
	  NodeIt w=G.bNode(actual_edge);
marci@58
   437
	  if (!reached.get(w)) {
marci@58
   438
	    bfs_queue.push(G.template first<OutEdgeIt>(w));
marci@58
   439
	    reached.set(w, true);
marci@58
   440
	    b_node_newly_reached=true;
marci@58
   441
	  } else {
marci@58
   442
	    b_node_newly_reached=false;
marci@58
   443
	  }
marci@58
   444
	}
marci@58
   445
      } else {
marci@58
   446
	bfs_queue.pop(); 
marci@58
   447
	if (!bfs_queue.empty()) {
marci@58
   448
	  actual_edge=bfs_queue.front();
marci@64
   449
	  if (actual_edge.valid()) {
marci@64
   450
	    NodeIt w=G.bNode(actual_edge);
marci@64
   451
	    if (!reached.get(w)) {
marci@64
   452
	      bfs_queue.push(G.template first<OutEdgeIt>(w));
marci@64
   453
	      reached.set(w, true);
marci@64
   454
	      b_node_newly_reached=true;
marci@64
   455
	    } else {
marci@64
   456
	      b_node_newly_reached=false;
marci@64
   457
	    }
marci@58
   458
	  }
marci@58
   459
	}
marci@58
   460
      }
marci@58
   461
      return *this;
marci@58
   462
    }
marci@58
   463
    bool finished() const { return bfs_queue.empty(); }
marci@58
   464
    operator OutEdgeIt () const { return actual_edge; }
marci@58
   465
    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
marci@58
   466
    bool isANodeExamined() const { return !(actual_edge.valid()); }
marci@58
   467
    const ReachedMap& getReachedMap() const { return reached; }
marci@58
   468
    const std::queue<OutEdgeIt>& getBfsQueue() const { return bfs_queue; }
marci@58
   469
 };
marci@58
   470
marci@75
   471
marci@75
   472
  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
marci@75
   473
  class BfsIterator3 {
marci@75
   474
    typedef typename Graph::NodeIt NodeIt;
marci@75
   475
    const Graph& G;
marci@75
   476
    std::queue< std::pair<NodeIt, OutEdgeIt> > bfs_queue;
marci@75
   477
    ReachedMap reached;
marci@75
   478
    bool b_node_newly_reached;
marci@75
   479
    OutEdgeIt actual_edge;
marci@75
   480
  public:
marci@75
   481
    BfsIterator3(const Graph& _G) : G(_G), reached(G, false) { }
marci@75
   482
    void pushAndSetReached(NodeIt s) { 
marci@75
   483
      reached.set(s, true);
marci@75
   484
      if (bfs_queue.empty()) {
marci@75
   485
	bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
marci@75
   486
	actual_edge=bfs_queue.front().second;
marci@75
   487
	if (actual_edge.valid()) { 
marci@75
   488
	  NodeIt w=G.bNode(actual_edge);
marci@75
   489
	  if (!reached.get(w)) {
marci@75
   490
	    bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
marci@75
   491
	    reached.set(w, true);
marci@75
   492
	    b_node_newly_reached=true;
marci@75
   493
	  } else {
marci@75
   494
	    b_node_newly_reached=false;
marci@75
   495
	  }
marci@75
   496
	} //else {
marci@75
   497
	//}
marci@75
   498
      } else {
marci@75
   499
	bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
marci@75
   500
      }
marci@75
   501
    }
marci@75
   502
    BfsIterator3<Graph, OutEdgeIt, ReachedMap>& 
marci@75
   503
    operator++() { 
marci@75
   504
      if (bfs_queue.front().second.valid()) { 
marci@75
   505
	++(bfs_queue.front().second);
marci@75
   506
	actual_edge=bfs_queue.front().second;
marci@75
   507
	if (actual_edge.valid()) {
marci@75
   508
	  NodeIt w=G.bNode(actual_edge);
marci@75
   509
	  if (!reached.get(w)) {
marci@75
   510
	    bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
marci@75
   511
	    reached.set(w, true);
marci@75
   512
	    b_node_newly_reached=true;
marci@75
   513
	  } else {
marci@75
   514
	    b_node_newly_reached=false;
marci@75
   515
	  }
marci@75
   516
	}
marci@75
   517
      } else {
marci@75
   518
	bfs_queue.pop(); 
marci@75
   519
	if (!bfs_queue.empty()) {
marci@75
   520
	  actual_edge=bfs_queue.front().second;
marci@75
   521
	  if (actual_edge.valid()) {
marci@75
   522
	    NodeIt w=G.bNode(actual_edge);
marci@75
   523
	    if (!reached.get(w)) {
marci@75
   524
	      bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
marci@75
   525
	      reached.set(w, true);
marci@75
   526
	      b_node_newly_reached=true;
marci@75
   527
	    } else {
marci@75
   528
	      b_node_newly_reached=false;
marci@75
   529
	    }
marci@75
   530
	  }
marci@75
   531
	}
marci@75
   532
      }
marci@75
   533
      return *this;
marci@75
   534
    }
marci@75
   535
    bool finished() const { return bfs_queue.empty(); }
marci@75
   536
    operator OutEdgeIt () const { return actual_edge; }
marci@75
   537
    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
marci@75
   538
    bool isANodeExamined() const { return !(actual_edge.valid()); }
marci@75
   539
    NodeIt aNode() const { return bfs_queue.front().first; }
marci@75
   540
    NodeIt bNode() const { return G.bNode(actual_edge); }
marci@75
   541
    const ReachedMap& getReachedMap() const { return reached; }
marci@75
   542
    //const std::queue< std::pair<NodeIt, OutEdgeIt> >& getBfsQueue() const { return bfs_queue; }
marci@75
   543
 };
marci@75
   544
marci@75
   545
  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
marci@75
   546
  class BfsIterator4 {
marci@75
   547
    typedef typename Graph::NodeIt NodeIt;
marci@75
   548
    const Graph& G;
marci@75
   549
    std::queue<NodeIt> bfs_queue;
marci@75
   550
    ReachedMap reached;
marci@75
   551
    bool b_node_newly_reached;
marci@75
   552
    OutEdgeIt actual_edge;
marci@75
   553
  public:
marci@75
   554
    BfsIterator4(const Graph& _G) : G(_G), reached(G, false) { }
marci@75
   555
    void pushAndSetReached(NodeIt s) { 
marci@75
   556
      reached.set(s, true);
marci@75
   557
      if (bfs_queue.empty()) {
marci@75
   558
	bfs_queue.push(s);
marci@75
   559
	G.getFirst(actual_edge, s);
marci@75
   560
	if (actual_edge.valid()) { 
marci@75
   561
	  NodeIt w=G.bNode(actual_edge);
marci@75
   562
	  if (!reached.get(w)) {
marci@75
   563
	    bfs_queue.push(w);
marci@75
   564
	    reached.set(w, true);
marci@75
   565
	    b_node_newly_reached=true;
marci@75
   566
	  } else {
marci@75
   567
	    b_node_newly_reached=false;
marci@75
   568
	  }
marci@75
   569
	} 
marci@75
   570
      } else {
marci@75
   571
	bfs_queue.push(s);
marci@75
   572
      }
marci@75
   573
    }
marci@75
   574
    BfsIterator4<Graph, OutEdgeIt, ReachedMap>& 
marci@75
   575
    operator++() { 
marci@75
   576
      if (actual_edge.valid()) { 
marci@75
   577
	++actual_edge;
marci@75
   578
	if (actual_edge.valid()) {
marci@75
   579
	  NodeIt w=G.bNode(actual_edge);
marci@75
   580
	  if (!reached.get(w)) {
marci@75
   581
	    bfs_queue.push(w);
marci@75
   582
	    reached.set(w, true);
marci@75
   583
	    b_node_newly_reached=true;
marci@75
   584
	  } else {
marci@75
   585
	    b_node_newly_reached=false;
marci@75
   586
	  }
marci@75
   587
	}
marci@75
   588
      } else {
marci@75
   589
	bfs_queue.pop(); 
marci@75
   590
	if (!bfs_queue.empty()) {
marci@75
   591
	  G.getFirst(actual_edge, bfs_queue.front());
marci@75
   592
	  if (actual_edge.valid()) {
marci@75
   593
	    NodeIt w=G.bNode(actual_edge);
marci@75
   594
	    if (!reached.get(w)) {
marci@75
   595
	      bfs_queue.push(w);
marci@75
   596
	      reached.set(w, true);
marci@75
   597
	      b_node_newly_reached=true;
marci@75
   598
	    } else {
marci@75
   599
	      b_node_newly_reached=false;
marci@75
   600
	    }
marci@75
   601
	  }
marci@75
   602
	}
marci@75
   603
      }
marci@75
   604
      return *this;
marci@75
   605
    }
marci@75
   606
    bool finished() const { return bfs_queue.empty(); }
marci@75
   607
    operator OutEdgeIt () const { return actual_edge; }
marci@75
   608
    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
marci@75
   609
    bool isANodeExamined() const { return !(actual_edge.valid()); }
marci@75
   610
    NodeIt aNode() const { return bfs_queue.front(); }
marci@75
   611
    NodeIt bNode() const { return G.bNode(actual_edge); }
marci@75
   612
    const ReachedMap& getReachedMap() const { return reached; }
marci@75
   613
    const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
marci@75
   614
 };
marci@75
   615
marci@75
   616
marci@75
   617
  template <typename GraphWrapper, typename ReachedMap>
marci@75
   618
  class BfsIterator5 {
marci@75
   619
    typedef typename GraphWrapper::NodeIt NodeIt;
marci@75
   620
    typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
marci@75
   621
    GraphWrapper gw;
marci@75
   622
    std::queue<NodeIt> bfs_queue;
marci@75
   623
    ReachedMap reached;
marci@75
   624
    bool b_node_newly_reached;
marci@75
   625
    OutEdgeIt actual_edge;
marci@75
   626
  public:
marci@75
   627
    BfsIterator5(GraphWrapper _gw) : 
marci@75
   628
      gw(_gw), reached(_gw.getGraph()) { }
marci@75
   629
    void pushAndSetReached(NodeIt s) { 
marci@75
   630
      reached.set(s, true);
marci@75
   631
      if (bfs_queue.empty()) {
marci@75
   632
	bfs_queue.push(s);
marci@75
   633
	gw.getFirst(actual_edge, s);
marci@75
   634
	if (actual_edge.valid()) { 
marci@75
   635
	  NodeIt w=gw.bNode(actual_edge);
marci@75
   636
	  if (!reached.get(w)) {
marci@75
   637
	    bfs_queue.push(w);
marci@75
   638
	    reached.set(w, true);
marci@75
   639
	    b_node_newly_reached=true;
marci@75
   640
	  } else {
marci@75
   641
	    b_node_newly_reached=false;
marci@75
   642
	  }
marci@75
   643
	} 
marci@75
   644
      } else {
marci@75
   645
	bfs_queue.push(s);
marci@75
   646
      }
marci@75
   647
    }
marci@75
   648
    BfsIterator5<GraphWrapper, ReachedMap>& 
marci@75
   649
    operator++() { 
marci@75
   650
      if (actual_edge.valid()) { 
marci@75
   651
	++actual_edge;
marci@75
   652
	if (actual_edge.valid()) {
marci@75
   653
	  NodeIt w=gw.bNode(actual_edge);
marci@75
   654
	  if (!reached.get(w)) {
marci@75
   655
	    bfs_queue.push(w);
marci@75
   656
	    reached.set(w, true);
marci@75
   657
	    b_node_newly_reached=true;
marci@75
   658
	  } else {
marci@75
   659
	    b_node_newly_reached=false;
marci@75
   660
	  }
marci@75
   661
	}
marci@75
   662
      } else {
marci@75
   663
	bfs_queue.pop(); 
marci@75
   664
	if (!bfs_queue.empty()) {
marci@75
   665
	  gw.getFirst(actual_edge, bfs_queue.front());
marci@75
   666
	  if (actual_edge.valid()) {
marci@75
   667
	    NodeIt w=gw.bNode(actual_edge);
marci@75
   668
	    if (!reached.get(w)) {
marci@75
   669
	      bfs_queue.push(w);
marci@75
   670
	      reached.set(w, true);
marci@75
   671
	      b_node_newly_reached=true;
marci@75
   672
	    } else {
marci@75
   673
	      b_node_newly_reached=false;
marci@75
   674
	    }
marci@75
   675
	  }
marci@75
   676
	}
marci@75
   677
      }
marci@75
   678
      return *this;
marci@75
   679
    }
marci@75
   680
    bool finished() const { return bfs_queue.empty(); }
marci@75
   681
    operator OutEdgeIt () const { return actual_edge; }
marci@75
   682
    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
marci@75
   683
    bool isANodeExamined() const { return !(actual_edge.valid()); }
marci@75
   684
    NodeIt aNode() const { return bfs_queue.front(); }
marci@75
   685
    NodeIt bNode() const { return gw.bNode(actual_edge); }
marci@75
   686
    const ReachedMap& getReachedMap() const { return reached; }
marci@75
   687
    const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
marci@75
   688
 };
marci@75
   689
marci@75
   690
marci@75
   691
marci@42
   692
} // namespace marci
marci@42
   693
marci@58
   694
#endif //BFS_ITERATOR_HH