source: lemon-0.x/src/work/marci/bfs_iterator.h @ 470:b64956c701c9

// -*- c++ -*-
#ifndef HUGO_BFS_ITERATOR_H
#define HUGO_BFS_ITERATOR_H

#include <queue>
#include <stack>
#include <utility>

namespace hugo {

  template <typename Graph, /*typename OutEdgeIt,*/ 
            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
  class BfsIterator {
  protected:
    typedef typename Graph::Node Node;
    typedef typename Graph::OutEdgeIt OutEdgeIt;
    const Graph* graph;
    std::queue<Node> bfs_queue;
    ReachedMap& reached;
    bool b_node_newly_reached;
    OutEdgeIt actual_edge;
    bool own_reached_map;
  public:
    BfsIterator(const Graph& _graph, ReachedMap& _reached) : 
      graph(&_graph), reached(_reached), 
      own_reached_map(false) { }
    BfsIterator(const Graph& _graph) : 
      graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), 
      own_reached_map(true) { }
    ~BfsIterator() { if (own_reached_map) delete &reached; }
    /// This method markes s reached.
    /// If the queue is empty, then s is pushed in the bfs queue 
    /// and the first OutEdgeIt is processed.
    /// If the queue is not empty, then s is simply pushed.
    void pushAndSetReached(Node s) { 
      reached.set(s, true);
      if (bfs_queue.empty()) {
        bfs_queue.push(s);
        graph->first(actual_edge, s);
        if (graph->valid(actual_edge)) { 
          Node w=graph->bNode(actual_edge);
          if (!reached[w]) {
            bfs_queue.push(w);
            reached.set(w, true);
            b_node_newly_reached=true;
          } else {
            b_node_newly_reached=false;
          }
        } 
      } else {
        bfs_queue.push(s);
      }
    }
    /// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator, 
    /// its \c operator++() iterates on the edges in a bfs order.
    BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& 
    operator++() { 
      if (graph->valid(actual_edge)) { 
        graph->next(actual_edge);
        if (graph->valid(actual_edge)) {
          Node w=graph->bNode(actual_edge);
          if (!reached[w]) {
            bfs_queue.push(w);
            reached.set(w, true);
            b_node_newly_reached=true;
          } else {
            b_node_newly_reached=false;
          }
        }
      } else {
        bfs_queue.pop(); 
        if (!bfs_queue.empty()) {
          graph->first(actual_edge, bfs_queue.front());
          if (graph->valid(actual_edge)) {
            Node w=graph->bNode(actual_edge);
            if (!reached[w]) {
              bfs_queue.push(w);
              reached.set(w, true);
              b_node_newly_reached=true;
            } else {
              b_node_newly_reached=false;
            }
          }
        }
      }
      return *this;
    }
    bool finished() const { return bfs_queue.empty(); }
    /// The conversion operator makes for converting the bfs-iterator 
    /// to an \c out-edge-iterator.
    operator OutEdgeIt() const { return actual_edge; }
    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
    Node aNode() const { return bfs_queue.front(); }
    Node bNode() const { return graph->bNode(actual_edge); }
    const ReachedMap& getReachedMap() const { return reached; }
    const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
  };  

  /// Bfs searches from s for the nodes wich are not marked in 
  /// \c reached_map
  /// Reached is a read-write bool-map, Pred is a write-nodemap 
  /// and dist is an rw-nodemap, have to be.
  template <typename Graph, 
            typename ReachedMap=typename Graph::template NodeMap<bool>, 
            typename PredMap
            =typename Graph::template NodeMap<typename Graph::Edge>, 
            typename DistMap=typename Graph::template NodeMap<int> > 
  class Bfs : public BfsIterator<Graph, ReachedMap> {
    typedef BfsIterator<Graph, ReachedMap> Parent;
  protected:
    typedef typename Parent::Node Node;
    PredMap& pred;
    DistMap& dist;
  public:
    Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred), dist(&_dist) { }
    /// s is marked to be reached and pushed in the bfs queue.
    /// If the queue is empty, then the first out-edge is processed.
    /// If s was not marked previously, then 
    /// in addition its pred is set to be INVALID, and dist to 0. 
    /// if s was marked previuosly, then it is simply pushed.
    void push(Node s) { 
      if (this->reached[s]) {
        Parent::pushAndSetReached(s);
      } else {
        Parent::pushAndSetReached(s);
        pred.set(s, INVALID);
        dist.set(s, 0);
      }
    }
    /// A bfs is processed from s.
    void run(Node s) {
      push(s);
      while (!this->finished()) this->operator++();
    }
    Bfs<Graph, ReachedMap, PredMap, DistMap> operator++() {
      Parent::operator++();
      if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) 
      {
        pred.set(this->bNode(), this->actual_edge);
        dist.set(this->bNode(), dist[this->aNode()]);
      }
      return *this;
    }
    const PredMap& getPredMap() const { return pred; }
    const DistMap& getDistMap() const { return dist; }
  };

  template <typename Graph, /*typename OutEdgeIt,*/ 
            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
  class DfsIterator {
  protected:
    typedef typename Graph::Node Node;
    typedef typename Graph::OutEdgeIt OutEdgeIt;
    const Graph* graph;
    std::stack<OutEdgeIt> dfs_stack;
    bool b_node_newly_reached;
    OutEdgeIt actual_edge;
    Node actual_node;
    ReachedMap& reached;
    bool own_reached_map;
  public:
    DfsIterator(const Graph& _graph, ReachedMap& _reached) : 
      graph(&_graph), reached(_reached), 
      own_reached_map(false) { }
    DfsIterator(const Graph& _graph) : 
      graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), 
      own_reached_map(true) { }
    ~DfsIterator() { if (own_reached_map) delete &reached; }
    void pushAndSetReached(Node s) { 
      actual_node=s;
      reached.set(s, true);
      OutEdgeIt e;
      graph->first(e, s);
      dfs_stack.push(e); 
    }
    DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& 
    operator++() { 
      actual_edge=dfs_stack.top();
      //actual_node=G.aNode(actual_edge);
      if (graph->valid(actual_edge)/*.valid()*/) { 
        Node w=graph->bNode(actual_edge);
        actual_node=w;
        if (!reached[w]) {
          OutEdgeIt e;
          graph->first(e, w);
          dfs_stack.push(e);
          reached.set(w, true);
          b_node_newly_reached=true;
        } else {
          actual_node=graph->aNode(actual_edge);
          graph->next(dfs_stack.top());
          b_node_newly_reached=false;
        }
      } else {
        //actual_node=G.aNode(dfs_stack.top());
        dfs_stack.pop();
      }
      return *this;
    }
    bool finished() const { return dfs_stack.empty(); }
    operator OutEdgeIt() const { return actual_edge; }
    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
    Node aNode() const { return actual_node; /*FIXME*/}
    Node bNode() const { return graph->bNode(actual_edge); }
    const ReachedMap& getReachedMap() const { return reached; }
    const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
  };

  /// Dfs searches from s for the nodes wich are not marked in 
  /// \c reached_map
  /// Reached is a read-write bool-map, Pred is a write-nodemap, have to be.
  template <typename Graph, 
            typename ReachedMap=typename Graph::template NodeMap<bool>, 
            typename PredMap
            =typename Graph::template NodeMap<typename Graph::Edge> > 
  class Dfs : public DfsIterator<Graph, ReachedMap> {
    typedef DfsIterator<Graph, ReachedMap> Parent;
  protected:
    typedef typename Parent::Node Node;
    PredMap& pred;
  public:
    Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred) { }
    /// s is marked to be reached and pushed in the bfs queue.
    /// If the queue is empty, then the first out-edge is processed.
    /// If s was not marked previously, then 
    /// in addition its pred is set to be INVALID. 
    /// if s was marked previuosly, then it is simply pushed.
    void push(Node s) { 
      if (this->reached[s]) {
        Parent::pushAndSetReached(s);
      } else {
        Parent::pushAndSetReached(s);
        pred.set(s, INVALID);
      }
    }
    /// A bfs is processed from s.
    void run(Node s) {
      push(s);
      while (!this->finished()) this->operator++();
    }
    Dfs<Graph, ReachedMap, PredMap> operator++() {
      Parent::operator++();
      if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) 
      {
        pred.set(this->bNode(), this->actual_edge);
      }
      return *this;
    }
    const PredMap& getPredMap() const { return pred; }
  };


} // namespace hugo

#endif //HUGO_BFS_ITERATOR_H