COIN-OR::LEMON - Graph Library

Changeset 448:510c53fd06cd in lemon-0.x


Ignore:
Timestamp:
04/27/04 18:27:08 (20 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@596
Message:

bfs, dfs, bfsiterator, dfsiterator for alpar's sake of being much more standardized.

File:
1 edited

Legend:

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

    r415 r448  
    2929      own_reached_map(true) { }
    3030    ~BfsIterator() { if (own_reached_map) delete &reached; }
    31     //s is marcked reached.
    32     //if the queue is empty, then the its is pushed ant the first OutEdgeIt is processe.
    33     //is the queue is not empty, then is it pushed.
     31    /// This method markes s reached.
     32    /// If the queue is empty, then s is pushed in the bfs queue
     33    /// and the first OutEdgeIt is processed.
     34    /// If the queue is not empty, then s is simply pushed.
    3435    void pushAndSetReached(Node s) {
    3536      reached.set(s, true);
     
    5152      }
    5253    }
     54    /// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator,
     55    /// its \c operator++() iterates on the edges in a bfs order.
    5356    BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
    5457    operator++() {
     
    8487    }
    8588    bool finished() const { return bfs_queue.empty(); }
     89    /// The conversion operator makes for converting the bfs-iterator
     90    /// to an \c out-edge-iterator.
    8691    operator OutEdgeIt() const { return actual_edge; }
    8792    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
     
    9499
    95100  /// Bfs searches from s for the nodes wich are not marked in
    96   /// reachedmap
     101  /// \c reached_map
     102  /// Reached is a read-write bool-map, Pred is a write-nodemap
     103  /// and dist is an rw-nodemap, have to be.
    97104  template <typename Graph,
    98105            typename ReachedMap=typename Graph::template NodeMap<bool>,
     
    108115  public:
    109116    Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred), dist(&_dist) { }
    110     //s is marked to be reached and pushed in the bfs queue.
    111     //if the queue is empty, then the first out-edge is processed
    112     //If s was not marked previously, then
    113     //in addition its pred is set to be INVALID, and dist to 0.
    114     //if s was marked previuosly, then it is simply pushed.
     117    /// s is marked to be reached and pushed in the bfs queue.
     118    /// If the queue is empty, then the first out-edge is processed.
     119    /// If s was not marked previously, then
     120    /// in addition its pred is set to be INVALID, and dist to 0.
     121    /// if s was marked previuosly, then it is simply pushed.
    115122    void push(Node s) {
    116123      if (this->reached[s]) {
     
    122129      }
    123130    }
     131    /// A bfs is processed from s.
    124132    void run(Node s) {
    125133      push(s);
     
    201209  };
    202210
     211  /// Dfs searches from s for the nodes wich are not marked in
     212  /// \c reached_map
     213  /// Reached is a read-write bool-map, Pred is a write-nodemap, have to be.
     214  template <typename Graph,
     215            typename ReachedMap=typename Graph::template NodeMap<bool>,
     216            typename PredMap
     217            =typename Graph::template NodeMap<typename Graph::Edge> >
     218  class Dfs : public DfsIterator<Graph, ReachedMap> {
     219    typedef DfsIterator<Graph, ReachedMap> Parent;
     220  protected:
     221    typedef typename Parent::Node Node;
     222    PredMap& pred;
     223  public:
     224    Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred) { }
     225    /// s is marked to be reached and pushed in the bfs queue.
     226    /// If the queue is empty, then the first out-edge is processed.
     227    /// If s was not marked previously, then
     228    /// in addition its pred is set to be INVALID.
     229    /// if s was marked previuosly, then it is simply pushed.
     230    void push(Node s) {
     231      if (this->reached[s]) {
     232        Parent::pushAndSetReached(s);
     233      } else {
     234        Parent::pushAndSetReached(s);
     235        pred.set(s, INVALID);
     236      }
     237    }
     238    /// A bfs is processed from s.
     239    void run(Node s) {
     240      push(s);
     241      while (!this->finished()) this->operator++();
     242    }
     243    Dfs<Graph, ReachedMap, PredMap> operator++() {
     244      Parent::operator++();
     245      if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
     246      {
     247        pred.set(this->bNode(), this->actual_edge);
     248      }
     249      return *this;
     250    }
     251    const PredMap& getPredMap() const { return pred; }
     252  };
     253
     254
    203255} // namespace hugo
    204256
Note: See TracChangeset for help on using the changeset viewer.