COIN-OR::LEMON - Graph Library

Changeset 954:5b1ffef43d4c in lemon-0.x for src/work


Ignore:
Timestamp:
11/01/04 20:00:19 (19 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1334
Message:

Improved docs.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/alpar/dijkstra.h

    r953 r954  
    3131/// @{
    3232
     33  ///Default traits class of Dijkstra class.
     34
     35  ///Default traits class of Dijkstra class.
     36  ///\param GR Graph type.
     37  ///\param LM Type of length map.
    3338  template<class GR, class LM>
    3439  struct DijkstraDefaultTraits
    3540  {
    36     ///\e
     41    ///The graph type the algorithm runs on.
    3742    typedef GR Graph;
    38     ///\e
    39     typedef typename Graph::Node Node;
    40     ///\e
    41     typedef typename Graph::Edge Edge;
    4243    ///The type of the map that stores the edge lengths.
    4344
     
    4546    ///
    4647    typedef LM LengthMap;
    47     ///The type of the length of the edges.
     48    //The type of the length of the edges.
    4849    typedef typename LM::ValueType ValueType;
    49     ///The heap type used by the dijkstra algorithm.
     50    ///The heap type used by Dijkstra algorithm.
    5051    typedef BinHeap<typename Graph::Node,
    5152                    typename LM::ValueType,
     
    5859    ///It must meet the \ref WriteMap concept.
    5960    ///
    60     typedef typename Graph::template NodeMap<Edge> PredMap;
    61     ///
     61    typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
     62    ///Instantiates a PredMap.
    6263 
    6364    ///\todo Please document...
    6465    ///
    65     static PredMap *createPredMap(const Graph &G)
     66    static PredMap *createPredMap(const GR &G)
    6667    {
    6768      return new PredMap(G);
     
    7273    ///It must meet the \ref WriteMap concept.
    7374    ///
    74     typedef typename Graph::template NodeMap<Node> PredNodeMap;
    75     ///
     75    typedef typename Graph::template NodeMap<typename GR::Node> PredNodeMap;
     76    ///Instantiates a PredNodeMap.
    7677 
    7778    ///\todo Please document...
    7879    ///
    79     static PredNodeMap *createPredNodeMap(const Graph &G)
     80    static PredNodeMap *createPredNodeMap(const GR &G)
    8081    {
    8182      return new PredNodeMap(G);
     
    8586    ///It must meet the \ref WriteMap concept.
    8687    ///
    87     typedef typename Graph::template NodeMap<ValueType> DistMap;
    88     ///
     88    typedef typename Graph::template NodeMap<typename LM::ValueType> DistMap;
     89    ///Instantiates a DistMap.
    8990 
    9091    ///\todo Please document...
    9192    ///
    92     static DistMap *createDistMap(const Graph &G)
     93    static DistMap *createDistMap(const GR &G)
    9394    {
    9495      return new DistMap(G);
     
    109110  ///
    110111  ///\param GR The graph type the algorithm runs on. The default value is
    111   ///\ref ListGraph
     112  ///\ref ListGraph. The value of GR is not used directly by %Dijsktra, it
     113  ///is only passed to \ref DijkstraDefaultTraits.
    112114  ///\param LM This read-only
    113115  ///EdgeMap
     
    116118  ///may involve in relatively time consuming process to compute the edge
    117119  ///length if it is necessary. The default map type is
    118   ///\ref skeleton::StaticGraph::EdgeMap "Graph::EdgeMap<int>"
    119   ///\param Heap The heap type used by the %Dijkstra
    120   ///algorithm. The default
    121   ///is using \ref BinHeap "binary heap".
     120  ///\ref skeleton::StaticGraph::EdgeMap "Graph::EdgeMap<int>".
     121  ///The value of LM is not used directly by %Dijsktra, it
     122  ///is only passed to \ref DijkstraDefaultTraits.
     123  ///\param TR Traits class to set various data types used by the algorithm.
     124  ///The default traits class is
     125  ///\ref DijkstraDefaultTraits<GR,LM> "DijkstraDefaultTraits<GR,LM>".
     126  ///See \ref DijkstraDefaultTraits for the documentation of
     127  ///a Dijkstra traits class.
    122128  ///
    123129  ///\author Jacint Szabo and Alpar Juttner
    124130  ///\todo We need a typedef-names should be standardized. (-:
    125   ///\todo Type of \c PredMap, \c PredNodeMap and \c DistMap
    126   ///should not be fixed. (Problematic to solve).
    127131
    128132#ifdef DOXYGEN
     
    139143    typedef TR Traits;
    140144    ///The type of the underlying graph.
    141     typedef GR Graph;
     145    typedef typename TR::Graph Graph;
    142146    ///\e
    143147    typedef typename Graph::Node Node;
     
    150154   
    151155    ///The type of the length of the edges.
    152     typedef typename LM::ValueType ValueType;
     156    typedef typename TR::LengthMap::ValueType ValueType;
    153157    ///The type of the map that stores the edge lengths.
    154     typedef LM LengthMap;
     158    typedef typename TR::LengthMap LengthMap;
    155159    ///\brief The type of the map that stores the last
    156160    ///edges of the shortest paths.
     
    161165    ///The type of the map that stores the dists of the nodes.
    162166    typedef typename TR::DistMap DistMap;
    163 
    164167    ///The heap type used by the dijkstra algorithm.
    165168    typedef typename TR::Heap Heap;
     
    169172    const Graph *G;
    170173    /// Pointer to the length map
    171     const LM *length;
     174    const LengthMap *length;
    172175    ///Pointer to the map of predecessors edges.
    173176    PredMap *predecessor;
     
    220223      }
    221224    };
    222     ///\ref named-templ-param "Named parameter" for setting PredMap's type
     225    ///\ref named-templ-param "Named parameter" for setting PredMap type
     226
     227    ///\ingroup flowalgs
     228    ///\ref named-templ-param "Named parameter" for setting PredMap type
    223229    template <class T>
    224230    class SetPredMap : public Dijkstra< Graph,
     
    238244      }
    239245    };
    240     ///\ref named-templ-param "Named parameter" for setting PredNodeMap's type
     246    ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
     247
     248    ///\ingroup flowalgs
     249    ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
    241250    template <class T>
    242251    class SetPredNodeMap : public Dijkstra< Graph,
     
    256265      }
    257266    };
    258     ///\ref named-templ-param "Named parameter" for setting DistMap's type
     267    ///\ref named-templ-param "Named parameter" for setting DistMap type
     268
     269    ///\ingroup flowalgs
     270    ///\ref named-templ-param "Named parameter" for setting DistMap type
    259271    template <class T>
    260272    class SetDistMap : public Dijkstra< Graph,
     
    266278    ///\param _G the graph the algorithm will run on.
    267279    ///\param _length the length map used by the algorithm.
    268     Dijkstra(const Graph& _G, const LM& _length) :
     280    Dijkstra(const Graph& _G, const LengthMap& _length) :
    269281      G(&_G), length(&_length),
    270282      predecessor(NULL), local_predecessor(false),
     
    285297    ///Sets the length map.
    286298    ///\return <tt> (*this) </tt>
    287     Dijkstra &setLengthMap(const LM &m)
     299    Dijkstra &setLengthMap(const LengthMap &m)
    288300    {
    289301      length = &m;
     
    350362  ///- The shortest path tree.
    351363  ///- The distance of each node from the root.
    352    
     364  ///\todo heap_map's type could also be in the traits class.
    353365    void run(Node s) {
    354366     
     
    362374      }
    363375     
    364       typename GR::template NodeMap<int> heap_map(*G,-1);
     376      typename Graph::template NodeMap<int> heap_map(*G,-1);
    365377     
    366378      Heap heap(heap_map);
     
    584596  ///\e
    585597
    586   ///\e
     598  ///\todo Please document...
    587599  ///
    588600  template<class GR, class LM>
Note: See TracChangeset for help on using the changeset viewer.