1.1 --- a/doc/Doxyfile Wed Sep 01 15:08:41 2004 +0000
1.2 +++ b/doc/Doxyfile Wed Sep 01 15:37:36 2004 +0000
1.3 @@ -23,7 +23,7 @@
1.4 # This could be handy for archiving the generated documentation or
1.5 # if some version control system is used.
1.6
1.7 -PROJECT_NUMBER = 0.1
1.8 +PROJECT_NUMBER = 0.2
1.9
1.10 # The OUTPUT_DIRECTORY tag is used to specify the (relative or absolute)
1.11 # base path where the generated documentation will be put.
2.1 --- a/src/hugo/bfs.h Wed Sep 01 15:08:41 2004 +0000
2.2 +++ b/src/hugo/bfs.h Wed Sep 01 15:37:36 2004 +0000
2.3 @@ -16,33 +16,14 @@
2.4 /// \addtogroup flowalgs
2.5 /// @{
2.6
2.7 - ///%Bfs algorithm class.
2.8 + ///%BFS algorithm class.
2.9
2.10 - ///This class provides an efficient implementation of %Bfs algorithm.
2.11 - ///The edge lengths are passed to the algorithm using a
2.12 - ///\ref ReadMapSkeleton "readable map",
2.13 - ///so it is easy to change it to any kind of length.
2.14 + ///This class provides an efficient implementation of %BFS algorithm.
2.15 + ///\param GR The graph type the algorithm runs on.
2.16 + ///This class does the same as Dijkstra does with constant 1 edge length,
2.17 + ///but it is faster.
2.18 ///
2.19 - ///The type of the length is determined by the \c ValueType of the length map.
2.20 - ///
2.21 - ///It is also possible to change the underlying priority heap.
2.22 - ///
2.23 - ///\param GR The graph type the algorithm runs on.
2.24 - ///\param LM This read-only
2.25 - ///EdgeMap
2.26 - ///determines the
2.27 - ///lengths of the edges. It is read once for each edge, so the map
2.28 - ///may involve in relatively time consuming process to compute the edge
2.29 - ///length if it is necessary. The default map type is
2.30 - ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
2.31 - ///\param Heap The heap type used by the %Bfs
2.32 - ///algorithm. The default
2.33 - ///is using \ref BinHeap "binary heap".
2.34 - ///
2.35 - ///\author Jacint Szabo and Alpar Juttner
2.36 - ///\todo We need a typedef-names should be standardized. (-:
2.37 - ///\todo Type of \c PredMap, \c PredNodeMap and \c DistMap
2.38 - ///should not be fixed. (Problematic to solve).
2.39 + ///\author Alpar Juttner
2.40
2.41 #ifdef DOXYGEN
2.42 template <typename GR>
2.43 @@ -80,16 +61,9 @@
2.44 Node source;
2.45
2.46
2.47 - ///Initialize maps.
2.48 -
2.49 - ///\todo Error if \c G or are \c NULL.
2.50 - ///\todo Better memory allocation (instead of new).
2.51 + ///Initializes the maps.
2.52 void init_maps()
2.53 {
2.54 -// if(!length) {
2.55 -// local_length = true;
2.56 -// length = new LM(G);
2.57 -// }
2.58 if(!predecessor) {
2.59 local_predecessor = true;
2.60 predecessor = new PredMap(*G);
2.61 @@ -114,7 +88,6 @@
2.62
2.63 ~Bfs()
2.64 {
2.65 - // if(local_length) delete length;
2.66 if(local_predecessor) delete predecessor;
2.67 if(local_pred_node) delete pred_node;
2.68 if(local_distance) delete distance;
2.69 @@ -124,13 +97,13 @@
2.70
2.71 ///Sets the graph the algorithm will run on.
2.72 ///\return <tt> (*this) </tt>
2.73 + ///\bug What about maps?
2.74 + ///\todo It may be unnecessary
2.75 Bfs &setGraph(const Graph &_G)
2.76 {
2.77 G = &_G;
2.78 return *this;
2.79 }
2.80 - ///Sets the length map.
2.81 -
2.82 ///Sets the map storing the predecessor edges.
2.83
2.84 ///Sets the map storing the predecessor edges.
2.85 @@ -186,9 +159,9 @@
2.86
2.87 ///This method runs the %BFS algorithm from a root node \c s
2.88 ///in order to
2.89 - ///compute the
2.90 + ///compute a
2.91 ///shortest path to each node. The algorithm computes
2.92 - ///- The shortest path tree.
2.93 + ///- The %BFS tree.
2.94 ///- The distance of each node from the root.
2.95
2.96 void run(Node s) {
2.97 @@ -232,23 +205,23 @@
2.98 ///of this funcion is undefined.
2.99 int dist(Node v) const { return (*distance)[v]; }
2.100
2.101 - ///Returns the 'previous edge' of the shortest path tree.
2.102 + ///Returns the 'previous edge' of the %BFS path tree.
2.103
2.104 - ///For a node \c v it returns the 'previous edge' of the shortest path tree,
2.105 - ///i.e. it returns the last edge from a shortest path from the root to \c
2.106 + ///For a node \c v it returns the 'previous edge' of the %BFS tree,
2.107 + ///i.e. it returns the last edge of a shortest path from the root to \c
2.108 ///v. It is \ref INVALID
2.109 ///if \c v is unreachable from the root or if \c v=s. The
2.110 - ///shortest path tree used here is equal to the shortest path tree used in
2.111 + ///%BFS tree used here is equal to the %BFS tree used in
2.112 ///\ref predNode(Node v). \pre \ref run() must be called before using
2.113 ///this function.
2.114 Edge pred(Node v) const { return (*predecessor)[v]; }
2.115
2.116 - ///Returns the 'previous node' of the shortest path tree.
2.117 + ///Returns the 'previous node' of the %BFS tree.
2.118
2.119 - ///For a node \c v it returns the 'previous node' of the shortest path tree,
2.120 + ///For a node \c v it returns the 'previous node' on the %BFS tree,
2.121 ///i.e. it returns the last but one node from a shortest path from the
2.122 ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
2.123 - ///\c v=s. The shortest path tree used here is equal to the shortest path
2.124 + ///\c v=s. The shortest path tree used here is equal to the %BFS
2.125 ///tree used in \ref pred(Node v). \pre \ref run() must be called before
2.126 ///using this function.
2.127 Node predNode(Node v) const { return (*pred_node)[v]; }
2.128 @@ -259,17 +232,17 @@
2.129 ///be called before using this function.
2.130 const DistMap &distMap() const { return *distance;}
2.131
2.132 - ///Returns a reference to the shortest path tree map.
2.133 + ///Returns a reference to the %BFS tree map.
2.134
2.135 ///Returns a reference to the NodeMap of the edges of the
2.136 - ///shortest path tree.
2.137 + ///%BFS tree.
2.138 ///\pre \ref run() must be called before using this function.
2.139 const PredMap &predMap() const { return *predecessor;}
2.140
2.141 - ///Returns a reference to the map of nodes of shortest paths.
2.142 + ///Returns a reference to the map of last but one nodes of shortest paths.
2.143
2.144 - ///Returns a reference to the NodeMap of the last but one nodes of the
2.145 - ///shortest path tree.
2.146 + ///Returns a reference to the NodeMap of the last but one nodes on the
2.147 + ///%BFS tree.
2.148 ///\pre \ref run() must be called before using this function.
2.149 const PredNodeMap &predNodeMap() const { return *pred_node;}
2.150
2.151 @@ -284,11 +257,6 @@
2.152
2.153 };
2.154
2.155 -
2.156 - // **********************************************************************
2.157 - // IMPLEMENTATIONS
2.158 - // **********************************************************************
2.159 -
2.160 /// @}
2.161
2.162 } //END OF NAMESPACE HUGO
3.1 --- a/src/hugo/dfs.h Wed Sep 01 15:08:41 2004 +0000
3.2 +++ b/src/hugo/dfs.h Wed Sep 01 15:37:36 2004 +0000
3.3 @@ -4,7 +4,7 @@
3.4
3.5 ///\ingroup flowalgs
3.6 ///\file
3.7 -///\brief Dfs algorithm.
3.8 +///\brief %DFS algorithm.
3.9 ///
3.10 ///\todo Revise Manual.
3.11
3.12 @@ -16,33 +16,13 @@
3.13 /// \addtogroup flowalgs
3.14 /// @{
3.15
3.16 - ///%Dfs algorithm class.
3.17 + ///%DFS algorithm class.
3.18
3.19 - ///This class provides an efficient implementation of %Dfs algorithm.
3.20 - ///The edge lengths are passed to the algorithm using a
3.21 - ///\ref ReadMapSkeleton "readable map",
3.22 - ///so it is easy to change it to any kind of length.
3.23 - ///
3.24 - ///The type of the length is determined by the \c ValueType of the length map.
3.25 - ///
3.26 - ///It is also possible to change the underlying priority heap.
3.27 + ///This class provides an efficient implementation of %DFS algorithm.
3.28 ///
3.29 ///\param GR The graph type the algorithm runs on.
3.30 - ///\param LM This read-only
3.31 - ///EdgeMap
3.32 - ///determines the
3.33 - ///lengths of the edges. It is read once for each edge, so the map
3.34 - ///may involve in relatively time consuming process to compute the edge
3.35 - ///length if it is necessary. The default map type is
3.36 - ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
3.37 - ///\param Heap The heap type used by the %Dfs
3.38 - ///algorithm. The default
3.39 - ///is using \ref BinHeap "binary heap".
3.40 ///
3.41 - ///\author Jacint Szabo and Alpar Juttner
3.42 - ///\todo We need a typedef-names should be standardized. (-:
3.43 - ///\todo Type of \c PredMap, \c PredNodeMap and \c DistMap
3.44 - ///should not be fixed. (Problematic to solve).
3.45 + ///\author Alpar Juttner
3.46
3.47 #ifdef DOXYGEN
3.48 template <typename GR>
3.49 @@ -59,12 +39,12 @@
3.50 typedef typename Graph::OutEdgeIt OutEdgeIt;
3.51
3.52 ///\brief The type of the map that stores the last
3.53 - ///edges of the shortest paths.
3.54 + ///edges of the paths on the %DFS tree.
3.55 typedef typename Graph::template NodeMap<Edge> PredMap;
3.56 ///\brief The type of the map that stores the last but one
3.57 - ///nodes of the shortest paths.
3.58 + ///nodes of the paths on the %DFS tree.
3.59 typedef typename Graph::template NodeMap<Node> PredNodeMap;
3.60 - ///The type of the map that stores the dists of the nodes.
3.61 + ///The type of the map that stores the dists of the nodes on the %DFS tree.
3.62 typedef typename Graph::template NodeMap<int> DistMap;
3.63
3.64 private:
3.65 @@ -80,16 +60,9 @@
3.66 Node source;
3.67
3.68
3.69 - ///Initialize maps.
3.70 -
3.71 - ///\todo Error if \c G or are \c NULL.
3.72 - ///\todo Better memory allocation (instead of new).
3.73 + ///Initializes the maps.
3.74 void init_maps()
3.75 {
3.76 -// if(!length) {
3.77 -// local_length = true;
3.78 -// length = new LM(G);
3.79 -// }
3.80 if(!predecessor) {
3.81 local_predecessor = true;
3.82 predecessor = new PredMap(*G);
3.83 @@ -114,7 +87,6 @@
3.84
3.85 ~Dfs()
3.86 {
3.87 - // if(local_length) delete length;
3.88 if(local_predecessor) delete predecessor;
3.89 if(local_pred_node) delete pred_node;
3.90 if(local_distance) delete distance;
3.91 @@ -124,13 +96,13 @@
3.92
3.93 ///Sets the graph the algorithm will run on.
3.94 ///\return <tt> (*this) </tt>
3.95 + ///\bug What about maps?
3.96 + ///\todo It may be unnecessary
3.97 Dfs &setGraph(const Graph &_G)
3.98 {
3.99 G = &_G;
3.100 return *this;
3.101 }
3.102 - ///Sets the length map.
3.103 -
3.104 ///Sets the map storing the predecessor edges.
3.105
3.106 ///Sets the map storing the predecessor edges.
3.107 @@ -186,10 +158,9 @@
3.108
3.109 ///This method runs the %DFS algorithm from a root node \c s
3.110 ///in order to
3.111 - ///compute the
3.112 - ///shortest path to each node. The algorithm computes
3.113 - ///- The shortest path tree.
3.114 - ///- The distance of each node from the root.
3.115 + ///compute
3.116 + ///- a %DFS tree and
3.117 + ///- the distance of each node from the root on this tree.
3.118
3.119 void run(Node s) {
3.120
3.121 @@ -227,52 +198,55 @@
3.122 } while(Qh>=0);
3.123 }
3.124
3.125 - ///The distance of a node from the root.
3.126 + ///The distance of a node from the root on the %DFS tree.
3.127
3.128 - ///Returns the distance of a node from the root.
3.129 + ///Returns the distance of a node from the root on the %DFS tree.
3.130 ///\pre \ref run() must be called before using this function.
3.131 ///\warning If node \c v in unreachable from the root the return value
3.132 ///of this funcion is undefined.
3.133 int dist(Node v) const { return (*distance)[v]; }
3.134
3.135 - ///Returns the 'previous edge' of the shortest path tree.
3.136 + ///Returns the 'previous edge' of the %DFS path tree.
3.137
3.138 - ///For a node \c v it returns the 'previous edge' of the shortest path tree,
3.139 - ///i.e. it returns the last edge from a shortest path from the root to \c
3.140 + ///For a node \c v it returns the last edge of the path on the %DFS tree
3.141 + ///from the root to \c
3.142 ///v. It is \ref INVALID
3.143 ///if \c v is unreachable from the root or if \c v=s. The
3.144 - ///shortest path tree used here is equal to the shortest path tree used in
3.145 + ///%DFS tree used here is equal to the %DFS tree used in
3.146 ///\ref predNode(Node v). \pre \ref run() must be called before using
3.147 ///this function.
3.148 Edge pred(Node v) const { return (*predecessor)[v]; }
3.149
3.150 - ///Returns the 'previous node' of the shortest path tree.
3.151 + ///Returns the 'previous node' of the %DFS tree.
3.152
3.153 - ///For a node \c v it returns the 'previous node' of the shortest path tree,
3.154 - ///i.e. it returns the last but one node from a shortest path from the
3.155 - ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
3.156 - ///\c v=s. The shortest path tree used here is equal to the shortest path
3.157 - ///tree used in \ref pred(Node v). \pre \ref run() must be called before
3.158 + ///For a node \c v it returns the 'previous node' on the %DFS tree,
3.159 + ///i.e. it returns the last but one node of the path from the
3.160 + ///root to \c /v on the %DFS tree.
3.161 + ///It is INVALID if \c v is unreachable from the root or if
3.162 + ///\c v=s.
3.163 + ///\pre \ref run() must be called before
3.164 ///using this function.
3.165 Node predNode(Node v) const { return (*pred_node)[v]; }
3.166
3.167 - ///Returns a reference to the NodeMap of distances.
3.168 + ///Returns a reference to the NodeMap of distances on the %DFS tree.
3.169
3.170 - ///Returns a reference to the NodeMap of distances. \pre \ref run() must
3.171 + ///Returns a reference to the NodeMap of distances on the %DFS tree.
3.172 + ///\pre \ref run() must
3.173 ///be called before using this function.
3.174 const DistMap &distMap() const { return *distance;}
3.175
3.176 - ///Returns a reference to the shortest path tree map.
3.177 + ///Returns a reference to the %DFS tree map.
3.178
3.179 ///Returns a reference to the NodeMap of the edges of the
3.180 - ///shortest path tree.
3.181 + ///%DFS tree.
3.182 ///\pre \ref run() must be called before using this function.
3.183 const PredMap &predMap() const { return *predecessor;}
3.184
3.185 - ///Returns a reference to the map of nodes of shortest paths.
3.186 + ///Returns a reference to the map of last but one nodes of the %DFS tree.
3.187
3.188 - ///Returns a reference to the NodeMap of the last but one nodes of the
3.189 - ///shortest path tree.
3.190 + ///Returns a reference to the NodeMap of the last but one nodes of the paths
3.191 + ///on the
3.192 + ///%DFS tree.
3.193 ///\pre \ref run() must be called before using this function.
3.194 const PredNodeMap &predNodeMap() const { return *pred_node;}
3.195
3.196 @@ -287,11 +261,6 @@
3.197
3.198 };
3.199
3.200 -
3.201 - // **********************************************************************
3.202 - // IMPLEMENTATIONS
3.203 - // **********************************************************************
3.204 -
3.205 /// @}
3.206
3.207 } //END OF NAMESPACE HUGO