COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 385:d7ebbae96025 in lemon-0.x for src/include


Ignore:
Timestamp:
04/23/04 21:04:05 (21 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@515
Message:

Some changes in the documentation.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/include/dijkstra.h

    r373 r385  
    11// -*- C++ -*-
    2 
    32#ifndef HUGO_DIJKSTRA_H
    43#define HUGO_DIJKSTRA_H
    … …  
    76///\brief Dijkstra algorithm.
    87
    9 #include <fib_heap.h>
    108#include <bin_heap.h>
    119#include <invalid.h>
    1210
    1311namespace hugo {
    14  
     12
    1513  ///%Dijkstra algorithm class.
    1614
    … …  
    2422  ///It is also possible to change the underlying priority heap.
    2523  ///
    26   ///\param Graph The graph type the algorithm runs on. 
    27   ///\param LengthMap This read-only EdgeMap determines the lengths of
    28   ///the edges. It is read once for each edge, so the map may involve
    29   ///in relatively time consuming process to compute the edge length
    30   ///if it is necessary. The default map type is \ref
    31   ///GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
    32   ///\param Heap The heap type used by the %Dijkstra algorithm. The
    33   ///default is using \ref BinHeap "binary heap".
     24  ///\param Graph The graph type the algorithm runs on.
     25  ///\param LengthMap This read-only
     26  ///EdgeMap
     27  ///determines the
     28  ///lengths of the edges. It is read once for each edge, so the map
     29  ///may involve in relatively time consuming process to compute the edge
     30  ///length if it is necessary. The default map type is
     31  ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
     32  ///\param Heap The heap type used by the %Dijkstra
     33  ///algorithm. The default
     34  ///is using \ref BinHeap "binary heap".
    3435 
    3536#ifdef DOXYGEN
    … …  
    6869    void run(Node s);
    6970   
    70     ///The distance of a node from the source.
     71    ///The distance of a node from the root.
    7172
    72     ///Returns the distance of a node from the source.
     73    ///Returns the distance of a node from the root.
    7374    ///\pre \ref run() must be called before using this function.
    74     ///\warning If node \c v in unreachable from the source the return value
     75    ///\warning If node \c v in unreachable from the root the return value
    7576    ///of this funcion is undefined.
    7677    ValueType dist(Node v) const { return distance[v]; }
    7778
    78     ///Returns the edges of the shortest path tree.
     79    ///Returns the previous edge of the shortest path tree.
    7980
    80     ///For a node \c v it returns the last edge of the shortest path
    81     ///from the source to \c v or INVALID if \c v is unreachable
    82     ///from the source.
    83     ///\pre \ref run() must be called before using this function.
     81    ///For a node \c v it returns the previous edge of the shortest path tree,
     82    ///i.e. it returns the last edge from a shortest path from the root to \c
     83    ///v. It is INVALID if \c v is unreachable from the root or if \c v=s. The
     84    ///shortest path tree used here is equal to the shortest path tree used in
     85    ///\ref predNode(Node v).  \pre \ref run() must be called before using
     86    ///this function.
    8487    Edge pred(Node v) const { return predecessor[v]; }
    8588
    86     ///Returns the nodes of the shortest paths.
     89    ///Returns the previous node of the shortest path tree.
    8790
    88     ///For a node \c v it returns the last but one node of the shortest path
    89     ///from the source to \c v or INVALID if \c v is unreachable
    90     ///from the source.
    91     ///\pre \ref run() must be called before using this function.
     91    ///For a node \c v it returns the previous node of the shortest path tree,
     92    ///i.e. it returns the last but one node from a shortest path from the
     93    ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
     94    ///\c v=s. The shortest path tree used here is equal to the shortest path
     95    ///tree used in \ref pred(Node v).  \pre \ref run() must be called before
     96    ///using this function.
    9297    Node predNode(Node v) const { return pred_node[v]; }
    9398   
    9499    ///Returns a reference to the NodeMap of distances.
    95100
    96     ///\pre \ref run() must be called before using this function.
    97     ///
     101    ///Returns a reference to the NodeMap of distances. \pre \ref run() must
     102    ///be called before using this function.
    98103    const DistMap &distMap() const { return distance;}
    99     
     104 
    100105    ///Returns a reference to the shortest path tree map.
    101106
    … …  
    104109    ///\pre \ref run() must be called before using this function.
    105110    const PredMap &predMap() const { return predecessor;}
    106     
    107     ///Returns a reference to the map of nodes of  shortest paths.
     111 
     112    ///Returns a reference to the map of nodes of shortest paths.
    108113
    109114    ///Returns a reference to the NodeMap of the last but one nodes of the
    110     ///shortest paths.
     115    ///shortest path tree.
    111116    ///\pre \ref run() must be called before using this function.
    112117    const PredNodeMap &predNodeMap() const { return pred_node;}
    113118
    114     ///Checks if a node is reachable from the source.
     119    ///Checks if a node is reachable from the root.
    115120
    116     ///Returns \c true if \c v is reachable from the source.
    117     ///\warning the source node is reported to be unreached!
     121    ///Returns \c true if \c v is reachable from the root.
     122    ///\warning the root node is reported to be unreached!
    118123    ///\todo Is this what we want?
    119124    ///\pre \ref run() must be called before using this function.
     125    ///
    120126    bool reached(Node v) { return G.valid(predecessor[v]); }
    121127   
    … …  
    127133  // **********************************************************************
    128134
    129   ///Runs %Dijkstra algorithm from source node \c s.
     135  ///Runs %Dijkstra algorithm from node the root.
    130136
    131   ///This method runs the %Dijkstra algorithm from a source node \c s
    132   ///in order to compute the shortest path to each node. The algorithm
    133   ///computes - The shortest path tree.  - The distance of each node
    134   ///from the source.
     137  ///This method runs the %Dijkstra algorithm from a root node \c s
     138  ///in order to
     139  ///compute the
     140  ///shortest path to each node. The algorithm computes
     141  ///- The shortest path tree.
     142  ///- The distance of each node from the root.
    135143  template <typename Graph, typename LengthMap,
    136144            template<class,class,class> class Heap >
    … …  
    146154   
    147155    Heap<Node,ValueType,typename Graph::NodeMap<int> > heap(heap_map);
     156   
    148157    heap.push(s,0);
    149158   
    150     while ( !heap.empty() ) {
    151      
    152       Node v=heap.top();
    153       ValueType oldvalue=heap[v];
    154       heap.pop();
    155       distance.set(v, oldvalue);
     159      while ( !heap.empty() ) {
    156160       
    157       { //FIXME this bracket is for e to be local
    158         OutEdgeIt e;
    159         for(G.first(e, v); G.valid(e); G.next(e)) {
     161        Node v=heap.top();
     162        ValueType oldvalue=heap[v];
     163        heap.pop();
     164        distance.set(v, oldvalue);
     165       
     166        { //FIXME this bracket is for e to be local
     167          OutEdgeIt e;
     168        for(G.first(e, v);
     169            G.valid(e); G.next(e)) {
    160170          Node w=G.head(e);
    161171         
    … …  
    177187          }
    178188        }
    179       } //FIXME this bracket
    180     }
     189      } //FIXME tis bracket
     190      }
    181191  }
    182192 
Note: See TracChangeset for help on using the changeset viewer.