source: lemon-0.x/src/work/marci/bfs_mm.h @ 1327:ecc1cdea2ee7

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

/// \ingroup galgs
/// \file
/// \brief Bfs and dfs iterators.
///
/// This file contains bfs and dfs iterator classes.
///
// /// \author Marton Makai

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

#include <lemon/invalid.h>

namespace lemon {
  namespace marci {

  /// Bfs searches for the nodes wich are not marked in 
  /// \c reached_map
  /// RM have to be a read-write bool node-map.
  /// \ingroup galgs
  template <typename Graph, /*typename OutEdgeIt,*/ 
            typename RM/*=typename Graph::NodeMap<bool>*/ >
  class BfsIterator {
  public:
    typedef RM ReachedMap;
  protected:
    typedef typename Graph::Node Node;
    typedef typename Graph::Edge Edge;
    typedef typename Graph::OutEdgeIt OutEdgeIt;
    const Graph* graph;
    std::queue<Node> bfs_queue;
    ReachedMap* reached_map;
    bool b_node_newly_reached;
    //OutEdgeIt actual_edge;
    Edge actual_edge;
    /// \e
    BfsIterator(const Graph& _graph) : graph(&_graph), reached_map(0) { }
    /// RM have to be set before any bfs operation.
    BfsIterator<Graph, RM>& setReached(RM& _reached_map) {
      reached_map=&_reached_map;
    }
  public:
    /// In that constructor \c _reached_map have to be a reference 
    /// for a bool bode-map. The algorithm will search for the 
    /// initially \c false nodes 
    /// in a bfs order.
    BfsIterator(const Graph& _graph, ReachedMap& _reached_map) : 
      graph(&_graph), reached_map(&_reached_map) { }
    /// The same as above, but the map storing the reached nodes 
    /// is constructed dynamically to everywhere false.
    /// \deprecated
//     BfsIterator(const Graph& _graph) : 
//       graph(&_graph), reached_map(new ReachedMap(*graph /*, false*/)), 
//       own_reached_map(true) { }
//     /// The map storing the reached nodes have to be destroyed if 
//     /// it was constructed dynamically
//     ~BfsIterator() { if (own_reached_map) delete reached_map; }
    /// This method markes \c s reached.
    /// If the queue is empty, then \c s is pushed in the bfs queue 
    /// and the first out-edge is processed.
    /// If the queue is not empty, then \c s is simply pushed.
    BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& pushAndSetReached(Node s) { 
      reached_map->set(s, true);
      if (bfs_queue.empty()) {
        bfs_queue.push(s);
        actual_edge=OutEdgeIt(*graph, s);
        //graph->first(actual_edge, s);
        if (actual_edge!=INVALID) { 
          Node w=graph->target(actual_edge);
          if (!(*reached_map)[w]) {
            bfs_queue.push(w);
            reached_map->set(w, true);
            b_node_newly_reached=true;
          } else {
            b_node_newly_reached=false;
          }
        } 
      } else {
        bfs_queue.push(s);
      }
      return *this;
    }
    /// 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 (actual_edge!=INVALID) { 
        actual_edge=++OutEdgeIt(*graph, actual_edge);
        //++actual_edge;
        if (actual_edge!=INVALID) {
          Node w=graph->target(actual_edge);
          if (!(*reached_map)[w]) {
            bfs_queue.push(w);
            reached_map->set(w, true);
            b_node_newly_reached=true;
          } else {
            b_node_newly_reached=false;
          }
        }
      } else {
        bfs_queue.pop(); 
        if (!bfs_queue.empty()) {
          actual_edge=OutEdgeIt(*graph, bfs_queue.front());
          //graph->first(actual_edge, bfs_queue.front());
          if (actual_edge!=INVALID) {
            Node w=graph->target(actual_edge);
            if (!(*reached_map)[w]) {
              bfs_queue.push(w);
              reached_map->set(w, true);
              b_node_newly_reached=true;
            } else {
              b_node_newly_reached=false;
            }
          }
        }
      }
      return *this;
    }
    /// Returns true iff the algorithm is finished.
    bool finished() const { return bfs_queue.empty(); }
    /// The conversion operator makes for converting the bfs-iterator 
    /// to an \c out-edge-iterator.
    ///\bug Edge have to be in LEMON 0.2
    operator Edge() const { return actual_edge; }
    /// Returns if b-node has been reached just now.
    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
    /// Returns if a-node is examined.
    bool isANodeExamined() const { return actual_edge==INVALID; }
    /// Returns a-node of the actual edge, so does if the edge is invalid.
    Node source() const { return bfs_queue.front(); }
    /// \pre The actual edge have to be valid.
    Node target() const { return graph->target(actual_edge); }
    /// Guess what?
    /// \deprecated 
    const ReachedMap& reachedMap() const { return *reached_map; }
    /// Guess what?
    /// \deprecated 
    typename ReachedMap::Value reached(const Node& n) const { 
      return (*reached_map)[n]; 
    }
    /// Guess what?
    /// \deprecated
    const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
  };

  /// Bfs searches for the nodes wich are not marked in 
  /// \c reached_map
  /// RM have to work as a read-write bool Node-map, 
  /// PM is a write edge node-map and
  /// PNM is a write node node-map and
  /// DM is a read-write node-map of integral value, have to be. 
  /// \ingroup galgs
  template <typename Graph, 
            typename RM=typename Graph::template NodeMap<bool>, 
            typename PM
            =typename Graph::template NodeMap<typename Graph::Edge>, 
            typename PNM
            =typename Graph::template NodeMap<typename Graph::Node>, 
            typename DM=typename Graph::template NodeMap<int> > 
  class Bfs : public BfsIterator<Graph, RM> {
    typedef BfsIterator<Graph, RM> Parent;
  public:
    typedef RM ReachedMap;
    typedef PM PredMap;
    typedef PNM PredNodeMap;
    typedef DM DistMap;
  protected:
    typedef typename Parent::Node Node;
    PredMap* pred_map;
    PredNodeMap* pred_node_map;
    DistMap* dist_map;
    /// \e
    Bfs<Graph, RM, PM, PNM, DM>
    (const Graph& _graph) : BfsIterator<Graph, RM>(_graph) { }
    /// PM have to be set before any bfs operation.
    Bfs<Graph, RM, PM, PNM, DM>& 
    setPredMap(PredMap& _pred_map) {
      pred_map=&_pred_map;
    }
    /// PredNodeMap have to be set before any bfs operation.
    Bfs<Graph, RM, PM, PNM, DM>& 
    setPredNodeMap(PredNodeMap& _pred_node_map) {
      pred_node_map=&_pred_node_map;
    }
    /// DistMap have to be set before any bfs operation.
    Bfs<Graph, RM, PM, PNM, DM>& 
    setDistMap(DistMap& _dist_map) {
      dist_map=&_dist_map;
    }
  public:
    /// The algorithm will search in a bfs order for 
    /// the nodes which are \c false initially. 
    /// The constructor makes no initial changes on the maps.
    Bfs<Graph, RM, PM, PNM, DM>
    (const Graph& _graph, ReachedMap& _reached_map, 
     PredMap& _pred_map, PredNodeMap& _pred_node_map, 
     DistMap& _dist_map) : BfsIterator<Graph, RM>(_graph, _reached_map), 
      pred_map(&_pred_map), pred_node_map(&_pred_node_map), 
                           dist_map(&_dist_map) { }
    /// \c 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 \c s was not marked previously, then 
    /// in addition its pred_map is set to be \c INVALID, 
    /// and dist_map to \c 0. 
    /// if \c s was marked previuosly, then it is simply pushed.
    Bfs<Graph, RM, PM, PNM, DM>& push(Node s) { 
      if ((*(this->reached_map))[s]) {
        Parent::pushAndSetReached(s);
      } else {
        Parent::pushAndSetReached(s);
        pred_map->set(s, INVALID);
        pred_node_map->set(s, INVALID);
        dist_map->set(s, 0);
      }
      return *this;
    }
    /// A bfs is processed from \c s.
    Bfs<Graph, RM, PM, PNM, DM>& run(Node s) {
      push(s);
      while (!this->finished()) this->operator++();
      return *this;
    }
    /// Beside the bfs iteration, \c pred_map and \dist_map are saved in a 
    /// newly reached node. 
    Bfs<Graph, RM, PM, PNM, DM>& operator++() {
      Parent::operator++();
      if ((this->actual_edge)!=INVALID && this->b_node_newly_reached) 
      {
        pred_map->set(this->target(), this->actual_edge);
        pred_node_map->set(this->target(), this->source());
        dist_map->set(this->target(), (*dist_map)[this->source()]);
      }
      return *this;
    }
    /// Guess what?
    /// \deprecated 
    const PredMap& predMap() const { return *pred_map; }
    /// Guess what?
    /// \deprecated 
    typename PredMap::Value pred(const Node& n) const { 
      return (*pred_map)[n]; 
    }
    /// Guess what?
    /// \deprecated 
    const PredNodeMap& predNodeMap() const { return *pred_node_map; }
    /// Guess what?
    /// \deprecated 
    typename PredNodeMap::Value predNode(const Node& n) const { 
      return (*pred_node_map)[n]; 
    }
    /// Guess what?
    /// \deprecated
    const DistMap& distMap() const { return *dist_map; }
    /// Guess what?
    /// \deprecated 
    typename DistMap::Value dist(const Node& n) const { 
      return (*dist_map)[n]; 
    }
  };

