The default constructors are removed from the maps.
The ArrayMap is the map structure of the graphs.
7 ///\brief Bfs algorithm.
9 ///\todo Revise Manual.
11 #include <hugo/bin_heap.h>
12 #include <hugo/invalid.h>
16 /// \addtogroup flowalgs
19 ///%BFS algorithm class.
21 ///This class provides an efficient implementation of %BFS algorithm.
22 ///\param GR The graph type the algorithm runs on.
23 ///This class does the same as Dijkstra does with constant 1 edge length,
26 ///\author Alpar Juttner
29 template <typename GR>
31 template <typename GR>
35 ///The type of the underlying graph.
38 typedef typename Graph::Node Node;
40 typedef typename Graph::NodeIt NodeIt;
42 typedef typename Graph::Edge Edge;
44 typedef typename Graph::OutEdgeIt OutEdgeIt;
46 ///\brief The type of the map that stores the last
47 ///edges of the shortest paths.
48 typedef typename Graph::template NodeMap<Edge> PredMap;
49 ///\brief The type of the map that stores the last but one
50 ///nodes of the shortest paths.
51 typedef typename Graph::template NodeMap<Node> PredNodeMap;
52 ///The type of the map that stores the dists of the nodes.
53 typedef typename Graph::template NodeMap<int> DistMap;
56 /// Pointer to the underlying graph.
58 ///Pointer to the map of predecessors edges.
60 ///Indicates if \ref predecessor is locally allocated (\c true) or not.
61 bool local_predecessor;
62 ///Pointer to the map of predecessors nodes.
63 PredNodeMap *pred_node;
64 ///Indicates if \ref pred_node is locally allocated (\c true) or not.
66 ///Pointer to the map of distances.
68 ///Indicates if \ref distance is locally allocated (\c true) or not.
71 ///The source node of the last execution.
75 ///Initializes the maps.
79 local_predecessor = true;
80 predecessor = new PredMap(*G);
83 local_pred_node = true;
84 pred_node = new PredNodeMap(*G);
87 local_distance = true;
88 distance = new DistMap(*G);
95 ///\param _G the graph the algorithm will run on.
96 Bfs(const Graph& _G) :
98 predecessor(NULL), local_predecessor(false),
99 pred_node(NULL), local_pred_node(false),
100 distance(NULL), local_distance(false)
106 if(local_predecessor) delete predecessor;
107 if(local_pred_node) delete pred_node;
108 if(local_distance) delete distance;
111 ///Sets the map storing the predecessor edges.
113 ///Sets the map storing the predecessor edges.
114 ///If you don't use this function before calling \ref run(),
115 ///it will allocate one. The destuctor deallocates this
116 ///automatically allocated map, of course.
117 ///\return <tt> (*this) </tt>
118 Bfs &setPredMap(PredMap &m)
120 if(local_predecessor) {
122 local_predecessor=false;
128 ///Sets the map storing the predecessor nodes.
130 ///Sets the map storing the predecessor nodes.
131 ///If you don't use this function before calling \ref run(),
132 ///it will allocate one. The destuctor deallocates this
133 ///automatically allocated map, of course.
134 ///\return <tt> (*this) </tt>
135 Bfs &setPredNodeMap(PredNodeMap &m)
137 if(local_pred_node) {
139 local_pred_node=false;
145 ///Sets the map storing the distances calculated by the algorithm.
147 ///Sets the map storing the distances calculated by the algorithm.
148 ///If you don't use this function before calling \ref run(),
149 ///it will allocate one. The destuctor deallocates this
150 ///automatically allocated map, of course.
151 ///\return <tt> (*this) </tt>
152 Bfs &setDistMap(DistMap &m)
156 local_distance=false;
162 ///Runs %BFS algorithm from node \c s.
164 ///This method runs the %BFS algorithm from a root node \c s
167 ///shortest path to each node. The algorithm computes
169 ///- The distance of each node from the root.
177 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
178 predecessor->set(u,INVALID);
179 pred_node->set(u,INVALID);
183 std::vector<typename Graph::Node> Q(N);
192 int d= (*distance)[n]+1;
194 for(OutEdgeIt e(*G,n);e!=INVALID;++e)
195 if((m=G->head(e))!=s && (*predecessor)[m]==INVALID) {
197 predecessor->set(m,e);
204 ///The distance of a node from the root.
206 ///Returns the distance of a node from the root.
207 ///\pre \ref run() must be called before using this function.
208 ///\warning If node \c v in unreachable from the root the return value
209 ///of this funcion is undefined.
210 int dist(Node v) const { return (*distance)[v]; }
212 ///Returns the 'previous edge' of the %BFS path tree.
214 ///For a node \c v it returns the 'previous edge' of the %BFS tree,
215 ///i.e. it returns the last edge of a shortest path from the root to \c
216 ///v. It is \ref INVALID
217 ///if \c v is unreachable from the root or if \c v=s. The
218 ///%BFS tree used here is equal to the %BFS tree used in
219 ///\ref predNode(Node v). \pre \ref run() must be called before using
221 Edge pred(Node v) const { return (*predecessor)[v]; }
223 ///Returns the 'previous node' of the %BFS tree.
225 ///For a node \c v it returns the 'previous node' on the %BFS tree,
226 ///i.e. it returns the last but one node from a shortest path from the
227 ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
228 ///\c v=s. The shortest path tree used here is equal to the %BFS
229 ///tree used in \ref pred(Node v). \pre \ref run() must be called before
230 ///using this function.
231 Node predNode(Node v) const { return (*pred_node)[v]; }
233 ///Returns a reference to the NodeMap of distances.
235 ///Returns a reference to the NodeMap of distances. \pre \ref run() must
236 ///be called before using this function.
237 const DistMap &distMap() const { return *distance;}
239 ///Returns a reference to the %BFS tree map.
241 ///Returns a reference to the NodeMap of the edges of the
243 ///\pre \ref run() must be called before using this function.
244 const PredMap &predMap() const { return *predecessor;}
246 ///Returns a reference to the map of last but one nodes of shortest paths.
248 ///Returns a reference to the NodeMap of the last but one nodes on the
250 ///\pre \ref run() must be called before using this function.
251 const PredNodeMap &predNodeMap() const { return *pred_node;}
253 ///Checks if a node is reachable from the root.
255 ///Returns \c true if \c v is reachable from the root.
256 ///\note The root node is reported to be reached!
258 ///\pre \ref run() must be called before using this function.
260 bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
266 } //END OF NAMESPACE HUGO