diff -r ee5959aa4410 -r c280de819a73 src/work/marci/bfs_mm.h --- a/src/work/marci/bfs_mm.h Sun Apr 17 18:57:22 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,559 +0,0 @@ -// -*- 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 -#include -#include - -#include - -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 */ > - 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 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& 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& 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 works as an edge-iterator, - /// its \c operator++() iterates on the edges in a bfs order. - BfsIterator& - 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& 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 PM - =typename Graph::template NodeMap, - typename PNM - =typename Graph::template NodeMap, - typename DM=typename Graph::template NodeMap > - class Bfs : public BfsIterator { - typedef BfsIterator 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 - (const Graph& _graph) : BfsIterator(_graph) { } - /// PM have to be set before any bfs operation. - Bfs& - setPredMap(PredMap& _pred_map) { - pred_map=&_pred_map; - } - /// PredNodeMap have to be set before any bfs operation. - Bfs& - setPredNodeMap(PredNodeMap& _pred_node_map) { - pred_node_map=&_pred_node_map; - } - /// DistMap have to be set before any bfs operation. - Bfs& - 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 - (const Graph& _graph, ReachedMap& _reached_map, - PredMap& _pred_map, PredNodeMap& _pred_node_map, - DistMap& _dist_map) : BfsIterator(_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& 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& 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& 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 PM -// =typename Graph::template NodeMap, -// typename PredNodeMap -// =typename Graph::template NodeMap, -// typename DistMap=typename Graph::template NodeMap > -// class BfsWizard : public Bfs { -// public: -// typedef Bfs 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& -// makeRreached() { -// own_reached_map=true; -// reached=new ReachedMap(*graph, false); -// } -// BfsWizard& -// deleteReachedMap() { -// own_reached_map=false; -// delete reached; -// } - -// BfsWizard& -// makePM() { -// own_pred_map=true; -// pred_map=new PM(*graph, INVALID); -// } -// BfsWizard& -// deletePM() { -// own_pred_map=false; -// delete pred_map; -// } - -// BfsWizard& -// makePredNodeMap() { -// own_pred_node_map=true; -// pred_node_map=new PredNodeMap(*graph, INVALID); -// } -// BfsWizard& -// deletePredNodeMap() { -// own_pred_node_map=false; -// delete pred_node_map; -// } - -// BfsWizard& -// makeDistMap() { -// own_dist_map=true; -// dist_map=new DistMap(*graph, 0); -// } -// BfsWizard& -// 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 -// (const Graph& _graph) : -// own_reached_map(false), -// own_pred_map(false), -// own_pred_node_map(false), -// own_dist_map(false) { -// } - -// /// \e -// ~BfsWizard() { -// if (own_reached_map) deleteReachedMap(); -// if (own_pred_map) deletePM(); -// if (own_pred_node_map) deletePredNodeMap(); -// if (own_dist_map) deleteDistMap(); -// } - -// /// \e -// BfsWizard& -// setReachedMap(ReachedMap& _reached) { -// if (own_reached_map) deleteReachedMap(); -// Parent::setReachedMap(_reached); -// } -// /// \e -// BfsWizard& -// setPM(PM& _pred) { -// if (own_pred_map) deletePM(); -// Parent::setPM(_pred); -// } -// /// \e -// BfsWizard& -// setPredNodeMap(PredNodeMap& _pred_node) { -// if (own_pred_node_map) deletePredNodeMap(); -// Parent::setPredNodeMap(_pred_node); -// } -// /// \e -// BfsWizard& -// setDistMap(DistMap& _dist) { -// if (own_dist_map) deleteDistMap(); -// Parent::setDistMap(_dist); -// } - -// /// \e -// BfsWizard& -// 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& -// operator++() { -// if (!reached) makeRM(); -// if (!pred_map) makePMMap(); -// if (!pred_node_map) makePredNodeMap(); -// if (!dist_map) makeDistMap(); -// ++(*this); -// return *this; -// } - -// /// \e -// BfsWizard& -// 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 */ > - class DfsIterator { - protected: - typedef typename Graph::Node Node; - typedef typename Graph::Edge Edge; - typedef typename Graph::OutEdgeIt OutEdgeIt; - const Graph* graph; - std::stack 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& 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 works as an edge-iterator, - /// its \c operator++() iterates on the edges in a dfs order. - DfsIterator& - 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& 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 PredMap - =typename Graph::template NodeMap > - class Dfs : public DfsIterator { - typedef DfsIterator 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(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator(_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& 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& 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& 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