1.1 --- a/src/hugo/bfs.h Wed Sep 01 15:08:41 2004 +0000
1.2 +++ b/src/hugo/bfs.h Wed Sep 01 15:37:36 2004 +0000
1.3 @@ -16,33 +16,14 @@
1.4 /// \addtogroup flowalgs
1.5 /// @{
1.6
1.7 - ///%Bfs algorithm class.
1.8 + ///%BFS algorithm class.
1.9
1.10 - ///This class provides an efficient implementation of %Bfs algorithm.
1.11 - ///The edge lengths are passed to the algorithm using a
1.12 - ///\ref ReadMapSkeleton "readable map",
1.13 - ///so it is easy to change it to any kind of length.
1.14 + ///This class provides an efficient implementation of %BFS algorithm.
1.15 + ///\param GR The graph type the algorithm runs on.
1.16 + ///This class does the same as Dijkstra does with constant 1 edge length,
1.17 + ///but it is faster.
1.18 ///
1.19 - ///The type of the length is determined by the \c ValueType of the length map.
1.20 - ///
1.21 - ///It is also possible to change the underlying priority heap.
1.22 - ///
1.23 - ///\param GR The graph type the algorithm runs on.
1.24 - ///\param LM This read-only
1.25 - ///EdgeMap
1.26 - ///determines the
1.27 - ///lengths of the edges. It is read once for each edge, so the map
1.28 - ///may involve in relatively time consuming process to compute the edge
1.29 - ///length if it is necessary. The default map type is
1.30 - ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
1.31 - ///\param Heap The heap type used by the %Bfs
1.32 - ///algorithm. The default
1.33 - ///is using \ref BinHeap "binary heap".
1.34 - ///
1.35 - ///\author Jacint Szabo and Alpar Juttner
1.36 - ///\todo We need a typedef-names should be standardized. (-:
1.37 - ///\todo Type of \c PredMap, \c PredNodeMap and \c DistMap
1.38 - ///should not be fixed. (Problematic to solve).
1.39 + ///\author Alpar Juttner
1.40
1.41 #ifdef DOXYGEN
1.42 template <typename GR>
1.43 @@ -80,16 +61,9 @@
1.44 Node source;
1.45
1.46
1.47 - ///Initialize maps.
1.48 -
1.49 - ///\todo Error if \c G or are \c NULL.
1.50 - ///\todo Better memory allocation (instead of new).
1.51 + ///Initializes the maps.
1.52 void init_maps()
1.53 {
1.54 -// if(!length) {
1.55 -// local_length = true;
1.56 -// length = new LM(G);
1.57 -// }
1.58 if(!predecessor) {
1.59 local_predecessor = true;
1.60 predecessor = new PredMap(*G);
1.61 @@ -114,7 +88,6 @@
1.62
1.63 ~Bfs()
1.64 {
1.65 - // if(local_length) delete length;
1.66 if(local_predecessor) delete predecessor;
1.67 if(local_pred_node) delete pred_node;
1.68 if(local_distance) delete distance;
1.69 @@ -124,13 +97,13 @@
1.70
1.71 ///Sets the graph the algorithm will run on.
1.72 ///\return <tt> (*this) </tt>
1.73 + ///\bug What about maps?
1.74 + ///\todo It may be unnecessary
1.75 Bfs &setGraph(const Graph &_G)
1.76 {
1.77 G = &_G;
1.78 return *this;
1.79 }
1.80 - ///Sets the length map.
1.81 -
1.82 ///Sets the map storing the predecessor edges.
1.83
1.84 ///Sets the map storing the predecessor edges.
1.85 @@ -186,9 +159,9 @@
1.86
1.87 ///This method runs the %BFS algorithm from a root node \c s
1.88 ///in order to
1.89 - ///compute the
1.90 + ///compute a
1.91 ///shortest path to each node. The algorithm computes
1.92 - ///- The shortest path tree.
1.93 + ///- The %BFS tree.
1.94 ///- The distance of each node from the root.
1.95
1.96 void run(Node s) {
1.97 @@ -232,23 +205,23 @@
1.98 ///of this funcion is undefined.
1.99 int dist(Node v) const { return (*distance)[v]; }
1.100
1.101 - ///Returns the 'previous edge' of the shortest path tree.
1.102 + ///Returns the 'previous edge' of the %BFS path tree.
1.103
1.104 - ///For a node \c v it returns the 'previous edge' of the shortest path tree,
1.105 - ///i.e. it returns the last edge from a shortest path from the root to \c
1.106 + ///For a node \c v it returns the 'previous edge' of the %BFS tree,
1.107 + ///i.e. it returns the last edge of a shortest path from the root to \c
1.108 ///v. It is \ref INVALID
1.109 ///if \c v is unreachable from the root or if \c v=s. The
1.110 - ///shortest path tree used here is equal to the shortest path tree used in
1.111 + ///%BFS tree used here is equal to the %BFS tree used in
1.112 ///\ref predNode(Node v). \pre \ref run() must be called before using
1.113 ///this function.
1.114 Edge pred(Node v) const { return (*predecessor)[v]; }
1.115
1.116 - ///Returns the 'previous node' of the shortest path tree.
1.117 + ///Returns the 'previous node' of the %BFS tree.
1.118
1.119 - ///For a node \c v it returns the 'previous node' of the shortest path tree,
1.120 + ///For a node \c v it returns the 'previous node' on the %BFS tree,
1.121 ///i.e. it returns the last but one node from a shortest path from the
1.122 ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
1.123 - ///\c v=s. The shortest path tree used here is equal to the shortest path
1.124 + ///\c v=s. The shortest path tree used here is equal to the %BFS
1.125 ///tree used in \ref pred(Node v). \pre \ref run() must be called before
1.126 ///using this function.
1.127 Node predNode(Node v) const { return (*pred_node)[v]; }
1.128 @@ -259,17 +232,17 @@
1.129 ///be called before using this function.
1.130 const DistMap &distMap() const { return *distance;}
1.131
1.132 - ///Returns a reference to the shortest path tree map.
1.133 + ///Returns a reference to the %BFS tree map.
1.134
1.135 ///Returns a reference to the NodeMap of the edges of the
1.136 - ///shortest path tree.
1.137 + ///%BFS tree.
1.138 ///\pre \ref run() must be called before using this function.
1.139 const PredMap &predMap() const { return *predecessor;}
1.140
1.141 - ///Returns a reference to the map of nodes of shortest paths.
1.142 + ///Returns a reference to the map of last but one nodes of shortest paths.
1.143
1.144 - ///Returns a reference to the NodeMap of the last but one nodes of the
1.145 - ///shortest path tree.
1.146 + ///Returns a reference to the NodeMap of the last but one nodes on the
1.147 + ///%BFS tree.
1.148 ///\pre \ref run() must be called before using this function.
1.149 const PredNodeMap &predNodeMap() const { return *pred_node;}
1.150
1.151 @@ -284,11 +257,6 @@
1.152
1.153 };
1.154
1.155 -
1.156 - // **********************************************************************
1.157 - // IMPLEMENTATIONS
1.158 - // **********************************************************************
1.159 -
1.160 /// @}
1.161
1.162 } //END OF NAMESPACE HUGO