COIN-OR::LEMON - Graph Library

Changeset 597:a6e2b02f496a in lemon-0.x


Ignore:
Timestamp:
05/10/04 18:31:48 (16 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@777
Message:

bfs, dfs docs

File:
1 edited

Legend:

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

    r560 r597  
    1111namespace hugo {
    1212
     13  /// Bfs searches for the nodes wich are not marked in
     14  /// \c reached_map
     15  /// Reached have to work as read-write bool Node-map.
    1316  template <typename Graph, /*typename OutEdgeIt,*/
    1417            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
     
    2427    bool own_reached_map;
    2528  public:
     29    /// In that constructor \c _reached have to be a reference
     30    /// for a bool Node-map. The algorithm will search in a bfs order for
     31    /// the nodes which are \c false initially
    2632    BfsIterator(const Graph& _graph, ReachedMap& _reached) :
    2733      graph(&_graph), reached(_reached),
    2834      own_reached_map(false) { }
     35    /// The same as above, but the map storing the reached nodes
     36    /// is constructed dynamically to everywhere false.
    2937    BfsIterator(const Graph& _graph) :
    3038      graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
    3139      own_reached_map(true) { }
     40    /// The storing the reached nodes have to be destroyed if
     41    /// it was constructed dynamically
    3242    ~BfsIterator() { if (own_reached_map) delete &reached; }
    33     /// This method markes s reached.
    34     /// If the queue is empty, then s is pushed in the bfs queue
    35     /// and the first OutEdgeIt is processed.
    36     /// If the queue is not empty, then s is simply pushed.
     43    /// This method markes \c s reached.
     44    /// If the queue is empty, then \c s is pushed in the bfs queue
     45    /// and the first out-edge is processed.
     46    /// If the queue is not empty, then \c s is simply pushed.
    3747    void pushAndSetReached(Node s) {
    3848      reached.set(s, true);
     
    8898      return *this;
    8999    }
     100    ///
    90101    bool finished() const { return bfs_queue.empty(); }
    91102    /// The conversion operator makes for converting the bfs-iterator
    92103    /// to an \c out-edge-iterator.
     104    ///\bug Edge have to be in HUGO 0.2
    93105    operator OutEdgeIt() const { return actual_edge; }
     106    ///
    94107    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
     108    ///
    95109    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
     110    ///
    96111    Node aNode() const { return bfs_queue.front(); }
     112    ///
    97113    Node bNode() const { return graph->bNode(actual_edge); }
     114    ///
    98115    const ReachedMap& getReachedMap() const { return reached; }
     116    ///
    99117    const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
    100118  }; 
    101119
    102   /// Bfs searches from s for the nodes wich are not marked in
     120  /// Bfs searches for the nodes wich are not marked in
    103121  /// \c reached_map
    104   /// Reached is a read-write bool-map, Pred is a write-nodemap
    105   /// and dist is an rw-nodemap, have to be.
     122  /// Reached have to work as a read-write bool Node-map,
     123  /// Pred is a write Edge Node-map and
     124  /// Dist is a read-write int Node-map, have to be.
     125  ///\todo In fact onsly simple operations requirement are needed for
     126  /// Dist::Value.
    106127  template <typename Graph,
    107128            typename ReachedMap=typename Graph::template NodeMap<bool>,
     
    116137    DistMap& dist;
    117138  public:
     139    /// The algorithm will search in a bfs order for
     140    /// the nodes which are \c false initially.
     141    /// The constructor makes no initial changes on the maps.
    118142    Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred), dist(&_dist) { }
    119     /// s is marked to be reached and pushed in the bfs queue.
     143    /// \c s is marked to be reached and pushed in the bfs queue.
    120144    /// If the queue is empty, then the first out-edge is processed.
    121     /// If s was not marked previously, then
    122     /// in addition its pred is set to be INVALID, and dist to 0.
    123     /// if s was marked previuosly, then it is simply pushed.
     145    /// If \c s was not marked previously, then
     146    /// in addition its pred is set to be \c INVALID, and dist to \c 0.
     147    /// if \c s was marked previuosly, then it is simply pushed.
    124148    void push(Node s) {
    125149      if (this->reached[s]) {
     
    131155      }
    132156    }
    133     /// A bfs is processed from s.
     157    /// A bfs is processed from \c s.
    134158    void run(Node s) {
    135159      push(s);
    136160      while (!this->finished()) this->operator++();
    137161    }
     162    /// Beside the bfs iteration, \c pred and \dist are saved in a
     163    /// newly reached node.
    138164    Bfs<Graph, ReachedMap, PredMap, DistMap> operator++() {
    139165      Parent::operator++();
     
    145171      return *this;
    146172    }
     173    ///
    147174    const PredMap& getPredMap() const { return pred; }
     175    ///
    148176    const DistMap& getDistMap() const { return dist; }
    149177  };
    150178
     179  /// Dfs searches for the nodes wich are not marked in
     180  /// \c reached_map
     181  /// Reached have to be a read-write bool Node-map.
    151182  template <typename Graph, /*typename OutEdgeIt,*/
    152183            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
     
    163194    bool own_reached_map;
    164195  public:
     196    /// In that constructor \c _reached have to be a reference
     197    /// for a bool Node-map. The algorithm will search in a dfs order for
     198    /// the nodes which are \c false initially
    165199    DfsIterator(const Graph& _graph, ReachedMap& _reached) :
    166200      graph(&_graph), reached(_reached),
    167201      own_reached_map(false) { }
     202    /// The same as above, but the map of reached nodes is
     203    /// constructed dynamically
     204    /// to everywhere false.
    168205    DfsIterator(const Graph& _graph) :
    169206      graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
    170207      own_reached_map(true) { }
    171208    ~DfsIterator() { if (own_reached_map) delete &reached; }
     209    /// This method markes s reached and first out-edge is processed.
    172210    void pushAndSetReached(Node s) {
    173211      actual_node=s;
     
    177215      dfs_stack.push(e);
    178216    }
     217    /// As \c DfsIterator<Graph, ReachedMap> works as an edge-iterator,
     218    /// its \c operator++() iterates on the edges in a dfs order.
    179219    DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
    180220    operator++() {
     
    201241      return *this;
    202242    }
     243    ///
    203244    bool finished() const { return dfs_stack.empty(); }
     245    ///
    204246    operator OutEdgeIt() const { return actual_edge; }
     247    ///
    205248    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
     249    ///
    206250    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
     251    ///
    207252    Node aNode() const { return actual_node; /*FIXME*/}
     253    ///
    208254    Node bNode() const { return graph->bNode(actual_edge); }
     255    ///
    209256    const ReachedMap& getReachedMap() const { return reached; }
     257    ///
    210258    const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
    211259  };
    212260
    213   /// Dfs searches from s for the nodes wich are not marked in
     261  /// Dfs searches for the nodes wich are not marked in
    214262  /// \c reached_map
    215   /// Reached is a read-write bool-map, Pred is a write-nodemap, have to be.
     263  /// Reached is a read-write bool Node-map,
     264  /// Pred is a write Node-map, have to be.
    216265  template <typename Graph,
    217266            typename ReachedMap=typename Graph::template NodeMap<bool>,
     
    224273    PredMap& pred;
    225274  public:
     275    /// The algorithm will search in a dfs order for
     276    /// the nodes which are \c false initially.
     277    /// The constructor makes no initial changes on the maps.
    226278    Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred) { }
    227     /// s is marked to be reached and pushed in the bfs queue.
     279    /// \c s is marked to be reached and pushed in the bfs queue.
    228280    /// If the queue is empty, then the first out-edge is processed.
    229     /// If s was not marked previously, then
    230     /// in addition its pred is set to be INVALID.
    231     /// if s was marked previuosly, then it is simply pushed.
     281    /// If \c s was not marked previously, then
     282    /// in addition its pred is set to be \c INVALID.
     283    /// if \c s was marked previuosly, then it is simply pushed.
    232284    void push(Node s) {
    233285      if (this->reached[s]) {
     
    238290      }
    239291    }
    240     /// A bfs is processed from s.
     292    /// A bfs is processed from \c s.
    241293    void run(Node s) {
    242294      push(s);
    243295      while (!this->finished()) this->operator++();
    244296    }
     297    /// Beside the dfs iteration, \c pred is saved in a
     298    /// newly reached node.
    245299    Dfs<Graph, ReachedMap, PredMap> operator++() {
    246300      Parent::operator++();
     
    251305      return *this;
    252306    }
     307    ///
    253308    const PredMap& getPredMap() const { return pred; }
    254309  };
Note: See TracChangeset for help on using the changeset viewer.