Changeset 781:d4d182ab75bd in lemon-0.x for src
- Timestamp:
- 09/01/04 17:37:36 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1074
- Location:
- src/hugo
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
src/hugo/bfs.h
r780 r781 17 17 /// @{ 18 18 19 ///%B fsalgorithm class.20 21 ///This class provides an efficient implementation of %B fsalgorithm.22 /// The edge lengths are passed to the algorithm using a23 /// \ref ReadMapSkeleton "readable map",24 /// so it is easy to change it to any kind of length.19 ///%BFS algorithm class. 20 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, 24 ///but it is faster. 25 25 /// 26 ///The type of the length is determined by the \c ValueType of the length map. 27 /// 28 ///It is also possible to change the underlying priority heap. 29 /// 30 ///\param GR The graph type the algorithm runs on. 31 ///\param LM This read-only 32 ///EdgeMap 33 ///determines the 34 ///lengths of the edges. It is read once for each edge, so the map 35 ///may involve in relatively time consuming process to compute the edge 36 ///length if it is necessary. The default map type is 37 ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>" 38 ///\param Heap The heap type used by the %Bfs 39 ///algorithm. The default 40 ///is using \ref BinHeap "binary heap". 41 /// 42 ///\author Jacint Szabo and Alpar Juttner 43 ///\todo We need a typedef-names should be standardized. (-: 44 ///\todo Type of \c PredMap, \c PredNodeMap and \c DistMap 45 ///should not be fixed. (Problematic to solve). 26 ///\author Alpar Juttner 46 27 47 28 #ifdef DOXYGEN … … 81 62 82 63 83 ///Initialize maps. 84 85 ///\todo Error if \c G or are \c NULL. 86 ///\todo Better memory allocation (instead of new). 64 ///Initializes the maps. 87 65 void init_maps() 88 66 { 89 // if(!length) {90 // local_length = true;91 // length = new LM(G);92 // }93 67 if(!predecessor) { 94 68 local_predecessor = true; … … 115 89 ~Bfs() 116 90 { 117 // if(local_length) delete length;118 91 if(local_predecessor) delete predecessor; 119 92 if(local_pred_node) delete pred_node; … … 125 98 ///Sets the graph the algorithm will run on. 126 99 ///\return <tt> (*this) </tt> 100 ///\bug What about maps? 101 ///\todo It may be unnecessary 127 102 Bfs &setGraph(const Graph &_G) 128 103 { … … 130 105 return *this; 131 106 } 132 ///Sets the length map.133 134 107 ///Sets the map storing the predecessor edges. 135 108 … … 187 160 ///This method runs the %BFS algorithm from a root node \c s 188 161 ///in order to 189 ///compute the162 ///compute a 190 163 ///shortest path to each node. The algorithm computes 191 ///- The shortest pathtree.164 ///- The %BFS tree. 192 165 ///- The distance of each node from the root. 193 166 … … 233 206 int dist(Node v) const { return (*distance)[v]; } 234 207 235 ///Returns the 'previous edge' of the shortestpath tree.236 237 ///For a node \c v it returns the 'previous edge' of the shortest pathtree,238 ///i.e. it returns the last edge froma shortest path from the root to \c208 ///Returns the 'previous edge' of the %BFS path tree. 209 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 239 212 ///v. It is \ref INVALID 240 213 ///if \c v is unreachable from the root or if \c v=s. The 241 /// shortest path tree used here is equal to the shortest pathtree used in214 ///%BFS tree used here is equal to the %BFS tree used in 242 215 ///\ref predNode(Node v). \pre \ref run() must be called before using 243 216 ///this function. 244 217 Edge pred(Node v) const { return (*predecessor)[v]; } 245 218 246 ///Returns the 'previous node' of the shortest pathtree.247 248 ///For a node \c v it returns the 'previous node' o f the shortest pathtree,219 ///Returns the 'previous node' of the %BFS tree. 220 221 ///For a node \c v it returns the 'previous node' on the %BFS tree, 249 222 ///i.e. it returns the last but one node from a shortest path from the 250 223 ///root to \c /v. It is INVALID if \c v is unreachable from the root or if 251 ///\c v=s. The shortest path tree used here is equal to the shortest path224 ///\c v=s. The shortest path tree used here is equal to the %BFS 252 225 ///tree used in \ref pred(Node v). \pre \ref run() must be called before 253 226 ///using this function. … … 260 233 const DistMap &distMap() const { return *distance;} 261 234 262 ///Returns a reference to the shortest pathtree map.235 ///Returns a reference to the %BFS tree map. 263 236 264 237 ///Returns a reference to the NodeMap of the edges of the 265 /// shortest pathtree.238 ///%BFS tree. 266 239 ///\pre \ref run() must be called before using this function. 267 240 const PredMap &predMap() const { return *predecessor;} 268 241 269 ///Returns a reference to the map of nodes of shortest paths.270 271 ///Returns a reference to the NodeMap of the last but one nodes o fthe272 /// shortest pathtree.242 ///Returns a reference to the map of last but one nodes of shortest paths. 243 244 ///Returns a reference to the NodeMap of the last but one nodes on the 245 ///%BFS tree. 273 246 ///\pre \ref run() must be called before using this function. 274 247 const PredNodeMap &predNodeMap() const { return *pred_node;} … … 285 258 }; 286 259 287 288 // **********************************************************************289 // IMPLEMENTATIONS290 // **********************************************************************291 292 260 /// @} 293 261 -
src/hugo/dfs.h
r780 r781 5 5 ///\ingroup flowalgs 6 6 ///\file 7 ///\brief Dfsalgorithm.7 ///\brief %DFS algorithm. 8 8 /// 9 9 ///\todo Revise Manual. … … 17 17 /// @{ 18 18 19 ///%Dfs algorithm class. 20 21 ///This class provides an efficient implementation of %Dfs algorithm. 22 ///The edge lengths are passed to the algorithm using a 23 ///\ref ReadMapSkeleton "readable map", 24 ///so it is easy to change it to any kind of length. 25 /// 26 ///The type of the length is determined by the \c ValueType of the length map. 27 /// 28 ///It is also possible to change the underlying priority heap. 19 ///%DFS algorithm class. 20 21 ///This class provides an efficient implementation of %DFS algorithm. 29 22 /// 30 23 ///\param GR The graph type the algorithm runs on. 31 ///\param LM This read-only32 ///EdgeMap33 ///determines the34 ///lengths of the edges. It is read once for each edge, so the map35 ///may involve in relatively time consuming process to compute the edge36 ///length if it is necessary. The default map type is37 ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"38 ///\param Heap The heap type used by the %Dfs39 ///algorithm. The default40 ///is using \ref BinHeap "binary heap".41 24 /// 42 ///\author Jacint Szabo and Alpar Juttner 43 ///\todo We need a typedef-names should be standardized. (-: 44 ///\todo Type of \c PredMap, \c PredNodeMap and \c DistMap 45 ///should not be fixed. (Problematic to solve). 25 ///\author Alpar Juttner 46 26 47 27 #ifdef DOXYGEN … … 60 40 61 41 ///\brief The type of the map that stores the last 62 ///edges of the shortest paths.42 ///edges of the paths on the %DFS tree. 63 43 typedef typename Graph::template NodeMap<Edge> PredMap; 64 44 ///\brief The type of the map that stores the last but one 65 ///nodes of the shortest paths.45 ///nodes of the paths on the %DFS tree. 66 46 typedef typename Graph::template NodeMap<Node> PredNodeMap; 67 ///The type of the map that stores the dists of the nodes .47 ///The type of the map that stores the dists of the nodes on the %DFS tree. 68 48 typedef typename Graph::template NodeMap<int> DistMap; 69 49 … … 81 61 82 62 83 ///Initialize maps. 84 85 ///\todo Error if \c G or are \c NULL. 86 ///\todo Better memory allocation (instead of new). 63 ///Initializes the maps. 87 64 void init_maps() 88 65 { 89 // if(!length) {90 // local_length = true;91 // length = new LM(G);92 // }93 66 if(!predecessor) { 94 67 local_predecessor = true; … … 115 88 ~Dfs() 116 89 { 117 // if(local_length) delete length;118 90 if(local_predecessor) delete predecessor; 119 91 if(local_pred_node) delete pred_node; … … 125 97 ///Sets the graph the algorithm will run on. 126 98 ///\return <tt> (*this) </tt> 99 ///\bug What about maps? 100 ///\todo It may be unnecessary 127 101 Dfs &setGraph(const Graph &_G) 128 102 { … … 130 104 return *this; 131 105 } 132 ///Sets the length map.133 134 106 ///Sets the map storing the predecessor edges. 135 107 … … 187 159 ///This method runs the %DFS algorithm from a root node \c s 188 160 ///in order to 189 ///compute the 190 ///shortest path to each node. The algorithm computes 191 ///- The shortest path tree. 192 ///- The distance of each node from the root. 161 ///compute 162 ///- a %DFS tree and 163 ///- the distance of each node from the root on this tree. 193 164 194 165 void run(Node s) { … … 228 199 } 229 200 230 ///The distance of a node from the root .231 232 ///Returns the distance of a node from the root .201 ///The distance of a node from the root on the %DFS tree. 202 203 ///Returns the distance of a node from the root on the %DFS tree. 233 204 ///\pre \ref run() must be called before using this function. 234 205 ///\warning If node \c v in unreachable from the root the return value … … 236 207 int dist(Node v) const { return (*distance)[v]; } 237 208 238 ///Returns the 'previous edge' of the shortestpath tree.239 240 ///For a node \c v it returns the 'previous edge' of the shortest path tree,241 /// i.e. it returns the last edge from a shortest pathfrom the root to \c209 ///Returns the 'previous edge' of the %DFS path tree. 210 211 ///For a node \c v it returns the last edge of the path on the %DFS tree 212 ///from the root to \c 242 213 ///v. It is \ref INVALID 243 214 ///if \c v is unreachable from the root or if \c v=s. The 244 /// shortest path tree used here is equal to the shortest pathtree used in215 ///%DFS tree used here is equal to the %DFS tree used in 245 216 ///\ref predNode(Node v). \pre \ref run() must be called before using 246 217 ///this function. 247 218 Edge pred(Node v) const { return (*predecessor)[v]; } 248 219 249 ///Returns the 'previous node' of the shortest path tree. 250 251 ///For a node \c v it returns the 'previous node' of the shortest path tree, 252 ///i.e. it returns the last but one node from a shortest path from the 253 ///root to \c /v. It is INVALID if \c v is unreachable from the root or if 254 ///\c v=s. The shortest path tree used here is equal to the shortest path 255 ///tree used in \ref pred(Node v). \pre \ref run() must be called before 220 ///Returns the 'previous node' of the %DFS tree. 221 222 ///For a node \c v it returns the 'previous node' on the %DFS tree, 223 ///i.e. it returns the last but one node of the path from the 224 ///root to \c /v on the %DFS tree. 225 ///It is INVALID if \c v is unreachable from the root or if 226 ///\c v=s. 227 ///\pre \ref run() must be called before 256 228 ///using this function. 257 229 Node predNode(Node v) const { return (*pred_node)[v]; } 258 230 259 ///Returns a reference to the NodeMap of distances. 260 261 ///Returns a reference to the NodeMap of distances. \pre \ref run() must 231 ///Returns a reference to the NodeMap of distances on the %DFS tree. 232 233 ///Returns a reference to the NodeMap of distances on the %DFS tree. 234 ///\pre \ref run() must 262 235 ///be called before using this function. 263 236 const DistMap &distMap() const { return *distance;} 264 237 265 ///Returns a reference to the shortest pathtree map.238 ///Returns a reference to the %DFS tree map. 266 239 267 240 ///Returns a reference to the NodeMap of the edges of the 268 /// shortest pathtree.241 ///%DFS tree. 269 242 ///\pre \ref run() must be called before using this function. 270 243 const PredMap &predMap() const { return *predecessor;} 271 244 272 ///Returns a reference to the map of nodes of shortest paths. 273 274 ///Returns a reference to the NodeMap of the last but one nodes of the 275 ///shortest path tree. 245 ///Returns a reference to the map of last but one nodes of the %DFS tree. 246 247 ///Returns a reference to the NodeMap of the last but one nodes of the paths 248 ///on the 249 ///%DFS tree. 276 250 ///\pre \ref run() must be called before using this function. 277 251 const PredNodeMap &predNodeMap() const { return *pred_node;} … … 288 262 }; 289 263 290 291 // **********************************************************************292 // IMPLEMENTATIONS293 // **********************************************************************294 295 264 /// @} 296 265
Note: See TracChangeset
for help on using the changeset viewer.