//   template <typename Graph, 
//          typename RM=typename Graph::template NodeMap<bool>, 
//          typename PM
//          =typename Graph::template NodeMap<typename Graph::Edge>, 
//          typename PredNodeMap
//          =typename Graph::template NodeMap<typename Graph::Node>, 
//          typename DistMap=typename Graph::template NodeMap<int> > 
//     class BfsWizard : public Bfs<Graph> {
//     public:
//       typedef Bfs<Graph, PM, PredNodeMap, DistMap> Parent;
//     protected:
//       typedef typename Parent::Node Node;
//       bool own_reached_map;
//       bool own_pred_map;
//       bool own_pred_node_map;
//       bool own_dist_map;

//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 
//       makeRreached() { 
//      own_reached_map=true;
//      reached=new ReachedMap(*graph, false);
//       }
//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 
//       deleteReachedMap() { 
//      own_reached_map=false;
//      delete reached;
//       }

//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 
//       makePM() { 
//      own_pred_map=true;
//      pred_map=new PM(*graph, INVALID);
//       }
//       BfsWizard<Graph, ReachedMap, PM, PredNodeMap, DistMap>& 
//       deletePM() { 
//      own_pred_map=false;
//      delete pred_map;
//       }

//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 
//       makePredNodeMap() { 
//      own_pred_node_map=true;
//      pred_node_map=new PredNodeMap(*graph, INVALID);
//       }
//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 
//       deletePredNodeMap() { 
//      own_pred_node_map=false;
//      delete pred_node_map;
//       }

