Nicer and more documented graph_wrapper.h file.
These are only the first steps for making this file more beautiful.
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.
37 typedef typename Graph::Node Node;
38 typedef typename Graph::NodeIt NodeIt;
39 typedef typename Graph::Edge Edge;
40 typedef typename Graph::OutEdgeIt OutEdgeIt;
42 ///\brief The type of the map that stores the last
43 ///edges of the shortest paths.
44 typedef typename Graph::template NodeMap<Edge> PredMap;
45 ///\brief The type of the map that stores the last but one
46 ///nodes of the shortest paths.
47 typedef typename Graph::template NodeMap<Node> PredNodeMap;
48 ///The type of the map that stores the dists of the nodes.
49 typedef typename Graph::template NodeMap<int> DistMap;
54 bool local_predecessor;
55 PredNodeMap *pred_node;
60 //The source node of the last execution.
64 ///Initializes the maps.
68 local_predecessor = true;
69 predecessor = new PredMap(*G);
72 local_pred_node = true;
73 pred_node = new PredNodeMap(*G);
76 local_distance = true;
77 distance = new DistMap(*G);
82 Bfs(const Graph& _G) :
84 predecessor(NULL), local_predecessor(false),
85 pred_node(NULL), local_pred_node(false),
86 distance(NULL), local_distance(false)
91 if(local_predecessor) delete predecessor;
92 if(local_pred_node) delete pred_node;
93 if(local_distance) delete distance;
96 ///Sets the graph the algorithm will run on.
98 ///Sets the graph the algorithm will run on.
99 ///\return <tt> (*this) </tt>
100 ///\bug What about maps?
101 ///\todo It may be unnecessary
102 Bfs &setGraph(const Graph &_G)
107 ///Sets the map storing the predecessor edges.
109 ///Sets the map storing the predecessor edges.
110 ///If you don't use this function before calling \ref run(),
111 ///it will allocate one. The destuctor deallocates this
112 ///automatically allocated map, of course.
113 ///\return <tt> (*this) </tt>
114 Bfs &setPredMap(PredMap &m)
116 if(local_predecessor) {
118 local_predecessor=false;
124 ///Sets the map storing the predecessor nodes.
126 ///Sets the map storing the predecessor nodes.
127 ///If you don't use this function before calling \ref run(),
128 ///it will allocate one. The destuctor deallocates this
129 ///automatically allocated map, of course.
130 ///\return <tt> (*this) </tt>
131 Bfs &setPredNodeMap(PredNodeMap &m)
133 if(local_pred_node) {
135 local_pred_node=false;
141 ///Sets the map storing the distances calculated by the algorithm.
143 ///Sets the map storing the distances calculated by the algorithm.
144 ///If you don't use this function before calling \ref run(),
145 ///it will allocate one. The destuctor deallocates this
146 ///automatically allocated map, of course.
147 ///\return <tt> (*this) </tt>
148 Bfs &setDistMap(DistMap &m)
152 local_distance=false;
158 ///Runs %BFS algorithm from node \c s.
160 ///This method runs the %BFS algorithm from a root node \c s
163 ///shortest path to each node. The algorithm computes
165 ///- The distance of each node from the root.
173 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
174 predecessor->set(u,INVALID);
175 pred_node->set(u,INVALID);
179 std::vector<typename Graph::Node> Q(N);
188 int d= (*distance)[n]+1;
190 for(OutEdgeIt e(*G,n);e!=INVALID;++e)
191 if((m=G->head(e))!=s && (*predecessor)[m]==INVALID) {
193 predecessor->set(m,e);
200 ///The distance of a node from the root.
202 ///Returns the distance of a node from the root.
203 ///\pre \ref run() must be called before using this function.
204 ///\warning If node \c v in unreachable from the root the return value
205 ///of this funcion is undefined.
206 int dist(Node v) const { return (*distance)[v]; }
208 ///Returns the 'previous edge' of the %BFS path tree.
210 ///For a node \c v it returns the 'previous edge' of the %BFS tree,
211 ///i.e. it returns the last edge of a shortest path from the root to \c
212 ///v. It is \ref INVALID
213 ///if \c v is unreachable from the root or if \c v=s. The
214 ///%BFS tree used here is equal to the %BFS tree used in
215 ///\ref predNode(Node v). \pre \ref run() must be called before using
217 Edge pred(Node v) const { return (*predecessor)[v]; }
219 ///Returns the 'previous node' of the %BFS tree.
221 ///For a node \c v it returns the 'previous node' on the %BFS tree,
222 ///i.e. it returns the last but one node from a shortest path from the
223 ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
224 ///\c v=s. The shortest path tree used here is equal to the %BFS
225 ///tree used in \ref pred(Node v). \pre \ref run() must be called before
226 ///using this function.
227 Node predNode(Node v) const { return (*pred_node)[v]; }
229 ///Returns a reference to the NodeMap of distances.
231 ///Returns a reference to the NodeMap of distances. \pre \ref run() must
232 ///be called before using this function.
233 const DistMap &distMap() const { return *distance;}
235 ///Returns a reference to the %BFS tree map.
237 ///Returns a reference to the NodeMap of the edges of the
239 ///\pre \ref run() must be called before using this function.
240 const PredMap &predMap() const { return *predecessor;}
242 ///Returns a reference to the map of last but one nodes of shortest paths.
244 ///Returns a reference to the NodeMap of the last but one nodes on the
246 ///\pre \ref run() must be called before using this function.
247 const PredNodeMap &predNodeMap() const { return *pred_node;}
249 ///Checks if a node is reachable from the root.
251 ///Returns \c true if \c v is reachable from the root.
252 ///\warning The root node is reported to be reached!
254 ///\pre \ref run() must be called before using this function.
256 bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
262 } //END OF NAMESPACE HUGO