# HG changeset patch # User alpar # Date 1094053056 0 # Node ID d4d182ab75bdc4774eae4a8b86e8c4bef0d0f83f # Parent e06d0d16595fc662fc9af22e95315c709676ecf1 Changes in the doc. diff -r e06d0d16595f -r d4d182ab75bd doc/Doxyfile --- a/doc/Doxyfile Wed Sep 01 15:08:41 2004 +0000 +++ b/doc/Doxyfile Wed Sep 01 15:37:36 2004 +0000 @@ -23,7 +23,7 @@ # This could be handy for archiving the generated documentation or # if some version control system is used. -PROJECT_NUMBER = 0.1 +PROJECT_NUMBER = 0.2 # The OUTPUT_DIRECTORY tag is used to specify the (relative or absolute) # base path where the generated documentation will be put. diff -r e06d0d16595f -r d4d182ab75bd src/hugo/bfs.h --- a/src/hugo/bfs.h Wed Sep 01 15:08:41 2004 +0000 +++ b/src/hugo/bfs.h Wed Sep 01 15:37:36 2004 +0000 @@ -16,33 +16,14 @@ /// \addtogroup flowalgs /// @{ - ///%Bfs algorithm class. + ///%BFS algorithm class. - ///This class provides an efficient implementation of %Bfs algorithm. - ///The edge lengths are passed to the algorithm using a - ///\ref ReadMapSkeleton "readable map", - ///so it is easy to change it to any kind of length. + ///This class provides an efficient implementation of %BFS algorithm. + ///\param GR The graph type the algorithm runs on. + ///This class does the same as Dijkstra does with constant 1 edge length, + ///but it is faster. /// - ///The type of the length is determined by the \c ValueType of the length map. - /// - ///It is also possible to change the underlying priority heap. - /// - ///\param GR The graph type the algorithm runs on. - ///\param LM This read-only - ///EdgeMap - ///determines the - ///lengths of the edges. It is read once for each edge, so the map - ///may involve in relatively time consuming process to compute the edge - ///length if it is necessary. The default map type is - ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap" - ///\param Heap The heap type used by the %Bfs - ///algorithm. The default - ///is using \ref BinHeap "binary heap". - /// - ///\author Jacint Szabo and Alpar Juttner - ///\todo We need a typedef-names should be standardized. (-: - ///\todo Type of \c PredMap, \c PredNodeMap and \c DistMap - ///should not be fixed. (Problematic to solve). + ///\author Alpar Juttner #ifdef DOXYGEN template @@ -80,16 +61,9 @@ Node source; - ///Initialize maps. - - ///\todo Error if \c G or are \c NULL. - ///\todo Better memory allocation (instead of new). + ///Initializes the maps. void init_maps() { -// if(!length) { -// local_length = true; -// length = new LM(G); -// } if(!predecessor) { local_predecessor = true; predecessor = new PredMap(*G); @@ -114,7 +88,6 @@ ~Bfs() { - // if(local_length) delete length; if(local_predecessor) delete predecessor; if(local_pred_node) delete pred_node; if(local_distance) delete distance; @@ -124,13 +97,13 @@ ///Sets the graph the algorithm will run on. ///\return (*this) + ///\bug What about maps? + ///\todo It may be unnecessary Bfs &setGraph(const Graph &_G) { G = &_G; return *this; } - ///Sets the length map. - ///Sets the map storing the predecessor edges. ///Sets the map storing the predecessor edges. @@ -186,9 +159,9 @@ ///This method runs the %BFS algorithm from a root node \c s ///in order to - ///compute the + ///compute a ///shortest path to each node. The algorithm computes - ///- The shortest path tree. + ///- The %BFS tree. ///- The distance of each node from the root. void run(Node s) { @@ -232,23 +205,23 @@ ///of this funcion is undefined. int dist(Node v) const { return (*distance)[v]; } - ///Returns the 'previous edge' of the shortest path tree. + ///Returns the 'previous edge' of the %BFS path tree. - ///For a node \c v it returns the 'previous edge' of the shortest path tree, - ///i.e. it returns the last edge from a shortest path from the root to \c + ///For a node \c v it returns the 'previous edge' of the %BFS tree, + ///i.e. it returns the last edge of a shortest path from the root to \c ///v. It is \ref INVALID ///if \c v is unreachable from the root or if \c v=s. The - ///shortest path tree used here is equal to the shortest path tree used in + ///%BFS tree used here is equal to the %BFS tree used in ///\ref predNode(Node v). \pre \ref run() must be called before using ///this function. Edge pred(Node v) const { return (*predecessor)[v]; } - ///Returns the 'previous node' of the shortest path tree. + ///Returns the 'previous node' of the %BFS tree. - ///For a node \c v it returns the 'previous node' of the shortest path tree, + ///For a node \c v it returns the 'previous node' on the %BFS tree, ///i.e. it returns the last but one node from a shortest path from the ///root to \c /v. It is INVALID if \c v is unreachable from the root or if - ///\c v=s. The shortest path tree used here is equal to the shortest path + ///\c v=s. The shortest path tree used here is equal to the %BFS ///tree used in \ref pred(Node v). \pre \ref run() must be called before ///using this function. Node predNode(Node v) const { return (*pred_node)[v]; } @@ -259,17 +232,17 @@ ///be called before using this function. const DistMap &distMap() const { return *distance;} - ///Returns a reference to the shortest path tree map. + ///Returns a reference to the %BFS tree map. ///Returns a reference to the NodeMap of the edges of the - ///shortest path tree. + ///%BFS tree. ///\pre \ref run() must be called before using this function. const PredMap &predMap() const { return *predecessor;} - ///Returns a reference to the map of nodes of shortest paths. + ///Returns a reference to the map of last but one nodes of shortest paths. - ///Returns a reference to the NodeMap of the last but one nodes of the - ///shortest path tree. + ///Returns a reference to the NodeMap of the last but one nodes on the + ///%BFS tree. ///\pre \ref run() must be called before using this function. const PredNodeMap &predNodeMap() const { return *pred_node;} @@ -284,11 +257,6 @@ }; - - // ********************************************************************** - // IMPLEMENTATIONS - // ********************************************************************** - /// @} } //END OF NAMESPACE HUGO diff -r e06d0d16595f -r d4d182ab75bd src/hugo/dfs.h --- a/src/hugo/dfs.h Wed Sep 01 15:08:41 2004 +0000 +++ b/src/hugo/dfs.h Wed Sep 01 15:37:36 2004 +0000 @@ -4,7 +4,7 @@ ///\ingroup flowalgs ///\file -///\brief Dfs algorithm. +///\brief %DFS algorithm. /// ///\todo Revise Manual. @@ -16,33 +16,13 @@ /// \addtogroup flowalgs /// @{ - ///%Dfs algorithm class. + ///%DFS algorithm class. - ///This class provides an efficient implementation of %Dfs algorithm. - ///The edge lengths are passed to the algorithm using a - ///\ref ReadMapSkeleton "readable map", - ///so it is easy to change it to any kind of length. - /// - ///The type of the length is determined by the \c ValueType of the length map. - /// - ///It is also possible to change the underlying priority heap. + ///This class provides an efficient implementation of %DFS algorithm. /// ///\param GR The graph type the algorithm runs on. - ///\param LM This read-only - ///EdgeMap - ///determines the - ///lengths of the edges. It is read once for each edge, so the map - ///may involve in relatively time consuming process to compute the edge - ///length if it is necessary. The default map type is - ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap" - ///\param Heap The heap type used by the %Dfs - ///algorithm. The default - ///is using \ref BinHeap "binary heap". /// - ///\author Jacint Szabo and Alpar Juttner - ///\todo We need a typedef-names should be standardized. (-: - ///\todo Type of \c PredMap, \c PredNodeMap and \c DistMap - ///should not be fixed. (Problematic to solve). + ///\author Alpar Juttner #ifdef DOXYGEN template @@ -59,12 +39,12 @@ typedef typename Graph::OutEdgeIt OutEdgeIt; ///\brief The type of the map that stores the last - ///edges of the shortest paths. + ///edges of the paths on the %DFS tree. typedef typename Graph::template NodeMap PredMap; ///\brief The type of the map that stores the last but one - ///nodes of the shortest paths. + ///nodes of the paths on the %DFS tree. typedef typename Graph::template NodeMap PredNodeMap; - ///The type of the map that stores the dists of the nodes. + ///The type of the map that stores the dists of the nodes on the %DFS tree. typedef typename Graph::template NodeMap DistMap; private: @@ -80,16 +60,9 @@ Node source; - ///Initialize maps. - - ///\todo Error if \c G or are \c NULL. - ///\todo Better memory allocation (instead of new). + ///Initializes the maps. void init_maps() { -// if(!length) { -// local_length = true; -// length = new LM(G); -// } if(!predecessor) { local_predecessor = true; predecessor = new PredMap(*G); @@ -114,7 +87,6 @@ ~Dfs() { - // if(local_length) delete length; if(local_predecessor) delete predecessor; if(local_pred_node) delete pred_node; if(local_distance) delete distance; @@ -124,13 +96,13 @@ ///Sets the graph the algorithm will run on. ///\return (*this) + ///\bug What about maps? + ///\todo It may be unnecessary Dfs &setGraph(const Graph &_G) { G = &_G; return *this; } - ///Sets the length map. - ///Sets the map storing the predecessor edges. ///Sets the map storing the predecessor edges. @@ -186,10 +158,9 @@ ///This method runs the %DFS algorithm from a root node \c s ///in order to - ///compute the - ///shortest path to each node. The algorithm computes - ///- The shortest path tree. - ///- The distance of each node from the root. + ///compute + ///- a %DFS tree and + ///- the distance of each node from the root on this tree. void run(Node s) { @@ -227,52 +198,55 @@ } while(Qh>=0); } - ///The distance of a node from the root. + ///The distance of a node from the root on the %DFS tree. - ///Returns the distance of a node from the root. + ///Returns the distance of a node from the root on the %DFS tree. ///\pre \ref run() must be called before using this function. ///\warning If node \c v in unreachable from the root the return value ///of this funcion is undefined. int dist(Node v) const { return (*distance)[v]; } - ///Returns the 'previous edge' of the shortest path tree. + ///Returns the 'previous edge' of the %DFS path tree. - ///For a node \c v it returns the 'previous edge' of the shortest path tree, - ///i.e. it returns the last edge from a shortest path from the root to \c + ///For a node \c v it returns the last edge of the path on the %DFS tree + ///from the root to \c ///v. It is \ref INVALID ///if \c v is unreachable from the root or if \c v=s. The - ///shortest path tree used here is equal to the shortest path tree used in + ///%DFS tree used here is equal to the %DFS tree used in ///\ref predNode(Node v). \pre \ref run() must be called before using ///this function. Edge pred(Node v) const { return (*predecessor)[v]; } - ///Returns the 'previous node' of the shortest path tree. + ///Returns the 'previous node' of the %DFS tree. - ///For a node \c v it returns the 'previous node' of the shortest path tree, - ///i.e. it returns the last but one node from a shortest path from the - ///root to \c /v. It is INVALID if \c v is unreachable from the root or if - ///\c v=s. The shortest path tree used here is equal to the shortest path - ///tree used in \ref pred(Node v). \pre \ref run() must be called before + ///For a node \c v it returns the 'previous node' on the %DFS tree, + ///i.e. it returns the last but one node of the path from the + ///root to \c /v on the %DFS tree. + ///It is INVALID if \c v is unreachable from the root or if + ///\c v=s. + ///\pre \ref run() must be called before ///using this function. Node predNode(Node v) const { return (*pred_node)[v]; } - ///Returns a reference to the NodeMap of distances. + ///Returns a reference to the NodeMap of distances on the %DFS tree. - ///Returns a reference to the NodeMap of distances. \pre \ref run() must + ///Returns a reference to the NodeMap of distances on the %DFS tree. + ///\pre \ref run() must ///be called before using this function. const DistMap &distMap() const { return *distance;} - ///Returns a reference to the shortest path tree map. + ///Returns a reference to the %DFS tree map. ///Returns a reference to the NodeMap of the edges of the - ///shortest path tree. + ///%DFS tree. ///\pre \ref run() must be called before using this function. const PredMap &predMap() const { return *predecessor;} - ///Returns a reference to the map of nodes of shortest paths. + ///Returns a reference to the map of last but one nodes of the %DFS tree. - ///Returns a reference to the NodeMap of the last but one nodes of the - ///shortest path tree. + ///Returns a reference to the NodeMap of the last but one nodes of the paths + ///on the + ///%DFS tree. ///\pre \ref run() must be called before using this function. const PredNodeMap &predNodeMap() const { return *pred_node;} @@ -287,11 +261,6 @@ }; - - // ********************************************************************** - // IMPLEMENTATIONS - // ********************************************************************** - /// @} } //END OF NAMESPACE HUGO