//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 
//       makeDistMap() { 
//      own_dist_map=true;
//      dist_map=new DistMap(*graph, 0);
//       }
//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 
//       deleteDistMap() { 
//      own_dist_map=false;
//      delete dist_map;
//       }

//     public:
//       /// User friendly Bfs class.
//       /// The maps which are not explicitly given by the user are 
//       /// constructed with false, INVALID, INVALID and 0 values.
//       /// For the user defined maps, the values are not modified, and 
//       /// the bfs is processed without any preset on maps. Therefore, 
//       /// the bfs will search only the nodes which are set false previously 
//       /// in reached, and in the nodes wich are not newly reached by the 
//       /// search, the map values are not modified.
//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>
//       (const Graph& _graph) : 
//      own_reached_map(false), 
//      own_pred_map(false), 
//      own_pred_node_map(false), 
//      own_dist_map(false) { 
//       }

//       /// \e
//       ~BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>() { 
//      if (own_reached_map) deleteReachedMap();
//      if (own_pred_map) deletePM();
//      if (own_pred_node_map) deletePredNodeMap();
//      if (own_dist_map) deleteDistMap();
//       }

//       /// \e
//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 
//       setReachedMap(ReachedMap& _reached) {
//      if (own_reached_map) deleteReachedMap();
//      Parent::setReachedMap(_reached);
//       }
//       /// \e
//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 
//       setPM(PM& _pred) {
//      if (own_pred_map) deletePM();
//      Parent::setPM(_pred);
//       }
//       /// \e
//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 
//       setPredNodeMap(PredNodeMap& _pred_node) {
//      if (own_pred_node_map) deletePredNodeMap();
//      Parent::setPredNodeMap(_pred_node);
//       }
//       /// \e
//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 
//       setDistMap(DistMap& _dist) {
//      if (own_dist_map) deleteDistMap();
//      Parent::setDistMap(_dist);
//       }

//       /// \e
//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 
//       push(Node s) { 
//      if (!reached) makeReachedMap();
//      if (!pred_map) makePMMap();
//      if (!pred_node_map) makePredNodeMap();
//      if (!dist_map) makeDistMap();
//      push(s);
//      return *this;
//       }

//       /// \e
//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 
//       operator++() { 
//      if (!reached) makeRM();
//      if (!pred_map) makePMMap();
//      if (!pred_node_map) makePredNodeMap();
//      if (!dist_map) makeDistMap();
//      ++(*this);
//      return *this;
//       }

//       /// \e
//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 
//       run(Node s) { 
//      if (!reached) makeRM();
//      if (!pred_map) makePMMap();
//      if (!pred_node_map) makePredNodeMap();
//      if (!dist_map) makeDistMap();
//      run(s);
//      return *this;
//       }
      
