COIN-OR::LEMON - Graph Library

Changeset 303:1b377a730d02 in lemon-0.x for src/work/marci/bfs_iterator.h


Ignore:
Timestamp:
04/05/04 18:52:46 (17 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@421
Message:

konvergalunk, konvergalunk...

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci/bfs_iterator.h

    r301 r303  
    66#include <stack>
    77#include <utility>
    8 #include <graph_wrapper.h>
    98
    109namespace hugo {
     
    631630
    632631
    633   template <typename GraphWrapper, /*typename OutEdgeIt,*/
    634             typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
     632  template <typename Graph, /*typename OutEdgeIt,*/
     633            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
    635634  class BfsIterator5 {
    636     typedef typename GraphWrapper::Node Node;
    637     typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
    638     GraphWrapper G;
     635  protected:
     636    typedef typename Graph::Node Node;
     637    typedef typename Graph::OutEdgeIt OutEdgeIt;
     638    const Graph* graph;
    639639    std::queue<Node> bfs_queue;
    640640    ReachedMap& reached;
     
    643643    bool own_reached_map;
    644644  public:
    645     BfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
    646       G(_G), reached(_reached),
     645    BfsIterator5(const Graph& _graph, ReachedMap& _reached) :
     646      graph(&_graph), reached(_reached),
    647647      own_reached_map(false) { }
    648     BfsIterator5(const GraphWrapper& _G) :
    649       G(_G), reached(*(new ReachedMap(G /*, false*/))),
     648    BfsIterator5(const Graph& _graph) :
     649      graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
    650650      own_reached_map(true) { }
    651 //     BfsIterator5(const typename GraphWrapper::BaseGraph& _G,
    652 //               ReachedMap& _reached) :
    653 //       G(_G), reached(_reached),
    654 //       own_reached_map(false) { }
    655 //     BfsIterator5(const typename GraphWrapper::BaseGraph& _G) :
    656 //       G(_G), reached(*(new ReachedMap(G /*, false*/))),
    657 //       own_reached_map(true) { }
    658651    ~BfsIterator5() { if (own_reached_map) delete &reached; }
    659652    void pushAndSetReached(Node s) {
     
    661654      if (bfs_queue.empty()) {
    662655        bfs_queue.push(s);
    663         G./*getF*/first(actual_edge, s);
    664         if (G.valid(actual_edge)/*.valid()*/) {
    665           Node w=G.bNode(actual_edge);
    666           if (!reached.get(w)) {
     656        graph->first(actual_edge, s);
     657        if (graph->valid(actual_edge)) {
     658          Node w=graph->bNode(actual_edge);
     659          if (!reached[w]) {
    667660            bfs_queue.push(w);
    668661            reached.set(w, true);
     
    676669      }
    677670    }
    678     BfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>&
     671    BfsIterator5<Graph, /*OutEdgeIt,*/ ReachedMap>&
    679672    operator++() {
    680       if (G.valid(actual_edge)/*.valid()*/) {
    681         /*++*/G.next(actual_edge);
    682         if (G.valid(actual_edge)/*.valid()*/) {
    683           Node w=G.bNode(actual_edge);
    684           if (!reached.get(w)) {
     673      if (graph->valid(actual_edge)) {
     674        graph->next(actual_edge);
     675        if (graph->valid(actual_edge)) {
     676          Node w=graph->bNode(actual_edge);
     677          if (!reached[w]) {
    685678            bfs_queue.push(w);
    686679            reached.set(w, true);
     
    693686        bfs_queue.pop();
    694687        if (!bfs_queue.empty()) {
    695           G./*getF*/first(actual_edge, bfs_queue.front());
    696           if (G.valid(actual_edge)/*.valid()*/) {
    697             Node w=G.bNode(actual_edge);
    698             if (!reached.get(w)) {
     688          graph->first(actual_edge, bfs_queue.front());
     689          if (graph->valid(actual_edge)) {
     690            Node w=graph->bNode(actual_edge);
     691            if (!reached[w]) {
    699692              bfs_queue.push(w);
    700693              reached.set(w, true);
     
    711704    operator OutEdgeIt () const { return actual_edge; }
    712705    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
    713     bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
     706    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
    714707    Node aNode() const { return bfs_queue.front(); }
    715     Node bNode() const { return G.bNode(actual_edge); }
     708    Node bNode() const { return graph->bNode(actual_edge); }
    716709    const ReachedMap& getReachedMap() const { return reached; }
    717710    const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
     
    774767//   };
    775768
    776   template <typename GraphWrapper, /*typename OutEdgeIt,*/
    777             typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
     769  template <typename Graph, /*typename OutEdgeIt,*/
     770            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
    778771  class DfsIterator5 {
    779     typedef typename GraphWrapper::Node Node;
    780     typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
    781     GraphWrapper G;
     772  protected:
     773    typedef typename Graph::Node Node;
     774    typedef typename Graph::OutEdgeIt OutEdgeIt;
     775    const Graph* graph;
    782776    std::stack<OutEdgeIt> dfs_stack;
    783777    bool b_node_newly_reached;
     
    787781    bool own_reached_map;
    788782  public:
    789     DfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
    790       G(_G), reached(_reached),
     783    DfsIterator5(const Graph& _graph, ReachedMap& _reached) :
     784      graph(&_graph), reached(_reached),
    791785      own_reached_map(false) { }
    792     DfsIterator5(const GraphWrapper& _G) :
    793       G(_G), reached(*(new ReachedMap(G /*, false*/))),
     786    DfsIterator5(const Graph& _graph) :
     787      graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
    794788      own_reached_map(true) { }
    795789    ~DfsIterator5() { if (own_reached_map) delete &reached; }
     
    798792      reached.set(s, true);
    799793      OutEdgeIt e;
    800       G.first(e, s);
     794      graph->first(e, s);
    801795      dfs_stack.push(e);
    802796    }
    803     DfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>&
     797    DfsIterator5<Graph, /*OutEdgeIt,*/ ReachedMap>&
    804798    operator++() {
    805799      actual_edge=dfs_stack.top();
    806800      //actual_node=G.aNode(actual_edge);
    807       if (G.valid(actual_edge)/*.valid()*/) {
    808         Node w=G.bNode(actual_edge);
     801      if (graph->valid(actual_edge)/*.valid()*/) {
     802        Node w=graph->bNode(actual_edge);
    809803        actual_node=w;
    810         if (!reached.get(w)) {
     804        if (!reached[w]) {
    811805          OutEdgeIt e;
    812           G.first(e, w);
     806          graph->first(e, w);
    813807          dfs_stack.push(e);
    814808          reached.set(w, true);
    815809          b_node_newly_reached=true;
    816810        } else {
    817           actual_node=G.aNode(actual_edge);
    818           /*++*/G.next(dfs_stack.top());
     811          actual_node=graph->aNode(actual_edge);
     812          graph->next(dfs_stack.top());
    819813          b_node_newly_reached=false;
    820814        }
     
    828822    operator OutEdgeIt () const { return actual_edge; }
    829823    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
    830     bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
     824    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
    831825    Node aNode() const { return actual_node; /*FIXME*/}
    832826    Node bNode() const { return G.bNode(actual_edge); }
Note: See TracChangeset for help on using the changeset viewer.