32 #endif |
32 #endif |
33 class Bfs{ |
33 class Bfs{ |
34 public: |
34 public: |
35 ///The type of the underlying graph. |
35 ///The type of the underlying graph. |
36 typedef GR Graph; |
36 typedef GR Graph; |
|
37 ///. |
37 typedef typename Graph::Node Node; |
38 typedef typename Graph::Node Node; |
|
39 ///. |
38 typedef typename Graph::NodeIt NodeIt; |
40 typedef typename Graph::NodeIt NodeIt; |
|
41 ///. |
39 typedef typename Graph::Edge Edge; |
42 typedef typename Graph::Edge Edge; |
|
43 ///. |
40 typedef typename Graph::OutEdgeIt OutEdgeIt; |
44 typedef typename Graph::OutEdgeIt OutEdgeIt; |
41 |
45 |
42 ///\brief The type of the map that stores the last |
46 ///\brief The type of the map that stores the last |
43 ///edges of the shortest paths. |
47 ///edges of the shortest paths. |
44 typedef typename Graph::template NodeMap<Edge> PredMap; |
48 typedef typename Graph::template NodeMap<Edge> PredMap; |
47 typedef typename Graph::template NodeMap<Node> PredNodeMap; |
51 typedef typename Graph::template NodeMap<Node> PredNodeMap; |
48 ///The type of the map that stores the dists of the nodes. |
52 ///The type of the map that stores the dists of the nodes. |
49 typedef typename Graph::template NodeMap<int> DistMap; |
53 typedef typename Graph::template NodeMap<int> DistMap; |
50 |
54 |
51 private: |
55 private: |
|
56 /// Pointer to the underlying graph. |
52 const Graph *G; |
57 const Graph *G; |
|
58 ///Pointer to the map of predecessors edges. |
53 PredMap *predecessor; |
59 PredMap *predecessor; |
|
60 ///Indicates if \ref predecessor is locally allocated (\c true) or not. |
54 bool local_predecessor; |
61 bool local_predecessor; |
|
62 ///Pointer to the map of predecessors nodes. |
55 PredNodeMap *pred_node; |
63 PredNodeMap *pred_node; |
|
64 ///Indicates if \ref pred_node is locally allocated (\c true) or not. |
56 bool local_pred_node; |
65 bool local_pred_node; |
|
66 ///Pointer to the map of distances. |
57 DistMap *distance; |
67 DistMap *distance; |
|
68 ///Indicates if \ref distance is locally allocated (\c true) or not. |
58 bool local_distance; |
69 bool local_distance; |
59 |
70 |
60 //The source node of the last execution. |
71 ///The source node of the last execution. |
61 Node source; |
72 Node source; |
62 |
73 |
63 |
74 |
64 ///Initializes the maps. |
75 ///Initializes the maps. |
65 void init_maps() |
76 void init_maps() |
77 distance = new DistMap(*G); |
88 distance = new DistMap(*G); |
78 } |
89 } |
79 } |
90 } |
80 |
91 |
81 public : |
92 public : |
|
93 ///Constructor. |
|
94 |
|
95 ///\param _G the graph the algorithm will run on. |
82 Bfs(const Graph& _G) : |
96 Bfs(const Graph& _G) : |
83 G(&_G), |
97 G(&_G), |
84 predecessor(NULL), local_predecessor(false), |
98 predecessor(NULL), local_predecessor(false), |
85 pred_node(NULL), local_pred_node(false), |
99 pred_node(NULL), local_pred_node(false), |
86 distance(NULL), local_distance(false) |
100 distance(NULL), local_distance(false) |
87 { } |
101 { } |
88 |
102 |
|
103 ///Destructor. |
89 ~Bfs() |
104 ~Bfs() |
90 { |
105 { |
91 if(local_predecessor) delete predecessor; |
106 if(local_predecessor) delete predecessor; |
92 if(local_pred_node) delete pred_node; |
107 if(local_pred_node) delete pred_node; |
93 if(local_distance) delete distance; |
108 if(local_distance) delete distance; |
94 } |
109 } |
95 |
110 |
96 ///Sets the graph the algorithm will run on. |
|
97 |
|
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) |
|
103 { |
|
104 G = &_G; |
|
105 return *this; |
|
106 } |
|
107 ///Sets the map storing the predecessor edges. |
111 ///Sets the map storing the predecessor edges. |
108 |
112 |
109 ///Sets the map storing the predecessor edges. |
113 ///Sets the map storing the predecessor edges. |
110 ///If you don't use this function before calling \ref run(), |
114 ///If you don't use this function before calling \ref run(), |
111 ///it will allocate one. The destuctor deallocates this |
115 ///it will allocate one. The destuctor deallocates this |
247 const PredNodeMap &predNodeMap() const { return *pred_node;} |
251 const PredNodeMap &predNodeMap() const { return *pred_node;} |
248 |
252 |
249 ///Checks if a node is reachable from the root. |
253 ///Checks if a node is reachable from the root. |
250 |
254 |
251 ///Returns \c true if \c v is reachable from the root. |
255 ///Returns \c true if \c v is reachable from the root. |
252 ///\warning The root node is reported to be reached! |
256 ///\note The root node is reported to be reached! |
253 /// |
257 /// |
254 ///\pre \ref run() must be called before using this function. |
258 ///\pre \ref run() must be called before using this function. |
255 /// |
259 /// |
256 bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; } |
260 bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; } |
257 |
261 |