//     };


  /// Dfs searches for the nodes wich are not marked in 
  /// \c reached_map
  /// Reached have to be a read-write bool Node-map.
  /// \ingroup galgs
  template <typename Graph, /*typename OutEdgeIt,*/ 
            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
  class DfsIterator {
  protected:
    typedef typename Graph::Node Node;
    typedef typename Graph::Edge Edge;
    typedef typename Graph::OutEdgeIt OutEdgeIt;
    const Graph* graph;
    std::stack<OutEdgeIt> dfs_stack;
    bool b_node_newly_reached;
    Edge actual_edge;
    Node actual_node;
    ReachedMap& reached;
    bool own_reached_map;
  public:
    /// In that constructor \c _reached have to be a reference 
    /// for a bool node-map. The algorithm will search in a dfs order for 
    /// the nodes which are \c false initially
    DfsIterator(const Graph& _graph, ReachedMap& _reached) : 
      graph(&_graph), reached(_reached), 
      own_reached_map(false) { }
    /// The same as above, but the map of reached nodes is 
    /// constructed dynamically 
    /// to everywhere false.
    DfsIterator(const Graph& _graph) : 
      graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), 
      own_reached_map(true) { }
    ~DfsIterator() { if (own_reached_map) delete &reached; }
    /// This method markes s reached and first out-edge is processed.
    DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& pushAndSetReached(Node s) { 
      actual_node=s;
      reached.set(s, true);
      OutEdgeIt e(*graph, s);
      //graph->first(e, s);
      dfs_stack.push(e); 
      return *this;
    }
    /// As \c DfsIterator<Graph, ReachedMap> works as an edge-iterator, 
    /// its \c operator++() iterates on the edges in a dfs order.
    DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& 
    operator++() { 
      actual_edge=dfs_stack.top();
      if (actual_edge!=INVALID/*.valid()*/) { 
        Node w=graph->target(actual_edge);
        actual_node=w;
        if (!reached[w]) {
          OutEdgeIt e(*graph, w);
          //graph->first(e, w);
          dfs_stack.push(e);
          reached.set(w, true);
          b_node_newly_reached=true;
        } else {
          actual_node=graph->source(actual_edge);
          ++dfs_stack.top();
          b_node_newly_reached=false;
        }
      } else {
        //actual_node=G.aNode(dfs_stack.top());
        dfs_stack.pop();
      }
      return *this;
    }
    /// Returns true iff the algorithm is finished.
    bool finished() const { return dfs_stack.empty(); }
    /// The conversion operator makes for converting the bfs-iterator 
    /// to an \c out-edge-iterator.
    ///\bug Edge have to be in LEMON 0.2
    operator Edge() const { return actual_edge; }
    /// Returns if b-node has been reached just now.
    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
    /// Returns if a-node is examined.
    bool isANodeExamined() const { return actual_edge==INVALID; }
    /// Returns a-node of the actual edge, so does if the edge is invalid.
    Node source() const { return actual_node; /*FIXME*/}
    /// Returns b-node of the actual edge. 
    /// \pre The actual edge have to be valid.
    Node target() const { return graph->target(actual_edge); }
    /// Guess what?
    /// \deprecated
    const ReachedMap& getReachedMap() const { return reached; }
    /// Guess what?
    /// \deprecated
    const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
  };

  /// Dfs searches for the nodes wich are not marked in 
  /// \c reached_map
  /// Reached is a read-write bool node-map, 
  /// Pred is a write node-map, have to be.
  /// \ingroup galgs
  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:
    /// The algorithm will search in a dfs order for 
    /// the nodes which are \c false initially. 
    /// The constructor makes no initial changes on the maps.
    Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(_pred) { }
    /// \c 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 \c s was not marked previously, then 
    /// in addition its pred is set to be \c INVALID. 
    /// if \c s was marked previuosly, then it is simply pushed.
    Dfs<Graph, ReachedMap, PredMap>& push(Node s) { 
      if (this->reached[s]) {
        Parent::pushAndSetReached(s);
      } else {
        Parent::pushAndSetReached(s);
        pred.set(s, INVALID);
      }
      return *this;
    }
    /// A bfs is processed from \c s.
    Dfs<Graph, ReachedMap, PredMap>& run(Node s) {
      push(s);
      while (!this->finished()) this->operator++();
      return *this;
    }
    /// Beside the dfs iteration, \c pred is saved in a 
    /// newly reached node. 
    Dfs<Graph, ReachedMap, PredMap>& operator++() {
      Parent::operator++();
      if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) 
      {
        pred.set(this->target(), this->actual_edge);
      }
      return *this;
    }
    /// Guess what?
    /// \deprecated
    const PredMap& getPredMap() const { return pred; }
  };

  } // namespace marci
} // namespace lemon

#endif //LEMON_BFS_DFS_H