Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/work/marci/bfs_dfs.h
changeset 655 a9878222d5c8
parent 646 bd7a69231cf8
child 671 708df4dc6ab6
equal deleted inserted replaced
3:f48b2dcbcbd8 4:47960420c4f9 
    18 
    18 
    19 namespace hugo {
 
    19 namespace hugo {
 
    20 
    20 
    21   /// Bfs searches for the nodes wich are not marked in 
    21   /// Bfs searches for the nodes wich are not marked in 
    22   /// \c reached_map
 
    22   /// \c reached_map
 
    23   /// Reached have to work as read-write bool Node-map.
 
    23   /// Reached have to be a read-write bool node-map.
 
    24   /// \ingroup galgs
 
    24   /// \ingroup galgs
 
    25   template <typename Graph, /*typename OutEdgeIt,*/ 
    25   template <typename Graph, /*typename OutEdgeIt,*/ 
    26 	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
 
    26 	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
 
    27   class BfsIterator {
 
    27   class BfsIterator {
 
    28   protected:
 
    28   protected:
 
    34     bool b_node_newly_reached;
 
    34     bool b_node_newly_reached;
 
    35     OutEdgeIt actual_edge;
 
    35     OutEdgeIt actual_edge;
 
    36     bool own_reached_map;
 
    36     bool own_reached_map;
 
    37   public:
 
    37   public:
 
    38     /// In that constructor \c _reached have to be a reference 
    38     /// In that constructor \c _reached have to be a reference 
    39     /// for a bool Node-map. The algorithm will search in a bfs order for 
    39     /// for a bool bode-map. The algorithm will search for the 
    40     /// the nodes which are \c false initially
 
    40     /// initially \c false nodes 
       
    41     /// in a bfs order.
 
    41     BfsIterator(const Graph& _graph, ReachedMap& _reached) : 
    42     BfsIterator(const Graph& _graph, ReachedMap& _reached) : 
    42       graph(&_graph), reached(_reached), 
    43       graph(&_graph), reached(_reached), 
    43       own_reached_map(false) { }
 
    44       own_reached_map(false) { }
 
    44     /// The same as above, but the map storing the reached nodes 
    45     /// The same as above, but the map storing the reached nodes 
    45     /// is constructed dynamically to everywhere false.
 
    46     /// is constructed dynamically to everywhere false.
 
       
    47     /// \deprecated
 
    46     BfsIterator(const Graph& _graph) : 
    48     BfsIterator(const Graph& _graph) : 
    47       graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), 
    49       graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), 
    48       own_reached_map(true) { }
 
    50       own_reached_map(true) { }
 
    49     /// The map storing the reached nodes have to be destroyed if 
    51     /// The map storing the reached nodes have to be destroyed if 
    50     /// it was constructed dynamically
 
    52     /// it was constructed dynamically
 
   119     /// Returns a-node of the actual edge, so does if the edge is invalid.
 
   121     /// Returns a-node of the actual edge, so does if the edge is invalid.
 
   120     Node aNode() const { return bfs_queue.front(); }
 
   122     Node aNode() const { return bfs_queue.front(); }
 
   121     /// \pre The actual edge have to be valid.
 
   123     /// \pre The actual edge have to be valid.
 
   122     Node bNode() const { return graph->bNode(actual_edge); }
 
   124     Node bNode() const { return graph->bNode(actual_edge); }
 
   123     /// Guess what?
 
   125     /// Guess what?
 
       
   126     /// \deprecated 
   124     const ReachedMap& getReachedMap() const { return reached; }
 
   127     const ReachedMap& getReachedMap() const { return reached; }
 
   125     /// Guess what?
 
   128     /// Guess what?
 
       
   129     /// \deprecated
 
   126     const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
 
   130     const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
 
   127   };
 
   131   };
 
   128 
   132 
   129   /// Bfs searches for the nodes wich are not marked in 
   133   /// Bfs searches for the nodes wich are not marked in 
   130   /// \c reached_map
 
   134   /// \c reached_map
 
   131   /// Reached have to work as a read-write bool Node-map, 
   135   /// Reached have to work as a read-write bool Node-map, 
   132   /// Pred is a write Edge Node-map and
 
   136   /// Pred is a write edge node-map and
 
   133   /// Dist is a read-write Node-map of integral value, have to be. 
   137   /// Dist is a read-write node-map of integral value, have to be. 
   134   /// \ingroup galgs
 
   138   /// \ingroup galgs
 
   135   template <typename Graph, 
   139   template <typename Graph, 
   136 	    typename ReachedMap=typename Graph::template NodeMap<bool>, 
   140 	    typename ReachedMap=typename Graph::template NodeMap<bool>, 
   137 	    typename PredMap
 
   141 	    typename PredMap
 
   138 	    =typename Graph::template NodeMap<typename Graph::Edge>, 
   142 	    =typename Graph::template NodeMap<typename Graph::Edge>, 
   177 	dist.set(this->bNode(), dist[this->aNode()]);
 
   181 	dist.set(this->bNode(), dist[this->aNode()]);
 
   178       }
 
   182       }
 
   179       return *this;
 
   183       return *this;
 
   180     }
 
   184     }
 
   181     /// Guess what?
 
   185     /// Guess what?
 
       
   186     /// \deprecated 
   182     const PredMap& getPredMap() const { return pred; }
 
   187     const PredMap& getPredMap() const { return pred; }
 
   183     /// Guess what?
 
   188     /// Guess what?
 
       
   189     /// \deprecated
 
   184     const DistMap& getDistMap() const { return dist; }
 
   190     const DistMap& getDistMap() const { return dist; }
 
   185   };
 
   191   };
 
   186 
   192 
   187   /// Dfs searches for the nodes wich are not marked in 
   193   /// Dfs searches for the nodes wich are not marked in 
   188   /// \c reached_map
 
   194   /// \c reached_map
 
   201     Node actual_node;
 
   207     Node actual_node;
 
   202     ReachedMap& reached;
 
   208     ReachedMap& reached;
 
   203     bool own_reached_map;
 
   209     bool own_reached_map;
 
   204   public:
 
   210   public:
 
   205     /// In that constructor \c _reached have to be a reference 
   211     /// In that constructor \c _reached have to be a reference 
   206     /// for a bool Node-map. The algorithm will search in a dfs order for 
   212     /// for a bool node-map. The algorithm will search in a dfs order for 
   207     /// the nodes which are \c false initially
 
   213     /// the nodes which are \c false initially
 
   208     DfsIterator(const Graph& _graph, ReachedMap& _reached) : 
   214     DfsIterator(const Graph& _graph, ReachedMap& _reached) : 
   209       graph(&_graph), reached(_reached), 
   215       graph(&_graph), reached(_reached), 
   210       own_reached_map(false) { }
 
   216       own_reached_map(false) { }
 
   211     /// The same as above, but the map of reached nodes is 
   217     /// The same as above, but the map of reached nodes is 
   263     Node aNode() const { return actual_node; /*FIXME*/}
 
   269     Node aNode() const { return actual_node; /*FIXME*/}
 
   264     /// Returns b-node of the actual edge. 
   270     /// Returns b-node of the actual edge. 
   265     /// \pre The actual edge have to be valid.
 
   271     /// \pre The actual edge have to be valid.
 
   266     Node bNode() const { return graph->bNode(actual_edge); }
 
   272     Node bNode() const { return graph->bNode(actual_edge); }
 
   267     /// Guess what?
 
   273     /// Guess what?
 
       
   274     /// \deprecated
 
   268     const ReachedMap& getReachedMap() const { return reached; }
 
   275     const ReachedMap& getReachedMap() const { return reached; }
 
   269     /// Guess what?
 
   276     /// Guess what?
 
       
   277     /// \deprecated
 
   270     const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
 
   278     const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
 
   271   };
 
   279   };
 
   272 
   280 
   273   /// Dfs searches for the nodes wich are not marked in 
   281   /// Dfs searches for the nodes wich are not marked in 
   274   /// \c reached_map
 
   282   /// \c reached_map
 
   275   /// Reached is a read-write bool Node-map, 
   283   /// Reached is a read-write bool node-map, 
   276   /// Pred is a write Node-map, have to be.
 
   284   /// Pred is a write node-map, have to be.
 
   277   /// \ingroup galgs
 
   285   /// \ingroup galgs
 
   278   template <typename Graph, 
   286   template <typename Graph, 
   279 	    typename ReachedMap=typename Graph::template NodeMap<bool>, 
   287 	    typename ReachedMap=typename Graph::template NodeMap<bool>, 
   280 	    typename PredMap
 
   288 	    typename PredMap
 
   281 	    =typename Graph::template NodeMap<typename Graph::Edge> > 
   289 	    =typename Graph::template NodeMap<typename Graph::Edge> > 
   316 	pred.set(this->bNode(), this->actual_edge);
 
   324 	pred.set(this->bNode(), this->actual_edge);
 
   317       }
 
   325       }
 
   318       return *this;
 
   326       return *this;
 
   319     }
 
   327     }
 
   320     /// Guess what?
 
   328     /// Guess what?
 
       
   329     /// \deprecated
 
   321     const PredMap& getPredMap() const { return pred; }
 
   330     const PredMap& getPredMap() const { return pred; }
 
   322   };
 
   331   };
 
   323 
   332 
   324 
   333 
   325 } // namespace hugo
 
   334 } // namespace hugo
lemon-0.x