COIN-OR::LEMON - Graph Library

Changeset 584:1d4855f5312e in lemon-0.x


Ignore:
Timestamp:
05/08/04 17:58:34 (16 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@761
Message:

Some new typedefs.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/hugo/dijkstra.h

    r570 r584  
    2626  ///It is also possible to change the underlying priority heap.
    2727  ///
    28   ///\param Graph The graph type the algorithm runs on.
    29   ///\param LengthMap This read-only
     28  ///\param GR The graph type the algorithm runs on.
     29  ///\param LM This read-only
    3030  ///EdgeMap
    3131  ///determines the
     
    3939  ///
    4040  ///\author Jacint Szabo
    41   ///\todo We need a LengthMap typedef
     41  ///\todo We need a typedef-names should be standardized.
     42
    4243#ifdef DOXYGEN
    43   template <typename Graph,
    44             typename LengthMap,
     44  template <typename GR,
     45            typename LM,
    4546            typename Heap>
    4647#else
    47   template <typename Graph,
    48             typename LengthMap=typename Graph::template EdgeMap<int>,
     48  template <typename GR,
     49            typename LM=typename GR::template EdgeMap<int>,
    4950            template <class,class,class,class> class Heap = BinHeap >
    5051#endif
    5152  class Dijkstra{
    5253  public:
     54    ///The type of the underlying graph.
     55    typedef GR Graph;
    5356    typedef typename Graph::Node Node;
    5457    typedef typename Graph::NodeIt NodeIt;
     
    5659    typedef typename Graph::OutEdgeIt OutEdgeIt;
    5760   
    58     typedef typename LengthMap::ValueType ValueType;
     61    ///The type of the length of the edges.
     62    typedef typename LM::ValueType ValueType;
     63    ///The the type of the map that stores the edge lengths.
     64    typedef LM LengthMap;
     65    ///\brief The the type of the map that stores the last
     66    ///edges of the shortest paths.
    5967    typedef typename Graph::template NodeMap<Edge> PredMap;
     68    ///\brief The the type of the map that stores the last but one
     69    ///nodes of the shortest paths.
    6070    typedef typename Graph::template NodeMap<Node> PredNodeMap;
     71    ///The the type of the map that stores the dists of the nodes.
    6172    typedef typename Graph::template NodeMap<ValueType> DistMap;
    6273
    6374  private:
    6475    const Graph& G;
    65     const LengthMap& length;
     76    const LM& length;
    6677    PredMap predecessor;
    6778    PredNodeMap pred_node;
     
    7081  public :
    7182   
    72     Dijkstra(const Graph& _G, const LengthMap& _length) :
     83    Dijkstra(const Graph& _G, const LM& _length) :
    7384      G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { }
    7485   
     
    8394    ValueType dist(Node v) const { return distance[v]; }
    8495
    85     ///Returns the previous edge of the shortest path tree.
    86 
    87     ///For a node \c v it returns the previous edge of the shortest path tree,
     96    ///Returns the 'previous edge' of the shortest path tree.
     97
     98    ///For a node \c v it returns the 'previous edge' of the shortest path tree,
    8899    ///i.e. it returns the last edge from a shortest path from the root to \c
    89100    ///v. It is INVALID if \c v is unreachable from the root or if \c v=s. The
     
    93104    Edge pred(Node v) const { return predecessor[v]; }
    94105
    95     ///Returns the previous node of the shortest path tree.
    96 
    97     ///For a node \c v it returns the previous node of the shortest path tree,
     106    ///Returns the 'previous node' of the shortest path tree.
     107
     108    ///For a node \c v it returns the 'previous node' of the shortest path tree,
    98109    ///i.e. it returns the last but one node from a shortest path from the
    99110    ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
     
    147158  ///- The shortest path tree.
    148159  ///- The distance of each node from the root.
    149   template <typename Graph, typename LengthMap,
     160  template <typename GR, typename LM,
    150161            template<class,class,class,class> class Heap >
    151   void Dijkstra<Graph,LengthMap,Heap>::run(Node s) {
     162  void Dijkstra<GR,LM,Heap>::run(Node s) {
    152163   
    153164    NodeIt u;
     
    157168    }
    158169   
    159     typename Graph::template NodeMap<int> heap_map(G,-1);
    160    
    161     typedef Heap<Node, ValueType, typename Graph::template NodeMap<int>,
     170    typename GR::template NodeMap<int> heap_map(G,-1);
     171   
     172    typedef Heap<Node, ValueType, typename GR::template NodeMap<int>,
    162173      std::less<ValueType> >
    163174      HeapType;
Note: See TracChangeset for help on using the changeset viewer.