lemon-0.x: src/work/marci/bfs

     1 // -*- c++ -*-

     2 #ifndef HUGO_BFS_DFS_H

     3 #define HUGO_BFS_DFS_H

     5 /// \ingroup galgs

     6 /// \file

     7 /// \brief Bfs and dfs iterators.

     8 ///

     9 /// This file contains bfs and dfs iterator classes.

    10 ///

    11 // /// \author Marton Makai

    13 #include <queue>

    14 #include <stack>

    15 #include <utility>

    17 #include <hugo/invalid.h>

    19 namespace hugo {

    21   /// Bfs searches for the nodes wich are not marked in

    22   /// \c reached_map

    23   /// Reached have to be a read-write bool node-map.

    24   /// \ingroup galgs

    25   template <typename Graph, /*typename OutEdgeIt,*/

    26 	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >

    27   class BfsIterator {

    28   protected:

    29     typedef typename Graph::Node Node;

    30     typedef typename Graph::OutEdgeIt OutEdgeIt;

    31     const Graph* graph;

    32     std::queue<Node> bfs_queue;

    33     ReachedMap& reached;

    34     bool b_node_newly_reached;

    35     OutEdgeIt actual_edge;

    36     bool own_reached_map;

    37   public:

    38     /// In that constructor \c _reached have to be a reference

    39     /// for a bool bode-map. The algorithm will search for the

    40     /// initially \c false nodes

    41     /// in a bfs order.

    42     BfsIterator(const Graph& _graph, ReachedMap& _reached) :

    43       graph(&_graph), reached(_reached),

    44       own_reached_map(false) { }

    45     /// The same as above, but the map storing the reached nodes

    46     /// is constructed dynamically to everywhere false.

    47     /// \deprecated

    48     BfsIterator(const Graph& _graph) :

    49       graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),

    50       own_reached_map(true) { }

    51     /// The map storing the reached nodes have to be destroyed if

    52     /// it was constructed dynamically

    53     ~BfsIterator() { if (own_reached_map) delete &reached; }

    54     /// This method markes \c s reached.

    55     /// If the queue is empty, then \c s is pushed in the bfs queue

    56     /// and the first out-edge is processed.

    57     /// If the queue is not empty, then \c s is simply pushed.

    58     void pushAndSetReached(Node s) {

    59       reached.set(s, true);

    60       if (bfs_queue.empty()) {

    61 	bfs_queue.push(s);

    62 	graph->first(actual_edge, s);

    63 	if (graph->valid(actual_edge)) {

    64 	  Node w=graph->bNode(actual_edge);

    65 	  if (!reached[w]) {

    66 	    bfs_queue.push(w);

    67 	    reached.set(w, true);

    68 	    b_node_newly_reached=true;

    69 	  } else {

    70 	    b_node_newly_reached=false;

    71 	  }

    72 	}

    73       } else {

    74 	bfs_queue.push(s);

    75       }

    76     }

    77     /// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator,

    78     /// its \c operator++() iterates on the edges in a bfs order.

    79     BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&

    80     operator++() {

    81       if (graph->valid(actual_edge)) {

    82 	graph->next(actual_edge);

    83 	if (graph->valid(actual_edge)) {

    84 	  Node w=graph->bNode(actual_edge);

    85 	  if (!reached[w]) {

    86 	    bfs_queue.push(w);

    87 	    reached.set(w, true);

    88 	    b_node_newly_reached=true;

    89 	  } else {

    90 	    b_node_newly_reached=false;

    91 	  }

    92 	}

    93       } else {

    94 	bfs_queue.pop();

    95 	if (!bfs_queue.empty()) {

    96 	  graph->first(actual_edge, bfs_queue.front());

    97 	  if (graph->valid(actual_edge)) {

    98 	    Node w=graph->bNode(actual_edge);

    99 	    if (!reached[w]) {

   100 	      bfs_queue.push(w);

   101 	      reached.set(w, true);

   102 	      b_node_newly_reached=true;

   103 	    } else {

   104 	      b_node_newly_reached=false;

   105 	    }

   106 	  }

   107 	}

   108       }

   109       return *this;

   110     }

   111     /// Returns true iff the algorithm is finished.

   112     bool finished() const { return bfs_queue.empty(); }

   113     /// The conversion operator makes for converting the bfs-iterator

   114     /// to an \c out-edge-iterator.

   115     ///\bug Edge have to be in HUGO 0.2

   116     operator OutEdgeIt() const { return actual_edge; }

   117     /// Returns if b-node has been reached just now.

   118     bool isBNodeNewlyReached() const { return b_node_newly_reached; }

   119     /// Returns if a-node is examined.

   120     bool isANodeExamined() const { return !(graph->valid(actual_edge)); }

   121     /// Returns a-node of the actual edge, so does if the edge is invalid.

   122     Node aNode() const { return bfs_queue.front(); }

   123     /// \pre The actual edge have to be valid.

   124     Node bNode() const { return graph->bNode(actual_edge); }

   125     /// Guess what?

   126     /// \deprecated

   127     const ReachedMap& getReachedMap() const { return reached; }

   128     /// Guess what?

   129     /// \deprecated

   130     const std::queue<Node>& getBfsQueue() const { return bfs_queue; }

   131   };

   133   /// Bfs searches for the nodes wich are not marked in

   134   /// \c reached_map

   135   /// Reached have to work as a read-write bool Node-map,

   136   /// Pred is a write edge node-map and

   137   /// Dist is a read-write node-map of integral value, have to be.

   138   /// \ingroup galgs

   139   template <typename Graph,

   140 	    typename ReachedMap=typename Graph::template NodeMap<bool>,

   141 	    typename PredMap

   142 	    =typename Graph::template NodeMap<typename Graph::Edge>,

   143 	    typename DistMap=typename Graph::template NodeMap<int> >

   144   class Bfs : public BfsIterator<Graph, ReachedMap> {

   145     typedef BfsIterator<Graph, ReachedMap> Parent;

   146   protected:

   147     typedef typename Parent::Node Node;

   148     PredMap& pred;

   149     DistMap& dist;

   150   public:

   151     /// The algorithm will search in a bfs order for

   152     /// the nodes which are \c false initially.

   153     /// The constructor makes no initial changes on the maps.

   154     Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) :

   155       BfsIterator<Graph, ReachedMap>(_graph, _reached),

   156       pred(_pred), dist(_dist) { }

   157     /// \c s is marked to be reached and pushed in the bfs queue.

   158     /// If the queue is empty, then the first out-edge is processed.

   159     /// If \c s was not marked previously, then

   160     /// in addition its pred is set to be \c INVALID, and dist to \c 0.

   161     /// if \c s was marked previuosly, then it is simply pushed.

   162     void push(Node s) {

   163       if (this->reached[s]) {

   164 	Parent::pushAndSetReached(s);

   165       } else {

   166 	Parent::pushAndSetReached(s);

   167 	pred.set(s, INVALID);

   168 	dist.set(s, 0);

   169       }

   170     }

   171     /// A bfs is processed from \c s.

   172     void run(Node s) {

   173       push(s);

   174       while (!this->finished()) this->operator++();

   175     }

   176     /// Beside the bfs iteration, \c pred and \dist are saved in a

   177     /// newly reached node.

   178     Bfs<Graph, ReachedMap, PredMap, DistMap>& operator++() {

   179       Parent::operator++();

   180       if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)

   181       {

   182 	pred.set(this->bNode(), this->actual_edge);

   183 	dist.set(this->bNode(), dist[this->aNode()]);

   184       }

   185       return *this;

   186     }

   187     /// Guess what?

   188     /// \deprecated

   189     const PredMap& getPredMap() const { return pred; }

   190     /// Guess what?

   191     /// \deprecated

   192     const DistMap& getDistMap() const { return dist; }

   193   };

   195   /// Dfs searches for the nodes wich are not marked in

   196   /// \c reached_map

   197   /// Reached have to be a read-write bool Node-map.

   198   /// \ingroup galgs

   199   template <typename Graph, /*typename OutEdgeIt,*/

   200 	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >

   201   class DfsIterator {

   202   protected:

   203     typedef typename Graph::Node Node;

   204     typedef typename Graph::OutEdgeIt OutEdgeIt;

   205     const Graph* graph;

   206     std::stack<OutEdgeIt> dfs_stack;

   207     bool b_node_newly_reached;

   208     OutEdgeIt actual_edge;

   209     Node actual_node;

   210     ReachedMap& reached;

   211     bool own_reached_map;

   212   public:

   213     /// In that constructor \c _reached have to be a reference

   214     /// for a bool node-map. The algorithm will search in a dfs order for

   215     /// the nodes which are \c false initially

   216     DfsIterator(const Graph& _graph, ReachedMap& _reached) :

   217       graph(&_graph), reached(_reached),

   218       own_reached_map(false) { }

   219     /// The same as above, but the map of reached nodes is

   220     /// constructed dynamically

   221     /// to everywhere false.

   222     DfsIterator(const Graph& _graph) :

   223       graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),

   224       own_reached_map(true) { }

   225     ~DfsIterator() { if (own_reached_map) delete &reached; }

   226     /// This method markes s reached and first out-edge is processed.

   227     void pushAndSetReached(Node s) {

   228       actual_node=s;

   229       reached.set(s, true);

   230       OutEdgeIt e;

   231       graph->first(e, s);

   232       dfs_stack.push(e);

   233     }

   234     /// As \c DfsIterator<Graph, ReachedMap> works as an edge-iterator,

   235     /// its \c operator++() iterates on the edges in a dfs order.

   236     DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&

   237     operator++() {

   238       actual_edge=dfs_stack.top();

   239       //actual_node=G.aNode(actual_edge);

   240       if (graph->valid(actual_edge)/*.valid()*/) {

   241 	Node w=graph->bNode(actual_edge);

   242 	actual_node=w;

   243 	if (!reached[w]) {

   244 	  OutEdgeIt e;

   245 	  graph->first(e, w);

   246 	  dfs_stack.push(e);

   247 	  reached.set(w, true);

   248 	  b_node_newly_reached=true;

   249 	} else {

   250 	  actual_node=graph->aNode(actual_edge);

   251 	  graph->next(dfs_stack.top());

   252 	  b_node_newly_reached=false;

   253 	}

   254       } else {

   255 	//actual_node=G.aNode(dfs_stack.top());

   256 	dfs_stack.pop();

   257       }

   258       return *this;

   259     }

   260     /// Returns true iff the algorithm is finished.

   261     bool finished() const { return dfs_stack.empty(); }

   262     /// The conversion operator makes for converting the bfs-iterator

   263     /// to an \c out-edge-iterator.

   264     ///\bug Edge have to be in HUGO 0.2

   265     operator OutEdgeIt() const { return actual_edge; }

   266     /// Returns if b-node has been reached just now.

   267     bool isBNodeNewlyReached() const { return b_node_newly_reached; }

   268     /// Returns if a-node is examined.

   269     bool isANodeExamined() const { return !(graph->valid(actual_edge)); }

   270     /// Returns a-node of the actual edge, so does if the edge is invalid.

   271     Node aNode() const { return actual_node; /*FIXME*/}

   272     /// Returns b-node of the actual edge.

   273     /// \pre The actual edge have to be valid.

   274     Node bNode() const { return graph->bNode(actual_edge); }

   275     /// Guess what?

   276     /// \deprecated

   277     const ReachedMap& getReachedMap() const { return reached; }

   278     /// Guess what?

   279     /// \deprecated

   280     const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }

   281   };

   283   /// Dfs searches for the nodes wich are not marked in

   284   /// \c reached_map

   285   /// Reached is a read-write bool node-map,

   286   /// Pred is a write node-map, have to be.

   287   /// \ingroup galgs

   288   template <typename Graph,

   289 	    typename ReachedMap=typename Graph::template NodeMap<bool>,

   290 	    typename PredMap

   291 	    =typename Graph::template NodeMap<typename Graph::Edge> >

   292   class Dfs : public DfsIterator<Graph, ReachedMap> {

   293     typedef DfsIterator<Graph, ReachedMap> Parent;

   294   protected:

   295     typedef typename Parent::Node Node;

   296     PredMap& pred;

   297   public:

   298     /// The algorithm will search in a dfs order for

   299     /// the nodes which are \c false initially.

   300     /// The constructor makes no initial changes on the maps.

   301     Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(_pred) { }

   302     /// \c s is marked to be reached and pushed in the bfs queue.

   303     /// If the queue is empty, then the first out-edge is processed.

   304     /// If \c s was not marked previously, then

   305     /// in addition its pred is set to be \c INVALID.

   306     /// if \c s was marked previuosly, then it is simply pushed.

   307     void push(Node s) {

   308       if (this->reached[s]) {

   309 	Parent::pushAndSetReached(s);

   310       } else {

   311 	Parent::pushAndSetReached(s);

   312 	pred.set(s, INVALID);

   313       }

   314     }

   315     /// A bfs is processed from \c s.

   316     void run(Node s) {

   317       push(s);

   318       while (!this->finished()) this->operator++();

   319     }

   320     /// Beside the dfs iteration, \c pred is saved in a

   321     /// newly reached node.

   322     Dfs<Graph, ReachedMap, PredMap>& operator++() {

   323       Parent::operator++();

   324       if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)

   325       {

   326 	pred.set(this->bNode(), this->actual_edge);

   327       }

   328       return *this;

   329     }

   330     /// Guess what?

   331     /// \deprecated

   332     const PredMap& getPredMap() const { return pred; }

   333   };

   336 } // namespace hugo

   338 #endif //HUGO_BFS_DFS_H

author	marci
	Tue, 17 Aug 2004 13:20:46 +0000
changeset 764	615aca7091d2
parent 650	588ff2ca55bd
child 774	4297098d9677
permissions	-rw-r--r--