COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 360:91fba31268d6 in lemon-0.x for src/work


Ignore:
Timestamp:
04/21/04 17:14:45 (21 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@487
Message:

work/marci/bfs_iterator.h BfsIterator5 -> BfsIterator?, DfsIterator5 -> DfsIterator?

Location:
src/work/marci
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • src/work/marci/bfs_iterator.h

    r303 r360  
    99namespace hugo {
    1010
    11 //   template <typename Graph>
    12 //   struct bfs {
    13 //     typedef typename Graph::Node Node;
    14 //     typedef typename Graph::Edge Edge;
    15 //     typedef typename Graph::NodeIt NodeIt;
    16 //     typedef typename Graph::OutEdgeIt OutEdgeIt;
    17 //     Graph& G;
    18 //     Node s;
    19 //     typename Graph::NodeMap<bool> reached;
    20 //     typename Graph::NodeMap<Edge> pred;
    21 //     typename Graph::NodeMap<int> dist;
    22 //     std::queue<Node> bfs_queue;
    23 //     bfs(Graph& _G, Node _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) {
    24 //       bfs_queue.push(s);
    25 //       for(NodeIt i=G.template first<NodeIt>(); i.valid(); ++i)
    26 //      reached.set(i, false);
    27 //       reached.set(s, true);
    28 //       dist.set(s, 0);
    29 //     }
    30    
    31 //     void run() {
    32 //       while (!bfs_queue.empty()) {
    33 //      Node v=bfs_queue.front();
    34 //      OutEdgeIt e=G.template first<OutEdgeIt>(v);
    35 //      bfs_queue.pop();
    36 //      for( ; e.valid(); ++e) {
    37 //        Node w=G.bNode(e);
    38 //        std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;
    39 //        if (!reached.get(w)) {
    40 //          std::cout << G.id(w) << " is newly reached :-)" << std::endl;
    41 //          bfs_queue.push(w);
    42 //          dist.set(w, dist.get(v)+1);
    43 //          pred.set(w, e);
    44 //          reached.set(w, true);
    45 //        } else {
    46 //          std::cout << G.id(w) << " is already reached" << std::endl;
    47 //        }
    48 //      }
    49 //       }
    50 //     }
    51 //   };
    52 
    53 //   template <typename Graph>
    54 //   struct bfs_visitor {
    55 //     typedef typename Graph::Node Node;
    56 //     typedef typename Graph::Edge Edge;
    57 //     typedef typename Graph::OutEdgeIt OutEdgeIt;
    58 //     Graph& G;
    59 //     bfs_visitor(Graph& _G) : G(_G) { }
    60 //     void at_previously_reached(OutEdgeIt& e) {
    61 //       //Node v=G.aNode(e);
    62 //       Node w=G.bNode(e);
    63 //       std::cout << G.id(w) << " is already reached" << std::endl;
    64 //    }
    65 //     void at_newly_reached(OutEdgeIt& e) {
    66 //       //Node v=G.aNode(e);
    67 //       Node w=G.bNode(e);
    68 //       std::cout << G.id(w) << " is newly reached :-)" << std::endl;
    69 //     }
    70 //   };
    71 
    72 //   template <typename Graph, typename ReachedMap, typename visitor_type>
    73 //   struct bfs_iterator {
    74 //     typedef typename Graph::Node Node;
    75 //     typedef typename Graph::Edge Edge;
    76 //     typedef typename Graph::OutEdgeIt OutEdgeIt;
    77 //     Graph& G;
    78 //     std::queue<OutEdgeIt>& bfs_queue;
    79 //     ReachedMap& reached;
    80 //     visitor_type& visitor;
    81 //     void process() {
    82 //       while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
    83 //       if (bfs_queue.empty()) return;
    84 //       OutEdgeIt e=bfs_queue.front();
    85 //       //Node v=G.aNode(e);
    86 //       Node w=G.bNode(e);
    87 //       if (!reached.get(w)) {
    88 //      visitor.at_newly_reached(e);
    89 //      bfs_queue.push(G.template first<OutEdgeIt>(w));
    90 //      reached.set(w, true);
    91 //       } else {
    92 //      visitor.at_previously_reached(e);
    93 //       }
    94 //     }
    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) {
    96 //       //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
    97 //       valid();
    98 //     }
    99 //     bfs_iterator<Graph, ReachedMap, visitor_type>& operator++() {
    100 //       //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
    101 //       //if (bfs_queue.empty()) return *this;
    102 //       if (!valid()) return *this;
    103 //       ++(bfs_queue.front());
    104 //       //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
    105 //       valid();
    106 //       return *this;
    107 //     }
    108 //     //void next() {
    109 //     //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
    110 //     //  if (bfs_queue.empty()) return;
    111 //     //  ++(bfs_queue.front());
    112 //     //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
    113 //     //}
    114 //     bool valid() {
    115 //       while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
    116 //       if (bfs_queue.empty()) return false; else return true;
    117 //     }
    118 //     //bool finished() {
    119 //     //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
    120 //     //  if (bfs_queue.empty()) return true; else return false;
    121 //     //}
    122 //     operator Edge () { return bfs_queue.front(); }
    123 
    124 //   };
    125 
    126 //   template <typename Graph, typename ReachedMap>
    127 //   struct bfs_iterator1 {
    128 //     typedef typename Graph::Node Node;
    129 //     typedef typename Graph::Edge Edge;
    130 //     typedef typename Graph::OutEdgeIt OutEdgeIt;
    131 //     Graph& G;
    132 //     std::queue<OutEdgeIt>& bfs_queue;
    133 //     ReachedMap& reached;
    134 //     bool _newly_reached;
    135 //     bfs_iterator1(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) {
    136 //       valid();
    137 //       if (!bfs_queue.empty() && bfs_queue.front().valid()) {
    138 //      OutEdgeIt e=bfs_queue.front();
    139 //      Node w=G.bNode(e);
    140 //      if (!reached.get(w)) {
    141 //        bfs_queue.push(G.template first<OutEdgeIt>(w));
    142 //        reached.set(w, true);
    143 //        _newly_reached=true;
    144 //      } else {
    145 //        _newly_reached=false;
    146 //      }
    147 //       }
    148 //     }
    149 //     bfs_iterator1<Graph, ReachedMap>& operator++() {
    150 //       if (!valid()) return *this;
    151 //       ++(bfs_queue.front());
    152 //       valid();
    153 //       if (!bfs_queue.empty() && bfs_queue.front().valid()) {
    154 //      OutEdgeIt e=bfs_queue.front();
    155 //      Node w=G.bNode(e);
    156 //      if (!reached.get(w)) {
    157 //        bfs_queue.push(G.template first<OutEdgeIt>(w));
    158 //        reached.set(w, true);
    159 //        _newly_reached=true;
    160 //      } else {
    161 //        _newly_reached=false;
    162 //      }
    163 //       }
    164 //       return *this;
    165 //     }
    166 //     bool valid() {
    167 //       while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
    168 //       if (bfs_queue.empty()) return false; else return true;
    169 //     }
    170 //     operator OutEdgeIt() { return bfs_queue.front(); }
    171 //     //ize
    172 //     bool newly_reached() { return _newly_reached; }
    173 
    174 //   };
    175 
    176 //   template <typename Graph, typename OutEdgeIt, typename ReachedMap>
    177 //   struct BfsIterator {
    178 //     typedef typename Graph::Node Node;
    179 //     Graph& G;
    180 //     std::queue<OutEdgeIt>& bfs_queue;
    181 //     ReachedMap& reached;
    182 //     bool b_node_newly_reached;
    183 //     OutEdgeIt actual_edge;
    184 //     BfsIterator(Graph& _G,
    185 //              std::queue<OutEdgeIt>& _bfs_queue,
    186 //              ReachedMap& _reached) :
    187 //       G(_G), bfs_queue(_bfs_queue), reached(_reached) {
    188 //       actual_edge=bfs_queue.front();
    189 //       if (actual_edge.valid()) {
    190 //      Node w=G.bNode(actual_edge);
    191 //      if (!reached.get(w)) {
    192 //        bfs_queue.push(G.firstOutEdge(w));
    193 //        reached.set(w, true);
    194 //        b_node_newly_reached=true;
    195 //      } else {
    196 //        b_node_newly_reached=false;
    197 //      }
    198 //       }
    199 //     }
    200 //     BfsIterator<Graph, OutEdgeIt, ReachedMap>&
    201 //     operator++() {
    202 //       if (bfs_queue.front().valid()) {
    203 //      ++(bfs_queue.front());
    204 //      actual_edge=bfs_queue.front();
    205 //      if (actual_edge.valid()) {
    206 //        Node w=G.bNode(actual_edge);
    207 //        if (!reached.get(w)) {
    208 //          bfs_queue.push(G.firstOutEdge(w));
    209 //          reached.set(w, true);
    210 //          b_node_newly_reached=true;
    211 //        } else {
    212 //          b_node_newly_reached=false;
    213 //        }
    214 //      }
    215 //       } else {
    216 //      bfs_queue.pop();
    217 //      actual_edge=bfs_queue.front();
    218 //      if (actual_edge.valid()) {
    219 //        Node w=G.bNode(actual_edge);
    220 //        if (!reached.get(w)) {
    221 //          bfs_queue.push(G.firstOutEdge(w));
    222 //          reached.set(w, true);
    223 //          b_node_newly_reached=true;
    224 //        } else {
    225 //          b_node_newly_reached=false;
    226 //        }
    227 //      }
    228 //       }
    229 //       return *this;
    230 //     }
    231 //     bool finished() { return bfs_queue.empty(); }
    232 //     operator OutEdgeIt () { return actual_edge; }
    233 //     bool bNodeIsNewlyReached() { return b_node_newly_reached; }
    234 //     bool aNodeIsExamined() { return !(actual_edge.valid()); }
    235 //   };
    236 
    237 
    238 //   template <typename Graph, typename OutEdgeIt, typename ReachedMap>
    239 //   struct DfsIterator {
    240 //     typedef typename Graph::Node Node;
    241 //     Graph& G;
    242 //     std::stack<OutEdgeIt>& bfs_queue;
    243 //     ReachedMap& reached;
    244 //     bool b_node_newly_reached;
    245 //     OutEdgeIt actual_edge;
    246 //     DfsIterator(Graph& _G,
    247 //              std::stack<OutEdgeIt>& _bfs_queue,
    248 //              ReachedMap& _reached) :
    249 //       G(_G), bfs_queue(_bfs_queue), reached(_reached) {
    250 //       actual_edge=bfs_queue.top();
    251 //       if (actual_edge.valid()) {
    252 //      Node w=G.bNode(actual_edge);
    253 //      if (!reached.get(w)) {
    254 //        bfs_queue.push(G.firstOutEdge(w));
    255 //        reached.set(w, true);
    256 //        b_node_newly_reached=true;
    257 //      } else {
    258 //        ++(bfs_queue.top());
    259 //        b_node_newly_reached=false;
    260 //      }
    261 //       } else {
    262 //      bfs_queue.pop();
    263 //       }
    264 //     }
    265 //     DfsIterator<Graph, OutEdgeIt, ReachedMap>&
    266 //     operator++() {
    267 //       actual_edge=bfs_queue.top();
    268 //       if (actual_edge.valid()) {
    269 //      Node w=G.bNode(actual_edge);
    270 //      if (!reached.get(w)) {
    271 //        bfs_queue.push(G.firstOutEdge(w));
    272 //        reached.set(w, true);
    273 //        b_node_newly_reached=true;
    274 //      } else {
    275 //        ++(bfs_queue.top());
    276 //        b_node_newly_reached=false;
    277 //      }
    278 //       } else {
    279 //      bfs_queue.pop();
    280 //       }
    281 //       return *this;
    282 //     }
    283 //     bool finished() { return bfs_queue.empty(); }
    284 //     operator OutEdgeIt () { return actual_edge; }
    285 //     bool bNodeIsNewlyReached() { return b_node_newly_reached; }
    286 //     bool aNodeIsExamined() { return !(actual_edge.valid()); }
    287 //   };
    288 
    289 //   template <typename Graph, typename OutEdgeIt, typename ReachedMap>
    290 //   struct BfsIterator1 {
    291 //     typedef typename Graph::Node Node;
    292 //     Graph& G;
    293 //     std::queue<OutEdgeIt>& bfs_queue;
    294 //     ReachedMap& reached;
    295 //     bool b_node_newly_reached;
    296 //     OutEdgeIt actual_edge;
    297 //     BfsIterator1(Graph& _G,
    298 //              std::queue<OutEdgeIt>& _bfs_queue,
    299 //              ReachedMap& _reached) :
    300 //       G(_G), bfs_queue(_bfs_queue), reached(_reached) {
    301 //       actual_edge=bfs_queue.front();
    302 //       if (actual_edge.valid()) {
    303 //              Node w=G.bNode(actual_edge);
    304 //      if (!reached.get(w)) {
    305 //        bfs_queue.push(OutEdgeIt(G, w));
    306 //        reached.set(w, true);
    307 //        b_node_newly_reached=true;
    308 //      } else {
    309 //        b_node_newly_reached=false;
    310 //      }
    311 //       }
    312 //     }
    313 //     void next() {
    314 //       if (bfs_queue.front().valid()) {
    315 //      ++(bfs_queue.front());
    316 //      actual_edge=bfs_queue.front();
    317 //      if (actual_edge.valid()) {
    318 //        Node w=G.bNode(actual_edge);
    319 //        if (!reached.get(w)) {
    320 //          bfs_queue.push(OutEdgeIt(G, w));
    321 //          reached.set(w, true);
    322 //          b_node_newly_reached=true;
    323 //        } else {
    324 //          b_node_newly_reached=false;
    325 //        }
    326 //      }
    327 //       } else {
    328 //      bfs_queue.pop();
    329 //      actual_edge=bfs_queue.front();
    330 //      if (actual_edge.valid()) {
    331 //        Node w=G.bNode(actual_edge);
    332 //        if (!reached.get(w)) {
    333 //          bfs_queue.push(OutEdgeIt(G, w));
    334 //          reached.set(w, true);
    335 //          b_node_newly_reached=true;
    336 //        } else {
    337 //          b_node_newly_reached=false;
    338 //        }
    339 //      }
    340 //       }
    341 //       //return *this;
    342 //     }
    343 //     bool finished() { return bfs_queue.empty(); }
    344 //     operator OutEdgeIt () { return actual_edge; }
    345 //     bool bNodeIsNewlyReached() { return b_node_newly_reached; }
    346 //     bool aNodeIsExamined() { return !(actual_edge.valid()); }
    347 //   };
    348 
    349 
    350 //   template <typename Graph, typename OutEdgeIt, typename ReachedMap>
    351 //   struct DfsIterator1 {
    352 //     typedef typename Graph::Node Node;
    353 //     Graph& G;
    354 //     std::stack<OutEdgeIt>& bfs_queue;
    355 //     ReachedMap& reached;
    356 //     bool b_node_newly_reached;
    357 //     OutEdgeIt actual_edge;
    358 //     DfsIterator1(Graph& _G,
    359 //              std::stack<OutEdgeIt>& _bfs_queue,
    360 //              ReachedMap& _reached) :
    361 //       G(_G), bfs_queue(_bfs_queue), reached(_reached) {
    362 //       //actual_edge=bfs_queue.top();
    363 //       //if (actual_edge.valid()) {
    364 //       //     Node w=G.bNode(actual_edge);
    365 //       //if (!reached.get(w)) {
    366 //       //  bfs_queue.push(OutEdgeIt(G, w));
    367 //       //  reached.set(w, true);
    368 //       //  b_node_newly_reached=true;
    369 //       //} else {
    370 //       //  ++(bfs_queue.top());
    371 //       //  b_node_newly_reached=false;
    372 //       //}
    373 //       //} else {
    374 //       //     bfs_queue.pop();
    375 //       //}
    376 //     }
    377 //     void next() {
    378 //       actual_edge=bfs_queue.top();
    379 //       if (actual_edge.valid()) {
    380 //      Node w=G.bNode(actual_edge);
    381 //      if (!reached.get(w)) {
    382 //        bfs_queue.push(OutEdgeIt(G, w));
    383 //        reached.set(w, true);
    384 //        b_node_newly_reached=true;
    385 //      } else {
    386 //        ++(bfs_queue.top());
    387 //        b_node_newly_reached=false;
    388 //      }
    389 //       } else {
    390 //      bfs_queue.pop();
    391 //       }
    392 //       //return *this;
    393 //     }
    394 //     bool finished() { return bfs_queue.empty(); }
    395 //     operator OutEdgeIt () { return actual_edge; }
    396 //     bool bNodeIsNewlyReached() { return b_node_newly_reached; }
    397 //     bool aNodeIsLeaved() { return !(actual_edge.valid()); }
    398 //   };
    399 
    400 //   template <typename Graph, typename OutEdgeIt, typename ReachedMap>
    401 //   class BfsIterator2 {
    402 //     typedef typename Graph::Node Node;
    403 //     const Graph& G;
    404 //     std::queue<OutEdgeIt> bfs_queue;
    405 //     ReachedMap reached;
    406 //     bool b_node_newly_reached;
    407 //     OutEdgeIt actual_edge;
    408 //   public:
    409 //     BfsIterator2(const Graph& _G) : G(_G), reached(G, false) { }
    410 //     void pushAndSetReached(Node s) {
    411 //       reached.set(s, true);
    412 //       if (bfs_queue.empty()) {
    413 //      bfs_queue.push(G.template first<OutEdgeIt>(s));
    414 //      actual_edge=bfs_queue.front();
    415 //      if (actual_edge.valid()) {
    416 //        Node w=G.bNode(actual_edge);
    417 //        if (!reached.get(w)) {
    418 //          bfs_queue.push(G.template first<OutEdgeIt>(w));
    419 //          reached.set(w, true);
    420 //          b_node_newly_reached=true;
    421 //        } else {
    422 //          b_node_newly_reached=false;
    423 //        }
    424 //      } //else {
    425 //      //}
    426 //       } else {
    427 //      bfs_queue.push(G.template first<OutEdgeIt>(s));
    428 //       }
    429 //     }
    430 //     BfsIterator2<Graph, OutEdgeIt, ReachedMap>&
    431 //     operator++() {
    432 //       if (bfs_queue.front().valid()) {
    433 //      ++(bfs_queue.front());
    434 //      actual_edge=bfs_queue.front();
    435 //      if (actual_edge.valid()) {
    436 //        Node w=G.bNode(actual_edge);
    437 //        if (!reached.get(w)) {
    438 //          bfs_queue.push(G.template first<OutEdgeIt>(w));
    439 //          reached.set(w, true);
    440 //          b_node_newly_reached=true;
    441 //        } else {
    442 //          b_node_newly_reached=false;
    443 //        }
    444 //      }
    445 //       } else {
    446 //      bfs_queue.pop();
    447 //      if (!bfs_queue.empty()) {
    448 //        actual_edge=bfs_queue.front();
    449 //        if (actual_edge.valid()) {
    450 //          Node w=G.bNode(actual_edge);
    451 //          if (!reached.get(w)) {
    452 //            bfs_queue.push(G.template first<OutEdgeIt>(w));
    453 //            reached.set(w, true);
    454 //            b_node_newly_reached=true;
    455 //          } else {
    456 //            b_node_newly_reached=false;
    457 //          }
    458 //        }
    459 //      }
    460 //       }
    461 //       return *this;
    462 //     }
    463 //     bool finished() const { return bfs_queue.empty(); }
    464 //     operator OutEdgeIt () const { return actual_edge; }
    465 //     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
    466 //     bool isANodeExamined() const { return !(actual_edge.valid()); }
    467 //     const ReachedMap& getReachedMap() const { return reached; }
    468 //     const std::queue<OutEdgeIt>& getBfsQueue() const { return bfs_queue; }
    469 //  };
    470 
    471 
    472 //   template <typename Graph, typename OutEdgeIt, typename ReachedMap>
    473 //   class BfsIterator3 {
    474 //     typedef typename Graph::Node Node;
    475 //     const Graph& G;
    476 //     std::queue< std::pair<Node, OutEdgeIt> > bfs_queue;
    477 //     ReachedMap reached;
    478 //     bool b_node_newly_reached;
    479 //     OutEdgeIt actual_edge;
    480 //   public:
    481 //     BfsIterator3(const Graph& _G) : G(_G), reached(G, false) { }
    482 //     void pushAndSetReached(Node s) {
    483 //       reached.set(s, true);
    484 //       if (bfs_queue.empty()) {
    485 //      bfs_queue.push(std::pair<Node, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
    486 //      actual_edge=bfs_queue.front().second;
    487 //      if (actual_edge.valid()) {
    488 //        Node w=G.bNode(actual_edge);
    489 //        if (!reached.get(w)) {
    490 //          bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
    491 //          reached.set(w, true);
    492 //          b_node_newly_reached=true;
    493 //        } else {
    494 //          b_node_newly_reached=false;
    495 //        }
    496 //      } //else {
    497 //      //}
    498 //       } else {
    499 //      bfs_queue.push(std::pair<Node, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
    500 //       }
    501 //     }
    502 //     BfsIterator3<Graph, OutEdgeIt, ReachedMap>&
    503 //     operator++() {
    504 //       if (bfs_queue.front().second.valid()) {
    505 //      ++(bfs_queue.front().second);
    506 //      actual_edge=bfs_queue.front().second;
    507 //      if (actual_edge.valid()) {
    508 //        Node w=G.bNode(actual_edge);
    509 //        if (!reached.get(w)) {
    510 //          bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
    511 //          reached.set(w, true);
    512 //          b_node_newly_reached=true;
    513 //        } else {
    514 //          b_node_newly_reached=false;
    515 //        }
    516 //      }
    517 //       } else {
    518 //      bfs_queue.pop();
    519 //      if (!bfs_queue.empty()) {
    520 //        actual_edge=bfs_queue.front().second;
    521 //        if (actual_edge.valid()) {
    522 //          Node w=G.bNode(actual_edge);
    523 //          if (!reached.get(w)) {
    524 //            bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
    525 //            reached.set(w, true);
    526 //            b_node_newly_reached=true;
    527 //          } else {
    528 //            b_node_newly_reached=false;
    529 //          }
    530 //        }
    531 //      }
    532 //       }
    533 //       return *this;
    534 //     }
    535 //     bool finished() const { return bfs_queue.empty(); }
    536 //     operator OutEdgeIt () const { return actual_edge; }
    537 //     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
    538 //     bool isANodeExamined() const { return !(actual_edge.valid()); }
    539 //     Node aNode() const { return bfs_queue.front().first; }
    540 //     Node bNode() const { return G.bNode(actual_edge); }
    541 //     const ReachedMap& getReachedMap() const { return reached; }
    542 //     //const std::queue< std::pair<Node, OutEdgeIt> >& getBfsQueue() const { return bfs_queue; }
    543 //  };
    544 
    545 
    546 //   template <typename Graph, typename OutEdgeIt,
    547 //          typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
    548 //   class BfsIterator4 {
    549 //     typedef typename Graph::Node Node;
    550 //     const Graph& G;
    551 //     std::queue<Node> bfs_queue;
    552 //     ReachedMap& reached;
    553 //     bool b_node_newly_reached;
    554 //     OutEdgeIt actual_edge;
    555 //     bool own_reached_map;
    556 //   public:
    557 //     BfsIterator4(const Graph& _G, ReachedMap& _reached) :
    558 //       G(_G), reached(_reached),
    559 //       own_reached_map(false) { }
    560 //     BfsIterator4(const Graph& _G) :
    561 //       G(_G), reached(*(new ReachedMap(G /*, false*/))),
    562 //       own_reached_map(true) { }
    563 //     ~BfsIterator4() { if (own_reached_map) delete &reached; }
    564 //     void pushAndSetReached(Node s) {
    565 //       //std::cout << "mimi" << &reached << std::endl;
    566 //       reached.set(s, true);
    567 //       //std::cout << "mumus" << std::endl;
    568 //       if (bfs_queue.empty()) {
    569 //      //std::cout << "bibi1" << std::endl;
    570 //      bfs_queue.push(s);
    571 //      //std::cout << "zizi" << std::endl;
    572 //      G./*getF*/first(actual_edge, s);
    573 //      //std::cout << "kiki" << std::endl;
    574 //      if (G.valid(actual_edge)/*.valid()*/) {
    575 //        Node w=G.bNode(actual_edge);
    576 //        if (!reached.get(w)) {
    577 //          bfs_queue.push(w);
    578 //          reached.set(w, true);
    579 //          b_node_newly_reached=true;
    580 //        } else {
    581 //          b_node_newly_reached=false;
    582 //        }
    583 //      }
    584 //       } else {
    585 //      //std::cout << "bibi2" << std::endl;
    586 //      bfs_queue.push(s);
    587 //       }
    588 //     }
    589 //     BfsIterator4<Graph, OutEdgeIt, ReachedMap>&
    590 //     operator++() {
    591 //       if (G.valid(actual_edge)/*.valid()*/) {
    592 //      /*++*/G.next(actual_edge);
    593 //      if (G.valid(actual_edge)/*.valid()*/) {
    594 //        Node w=G.bNode(actual_edge);
    595 //        if (!reached.get(w)) {
    596 //          bfs_queue.push(w);
    597 //          reached.set(w, true);
    598 //          b_node_newly_reached=true;
    599 //        } else {
    600 //          b_node_newly_reached=false;
    601 //        }
    602 //      }
    603 //       } else {
    604 //      bfs_queue.pop();
    605 //      if (!bfs_queue.empty()) {
    606 //        G./*getF*/first(actual_edge, bfs_queue.front());
    607 //        if (G.valid(actual_edge)/*.valid()*/) {
    608 //          Node w=G.bNode(actual_edge);
    609 //          if (!reached.get(w)) {
    610 //            bfs_queue.push(w);
    611 //            reached.set(w, true);
    612 //            b_node_newly_reached=true;
    613 //          } else {
    614 //            b_node_newly_reached=false;
    615 //          }
    616 //        }
    617 //      }
    618 //       }
    619 //       return *this;
    620 //     }
    621 //     bool finished() const { return bfs_queue.empty(); }
    622 //     operator OutEdgeIt () const { return actual_edge; }
    623 //     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
    624 //     bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
    625 //     Node aNode() const { return bfs_queue.front(); }
    626 //     Node bNode() const { return G.bNode(actual_edge); }
    627 //     const ReachedMap& getReachedMap() const { return reached; }
    628 //     const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
    629 //  }; 
    630 
    631 
    63211  template <typename Graph, /*typename OutEdgeIt,*/
    63312            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
    634   class BfsIterator5 {
     13  class BfsIterator {
    63514  protected:
    63615    typedef typename Graph::Node Node;
    … …  
    64322    bool own_reached_map;
    64423  public:
    645     BfsIterator5(const Graph& _graph, ReachedMap& _reached) :
     24    BfsIterator(const Graph& _graph, ReachedMap& _reached) :
    64625      graph(&_graph), reached(_reached),
    64726      own_reached_map(false) { }
    648     BfsIterator5(const Graph& _graph) :
     27    BfsIterator(const Graph& _graph) :
    64928      graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
    65029      own_reached_map(true) { }
    651     ~BfsIterator5() { if (own_reached_map) delete &reached; }
     30    ~BfsIterator() { if (own_reached_map) delete &reached; }
    65231    void pushAndSetReached(Node s) {
    65332      reached.set(s, true);
    … …  
    66948      }
    67049    }
    671     BfsIterator5<Graph, /*OutEdgeIt,*/ ReachedMap>&
     50    BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
    67251    operator++() {
    67352      if (graph->valid(actual_edge)) {
    … …  
    71190  }; 
    71291
    713 //   template <typename Graph, typename OutEdgeIt,
    714 //          typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
    715 //   class DfsIterator4 {
    716 //     typedef typename Graph::Node Node;
    717 //     const Graph& G;
    718 //     std::stack<OutEdgeIt> dfs_stack;
    719 //     bool b_node_newly_reached;
    720 //     OutEdgeIt actual_edge;
    721 //     Node actual_node;
    722 //     ReachedMap& reached;
    723 //     bool own_reached_map;
    724 //   public:
    725 //     DfsIterator4(const Graph& _G, ReachedMap& _reached) :
    726 //       G(_G), reached(_reached),
    727 //       own_reached_map(false) { }
    728 //     DfsIterator4(const Graph& _G) :
    729 //       G(_G), reached(*(new ReachedMap(G /*, false*/))),
    730 //       own_reached_map(true) { }
    731 //     ~DfsIterator4() { if (own_reached_map) delete &reached; }
    732 //     void pushAndSetReached(Node s) {
    733 //       actual_node=s;
    734 //       reached.set(s, true);
    735 //       dfs_stack.push(G.template first<OutEdgeIt>(s));
    736 //     }
    737 //     DfsIterator4<Graph, OutEdgeIt, ReachedMap>&
    738 //     operator++() {
    739 //       actual_edge=dfs_stack.top();
    740 //       //actual_node=G.aNode(actual_edge);
    741 //       if (G.valid(actual_edge)/*.valid()*/) {
    742 //      Node w=G.bNode(actual_edge);
    743 //      actual_node=w;
    744 //      if (!reached.get(w)) {
    745 //        dfs_stack.push(G.template first<OutEdgeIt>(w));
    746 //        reached.set(w, true);
    747 //        b_node_newly_reached=true;
    748 //      } else {
    749 //        actual_node=G.aNode(actual_edge);
    750 //        /*++*/G.next(dfs_stack.top());
    751 //        b_node_newly_reached=false;
    752 //      }
    753 //       } else {
    754 //      //actual_node=G.aNode(dfs_stack.top());
    755 //      dfs_stack.pop();
    756 //       }
    757 //       return *this;
    758 //     }
    759 //     bool finished() const { return dfs_stack.empty(); }
    760 //     operator OutEdgeIt () const { return actual_edge; }
    761 //     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
    762 //     bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
    763 //     Node aNode() const { return actual_node; /*FIXME*/}
    764 //     Node bNode() const { return G.bNode(actual_edge); }
    765 //     const ReachedMap& getReachedMap() const { return reached; }
    766 //     const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
    767 //   };
    768 
    76992  template <typename Graph, /*typename OutEdgeIt,*/
    77093            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
    771   class DfsIterator5 {
     94  class DfsIterator {
    77295  protected:
    77396    typedef typename Graph::Node Node;
    … …  
    781104    bool own_reached_map;
    782105  public:
    783     DfsIterator5(const Graph& _graph, ReachedMap& _reached) :
     106    DfsIterator(const Graph& _graph, ReachedMap& _reached) :
    784107      graph(&_graph), reached(_reached),
    785108      own_reached_map(false) { }
    786     DfsIterator5(const Graph& _graph) :
     109    DfsIterator(const Graph& _graph) :
    787110      graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
    788111      own_reached_map(true) { }
    789     ~DfsIterator5() { if (own_reached_map) delete &reached; }
     112    ~DfsIterator() { if (own_reached_map) delete &reached; }
    790113    void pushAndSetReached(Node s) {
    791114      actual_node=s;
    … …  
    795118      dfs_stack.push(e);
    796119    }
    797     DfsIterator5<Graph, /*OutEdgeIt,*/ ReachedMap>&
     120    DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
    798121    operator++() {
    799122      actual_edge=dfs_stack.top();
    … …  
    829152  };
    830153
    831 
    832 
    833154} // namespace hugo
    834155

  • src/work/marci/bfsit_vs_byhand.cc

    r359 r360  
    5252  {
    5353    ts.reset();     
    54     BfsIterator5< Graph, Graph::NodeMap<bool> > bfs(G);
     54    BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G);
    5555    bfs.pushAndSetReached(s);
    5656    pred.set(s, INVALID);

  • src/work/marci/edmonds_karp.h

    r330 r360  
    276276      bool _augment=false;
    277277     
    278       BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
     278      BfsIterator< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
    279279      bfs.pushAndSetReached(s);
    280280       
    … …  
    340340      ResGW res_graph(*g, *capacity, *flow);
    341341
    342       BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
     342      BfsIterator< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
    343343
    344344      bfs.pushAndSetReached(s);
    … …  
    392392        //computing blocking flow with dfs
    393393
    394         DfsIterator5< MG, typename MG::NodeMap<bool> > dfs(F);
     394        DfsIterator< MG, typename MG::NodeMap<bool> > dfs(F);
    395395        typename MG::NodeMap<typename MG::Edge> pred(F);
    396396        pred.set(sF, INVALID);
    … …  
    450450
    451451      //bfs for distances on the residual graph
    452       BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
     452      BfsIterator< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
    453453      bfs.pushAndSetReached(s);
    454454      typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's
    … …  
    498498        __augment=false;
    499499        //computing blocking flow with dfs
    500         DfsIterator5< MG, typename MG::NodeMap<bool> > dfs(F);
     500        DfsIterator< MG, typename MG::NodeMap<bool> > dfs(F);
    501501        typename MG::NodeMap<typename MG::Edge> pred(F);
    502502        pred.set(sF, INVALID);
    … …  
    554554      ResGW res_graph(*g, *capacity, *flow);
    555555
    556       BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
     556      BfsIterator< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
    557557
    558558      bfs.pushAndSetReached(s);
    … …  
    594594        __augment=false;
    595595        //computing blocking flow with dfs
    596         DfsIterator5< ErasingResGW, typename ErasingResGW::NodeMap<bool> >
     596        DfsIterator< ErasingResGW, typename ErasingResGW::NodeMap<bool> >
    597597          dfs(erasing_res_graph);
    598598        typename ErasingResGW::NodeMap<typename ErasingResGW::OutEdgeIt>
    … …  
    729729     
    730730//       typedef typename AugGraph::NodeMap<bool> ReachedMap;
    731 //       BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > bfs(res_graph);
     731//       BfsIterator< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > bfs(res_graph);
    732732//       typename AugGraph::NodeMap<AugEdge> pred(res_graph);
    733733//       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
    … …  
    919919
    920920//       //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
    921 //       BfsIterator5<
     921//       BfsIterator<
    922922//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
    923923//      /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
    … …  
    959959//      //computing blocking flow with dfs
    960960//      typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
    961 //      DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
     961//      DfsIterator< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
    962962//        dfs(res_graph);
    963963//      typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID);

  • src/work/marci/iterator_bfs_demo.cc

    r317 r360  
    104104
    105105    cout << "bfs from s ..." << endl;
    106     BfsIterator5< Graph, Graph::NodeMap<bool> > bfs(G);
     106    BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G);
    107107    bfs.pushAndSetReached(s);
    108108    while (!bfs.finished()) {
    … …  
    137137
    138138    cout << "dfs from s ..." << endl;
    139     DfsIterator5< Graph, Graph::NodeMap<bool> > dfs(G);
     139    DfsIterator< Graph, Graph::NodeMap<bool> > dfs(G);
    140140    dfs.pushAndSetReached(s);
    141141    while (!dfs.finished()) {
    … …  
    180180
    181181    cout << "bfs from t ..." << endl;
    182     BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw);
     182    BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
    183183    bfs.pushAndSetReached(t);
    184184    while (!bfs.finished()) {
    … …  
    213213   
    214214    cout << "dfs from t ..." << endl;
    215     DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw);
     215    DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
    216216    dfs.pushAndSetReached(t);
    217217    while (!dfs.finished()) {
    … …  
    259259
    260260    cout << "bfs from t ..." << endl;
    261     BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw);
     261    BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
    262262    bfs.pushAndSetReached(t);
    263263    while (!bfs.finished()) {
    … …  
    292292   
    293293    cout << "dfs from t ..." << endl;
    294     DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw);
     294    DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
    295295    dfs.pushAndSetReached(t);
    296296    while (!dfs.finished()) {
Note: See TracChangeset for help on using the changeset viewer.