COIN-OR::LEMON - Graph Library

Changeset 781:d4d182ab75bd in lemon-0.x


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

Changes in the doc.

Files:
3 edited

Legend:

Unmodified
Added
Removed
  • doc/Doxyfile

    r666 r781  
    2424# if some version control system is used.
    2525
    26 PROJECT_NUMBER         = 0.1
     26PROJECT_NUMBER         = 0.2
    2727
    2828# The OUTPUT_DIRECTORY tag is used to specify the (relative or absolute)
  • src/hugo/bfs.h

    r780 r781  
    1717/// @{
    1818
    19   ///%Bfs algorithm class.
    20 
    21   ///This class provides an efficient implementation of %Bfs 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.
     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.
    2525  ///
    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
    4627
    4728#ifdef DOXYGEN
     
    8162
    8263
    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.
    8765    void init_maps()
    8866    {
    89 //       if(!length) {
    90 //      local_length = true;
    91 //      length = new LM(G);
    92 //       }
    9367      if(!predecessor) {
    9468        local_predecessor = true;
     
    11589    ~Bfs()
    11690    {
    117       //      if(local_length) delete length;
    11891      if(local_predecessor) delete predecessor;
    11992      if(local_pred_node) delete pred_node;
     
    12598    ///Sets the graph the algorithm will run on.
    12699    ///\return <tt> (*this) </tt>
     100    ///\bug What about maps?
     101    ///\todo It may be unnecessary
    127102    Bfs &setGraph(const Graph &_G)
    128103    {
     
    130105      return *this;
    131106    }
    132     ///Sets the length map.
    133 
    134107    ///Sets the map storing the predecessor edges.
    135108
     
    187160  ///This method runs the %BFS algorithm from a root node \c s
    188161  ///in order to
    189   ///compute the
     162  ///compute a
    190163  ///shortest path to each node. The algorithm computes
    191   ///- The shortest path tree.
     164  ///- The %BFS tree.
    192165  ///- The distance of each node from the root.
    193166 
     
    233206    int dist(Node v) const { return (*distance)[v]; }
    234207
    235     ///Returns the 'previous edge' of the shortest path tree.
    236 
    237     ///For a node \c v it returns the 'previous edge' of the shortest path tree,
    238     ///i.e. it returns the last edge from a shortest path from the root to \c
     208    ///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
    239212    ///v. It is \ref INVALID
    240213    ///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 path tree used in
     214    ///%BFS tree used here is equal to the %BFS tree used in
    242215    ///\ref predNode(Node v).  \pre \ref run() must be called before using
    243216    ///this function.
    244217    Edge pred(Node v) const { return (*predecessor)[v]; }
    245218
    246     ///Returns the 'previous node' of the shortest path tree.
    247 
    248     ///For a node \c v it returns the 'previous node' of the shortest path tree,
     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,
    249222    ///i.e. it returns the last but one node from a shortest path from the
    250223    ///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 path
     224    ///\c v=s. The shortest path tree used here is equal to the %BFS
    252225    ///tree used in \ref pred(Node v).  \pre \ref run() must be called before
    253226    ///using this function.
     
    260233    const DistMap &distMap() const { return *distance;}
    261234 
    262     ///Returns a reference to the shortest path tree map.
     235    ///Returns a reference to the %BFS tree map.
    263236
    264237    ///Returns a reference to the NodeMap of the edges of the
    265     ///shortest path tree.
     238    ///%BFS tree.
    266239    ///\pre \ref run() must be called before using this function.
    267240    const PredMap &predMap() const { return *predecessor;}
    268241 
    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 of the
    272     ///shortest path tree.
     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.
    273246    ///\pre \ref run() must be called before using this function.
    274247    const PredNodeMap &predNodeMap() const { return *pred_node;}
     
    285258  };
    286259 
    287 
    288   // **********************************************************************
    289   //  IMPLEMENTATIONS
    290   // **********************************************************************
    291 
    292260/// @}
    293261 
  • src/hugo/dfs.h

    r780 r781  
    55///\ingroup flowalgs
    66///\file
    7 ///\brief Dfs algorithm.
     7///\brief %DFS algorithm.
    88///
    99///\todo Revise Manual.
     
    1717/// @{
    1818
    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.
    2922  ///
    3023  ///\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 %Dfs
    39   ///algorithm. The default
    40   ///is using \ref BinHeap "binary heap".
    4124  ///
    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
    4626
    4727#ifdef DOXYGEN
     
    6040   
    6141    ///\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.
    6343    typedef typename Graph::template NodeMap<Edge> PredMap;
    6444    ///\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.
    6646    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.
    6848    typedef typename Graph::template NodeMap<int> DistMap;
    6949
     
    8161
    8262
    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.
    8764    void init_maps()
    8865    {
    89 //       if(!length) {
    90 //      local_length = true;
    91 //      length = new LM(G);
    92 //       }
    9366      if(!predecessor) {
    9467        local_predecessor = true;
     
    11588    ~Dfs()
    11689    {
    117       //      if(local_length) delete length;
    11890      if(local_predecessor) delete predecessor;
    11991      if(local_pred_node) delete pred_node;
     
    12597    ///Sets the graph the algorithm will run on.
    12698    ///\return <tt> (*this) </tt>
     99    ///\bug What about maps?
     100    ///\todo It may be unnecessary
    127101    Dfs &setGraph(const Graph &_G)
    128102    {
     
    130104      return *this;
    131105    }
    132     ///Sets the length map.
    133 
    134106    ///Sets the map storing the predecessor edges.
    135107
     
    187159  ///This method runs the %DFS algorithm from a root node \c s
    188160  ///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.
    193164 
    194165    void run(Node s) {
     
    228199    }
    229200   
    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.
    233204    ///\pre \ref run() must be called before using this function.
    234205    ///\warning If node \c v in unreachable from the root the return value
     
    236207    int dist(Node v) const { return (*distance)[v]; }
    237208
    238     ///Returns the 'previous edge' of the shortest path 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 path from the root to \c
     209    ///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
    242213    ///v. It is \ref INVALID
    243214    ///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 path tree used in
     215    ///%DFS tree used here is equal to the %DFS tree used in
    245216    ///\ref predNode(Node v).  \pre \ref run() must be called before using
    246217    ///this function.
    247218    Edge pred(Node v) const { return (*predecessor)[v]; }
    248219
    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
    256228    ///using this function.
    257229    Node predNode(Node v) const { return (*pred_node)[v]; }
    258230   
    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
    262235    ///be called before using this function.
    263236    const DistMap &distMap() const { return *distance;}
    264237 
    265     ///Returns a reference to the shortest path tree map.
     238    ///Returns a reference to the %DFS tree map.
    266239
    267240    ///Returns a reference to the NodeMap of the edges of the
    268     ///shortest path tree.
     241    ///%DFS tree.
    269242    ///\pre \ref run() must be called before using this function.
    270243    const PredMap &predMap() const { return *predecessor;}
    271244 
    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.
    276250    ///\pre \ref run() must be called before using this function.
    277251    const PredNodeMap &predNodeMap() const { return *pred_node;}
     
    288262  };
    289263 
    290 
    291   // **********************************************************************
    292   //  IMPLEMENTATIONS
    293   // **********************************************************************
    294 
    295264/// @}
    296265 
Note: See TracChangeset for help on using the changeset viewer.