COIN-OR::LEMON - Graph Library

Changeset 75:87623302a68f in lemon-0.x for src/work/bfs_iterator.hh


Ignore:
Timestamp:
02/16/04 12:29:48 (17 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@98
Message:

.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/bfs_iterator.hh

    r64 r75  
    44#include <queue>
    55#include <stack>
     6#include <utility>
     7#include <graph_wrapper.h>
    68
    79namespace marci {
     
    467469 };
    468470
     471
     472  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
     473  class BfsIterator3 {
     474    typedef typename Graph::NodeIt NodeIt;
     475    const Graph& G;
     476    std::queue< std::pair<NodeIt, 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(NodeIt s) {
     483      reached.set(s, true);
     484      if (bfs_queue.empty()) {
     485        bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
     486        actual_edge=bfs_queue.front().second;
     487        if (actual_edge.valid()) {
     488          NodeIt w=G.bNode(actual_edge);
     489          if (!reached.get(w)) {
     490            bfs_queue.push(std::pair<NodeIt, 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<NodeIt, 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          NodeIt w=G.bNode(actual_edge);
     509          if (!reached.get(w)) {
     510            bfs_queue.push(std::pair<NodeIt, 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            NodeIt w=G.bNode(actual_edge);
     523            if (!reached.get(w)) {
     524              bfs_queue.push(std::pair<NodeIt, 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    NodeIt aNode() const { return bfs_queue.front().first; }
     540    NodeIt bNode() const { return G.bNode(actual_edge); }
     541    const ReachedMap& getReachedMap() const { return reached; }
     542    //const std::queue< std::pair<NodeIt, OutEdgeIt> >& getBfsQueue() const { return bfs_queue; }
     543 };
     544
     545  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
     546  class BfsIterator4 {
     547    typedef typename Graph::NodeIt NodeIt;
     548    const Graph& G;
     549    std::queue<NodeIt> bfs_queue;
     550    ReachedMap reached;
     551    bool b_node_newly_reached;
     552    OutEdgeIt actual_edge;
     553  public:
     554    BfsIterator4(const Graph& _G) : G(_G), reached(G, false) { }
     555    void pushAndSetReached(NodeIt s) {
     556      reached.set(s, true);
     557      if (bfs_queue.empty()) {
     558        bfs_queue.push(s);
     559        G.getFirst(actual_edge, s);
     560        if (actual_edge.valid()) {
     561          NodeIt w=G.bNode(actual_edge);
     562          if (!reached.get(w)) {
     563            bfs_queue.push(w);
     564            reached.set(w, true);
     565            b_node_newly_reached=true;
     566          } else {
     567            b_node_newly_reached=false;
     568          }
     569        }
     570      } else {
     571        bfs_queue.push(s);
     572      }
     573    }
     574    BfsIterator4<Graph, OutEdgeIt, ReachedMap>&
     575    operator++() {
     576      if (actual_edge.valid()) {
     577        ++actual_edge;
     578        if (actual_edge.valid()) {
     579          NodeIt w=G.bNode(actual_edge);
     580          if (!reached.get(w)) {
     581            bfs_queue.push(w);
     582            reached.set(w, true);
     583            b_node_newly_reached=true;
     584          } else {
     585            b_node_newly_reached=false;
     586          }
     587        }
     588      } else {
     589        bfs_queue.pop();
     590        if (!bfs_queue.empty()) {
     591          G.getFirst(actual_edge, bfs_queue.front());
     592          if (actual_edge.valid()) {
     593            NodeIt w=G.bNode(actual_edge);
     594            if (!reached.get(w)) {
     595              bfs_queue.push(w);
     596              reached.set(w, true);
     597              b_node_newly_reached=true;
     598            } else {
     599              b_node_newly_reached=false;
     600            }
     601          }
     602        }
     603      }
     604      return *this;
     605    }
     606    bool finished() const { return bfs_queue.empty(); }
     607    operator OutEdgeIt () const { return actual_edge; }
     608    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
     609    bool isANodeExamined() const { return !(actual_edge.valid()); }
     610    NodeIt aNode() const { return bfs_queue.front(); }
     611    NodeIt bNode() const { return G.bNode(actual_edge); }
     612    const ReachedMap& getReachedMap() const { return reached; }
     613    const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
     614 };
     615
     616
     617  template <typename GraphWrapper, typename ReachedMap>
     618  class BfsIterator5 {
     619    typedef typename GraphWrapper::NodeIt NodeIt;
     620    typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
     621    GraphWrapper gw;
     622    std::queue<NodeIt> bfs_queue;
     623    ReachedMap reached;
     624    bool b_node_newly_reached;
     625    OutEdgeIt actual_edge;
     626  public:
     627    BfsIterator5(GraphWrapper _gw) :
     628      gw(_gw), reached(_gw.getGraph()) { }
     629    void pushAndSetReached(NodeIt s) {
     630      reached.set(s, true);
     631      if (bfs_queue.empty()) {
     632        bfs_queue.push(s);
     633        gw.getFirst(actual_edge, s);
     634        if (actual_edge.valid()) {
     635          NodeIt w=gw.bNode(actual_edge);
     636          if (!reached.get(w)) {
     637            bfs_queue.push(w);
     638            reached.set(w, true);
     639            b_node_newly_reached=true;
     640          } else {
     641            b_node_newly_reached=false;
     642          }
     643        }
     644      } else {
     645        bfs_queue.push(s);
     646      }
     647    }
     648    BfsIterator5<GraphWrapper, ReachedMap>&
     649    operator++() {
     650      if (actual_edge.valid()) {
     651        ++actual_edge;
     652        if (actual_edge.valid()) {
     653          NodeIt w=gw.bNode(actual_edge);
     654          if (!reached.get(w)) {
     655            bfs_queue.push(w);
     656            reached.set(w, true);
     657            b_node_newly_reached=true;
     658          } else {
     659            b_node_newly_reached=false;
     660          }
     661        }
     662      } else {
     663        bfs_queue.pop();
     664        if (!bfs_queue.empty()) {
     665          gw.getFirst(actual_edge, bfs_queue.front());
     666          if (actual_edge.valid()) {
     667            NodeIt w=gw.bNode(actual_edge);
     668            if (!reached.get(w)) {
     669              bfs_queue.push(w);
     670              reached.set(w, true);
     671              b_node_newly_reached=true;
     672            } else {
     673              b_node_newly_reached=false;
     674            }
     675          }
     676        }
     677      }
     678      return *this;
     679    }
     680    bool finished() const { return bfs_queue.empty(); }
     681    operator OutEdgeIt () const { return actual_edge; }
     682    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
     683    bool isANodeExamined() const { return !(actual_edge.valid()); }
     684    NodeIt aNode() const { return bfs_queue.front(); }
     685    NodeIt bNode() const { return gw.bNode(actual_edge); }
     686    const ReachedMap& getReachedMap() const { return reached; }
     687    const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
     688 };
     689
     690
     691
    469692} // namespace marci
    470693
Note: See TracChangeset for help on using the changeset viewer.