# Changeset 781:d4d182ab75bd in lemon-0.x

Ignore:
Timestamp:
09/01/04 17:37:36 (17 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1074
Message:

Changes in the doc.

Files:
3 edited

Unmodified
Removed
• ## doc/Doxyfile

 r666 # 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)
• ## src/hugo/bfs.h

 r780 /// @{ ///%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. ///%BFS algorithm class. ///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 ///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; ~Bfs() { //      if(local_length) delete length; if(local_predecessor) delete predecessor; if(local_pred_node) delete pred_node; ///Sets the graph the algorithm will run on. ///\return (*this) ///\bug What about maps? ///\todo It may be unnecessary Bfs &setGraph(const Graph &_G) { return *this; } ///Sets the length map. ///Sets the map storing the predecessor edges. ///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. int dist(Node v) const { return (*distance)[v]; } ///Returns the 'previous edge' of the shortest 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 ///Returns the 'previous edge' of the %BFS path tree. ///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. ///For a node \c v it 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' 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. 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 NodeMap of the last but one nodes of the ///shortest path tree. ///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 on the ///%BFS tree. ///\pre \ref run() must be called before using this function. const PredNodeMap &predNodeMap() const { return *pred_node;} }; // ********************************************************************** //  IMPLEMENTATIONS // ********************************************************************** /// @}
• ## src/hugo/dfs.h

 r780 ///\ingroup flowalgs ///\file ///\brief Dfs algorithm. ///\brief %DFS algorithm. /// ///\todo Revise Manual. /// @{ ///%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. ///%DFS algorithm class. ///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 ///\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; ///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; ~Dfs() { //      if(local_length) delete length; if(local_predecessor) delete predecessor; if(local_pred_node) delete pred_node; ///Sets the graph the algorithm will run on. ///\return (*this) ///\bug What about maps? ///\todo It may be unnecessary Dfs &setGraph(const Graph &_G) { return *this; } ///Sets the length map. ///Sets the map storing the predecessor edges. ///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) { } ///The distance of a node from the root. ///Returns 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 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 int dist(Node v) const { return (*distance)[v]; } ///Returns the 'previous edge' of the shortest 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 ///Returns the 'previous edge' of the %DFS path tree. ///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. ///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 ///Returns the 'previous node' of the %DFS tree. ///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. \pre \ref run() must ///Returns a reference to the NodeMap of distances on the %DFS tree. ///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 NodeMap of the last but one nodes of the ///shortest path tree. ///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 paths ///on the ///%DFS tree. ///\pre \ref run() must be called before using this function. const PredNodeMap &predNodeMap() const { return *pred_node;} }; // ********************************************************************** //  IMPLEMENTATIONS // ********************************************************************** /// @}
Note: See TracChangeset for help on using the changeset viewer.