COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/alpar/dijkstra/dijkstra.h @ 222:0c6bd3a98edf

Last change on this file since 222:0c6bd3a98edf was 222:0c6bd3a98edf, checked in by Alpar Juttner, 16 years ago

Aprosagok...

File size: 3.7 KB
Line 
1// -*- C++ -*-
2/*
3 *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> >
4 *
5 *Constructor:
6 *
7 *Dijkstra(Graph G, LengthMap length)
8 *
9 *
10 *Methods:
11 *
12 *void run(Node s)
13 *
14 *T dist(Node v) : After run(s) was run, it returns the distance from s to v.
15 *   Returns T() if v is not reachable from s.
16 *
17 *Edge pred(Node v) : After run(s) was run, it returns the last
18 *   edge of a shortest s-v path. It is INVALID for s and for
19 *   the nodes not reachable from s.
20 *
21 *bool reached(Node v) : After run(s) was run, it is true iff v is
22 *   reachable from s
23 *
24 */
25
26#ifndef HUGO_DIJKSTRA_H
27#define HUGO_DIJKSTRA_H
28
29#include <fib_heap.h>
30#include <invalid.h>
31
32namespace hugo {
33 
34  //Alpar: Changed the order of the parameters
35  template <typename Graph,
36            typename LengthMap=typename Graph::EdgeMap<int>,
37            typename Heap=FibHeap<typename Graph::Node,
38                                  typename LengthMap::ValueType,
39                                  typename Graph::NodeMap<int> > >
40  class Dijkstra{
41  public:
42    typedef typename LengthMap::ValueType ValueType;
43
44  private:
45    typedef typename Graph::Node Node;
46    typedef typename Graph::NodeIt NodeIt;
47    typedef typename Graph::Edge Edge;
48    typedef typename Graph::OutEdgeIt OutEdgeIt;
49   
50    const Graph& G;
51    const LengthMap& length;
52    typedef typename Graph::NodeMap<Edge> PredMap;
53    PredMap predecessor;
54    //In place of reach:
55    typedef typename Graph::NodeMap<Node> PredNodeMap;
56    PredNodeMap pred_node;
57    typedef typename Graph::NodeMap<ValueType> DistMap;
58    DistMap distance;
59    //I don't like this:
60    //     //FIXME:
61    //     typename Graph::NodeMap<bool> reach;
62    //     //typename Graph::NodeMap<int> reach;
63   
64  public :
65   
66    /*
67      The distance of the nodes is 0.
68    */
69    Dijkstra(Graph& _G, LengthMap& _length) :
70      G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { }
71   
72
73    void run(Node s);
74   
75    ValueType dist(Node v) const { return distance[v]; }
76    Edge pred(Node v) const { return predecessor[v]; }
77    Node predNode(Node v) const { return pred_node[v]; }
78   
79    const DistMap &distMap() const { return distance;}
80    const PredMap &predMap() const { return predecessor;}
81    const PredNodeMap &predNodeMap() const { return pred_node;}
82
83    //    bool reached(Node v) { return reach[v]; }
84    ///\warning \c s is not reached!
85    ///
86    bool reached(Node v) { return G.valid(predecessor[v]); }
87   
88  };
89 
90
91  // IMPLEMENTATIONS
92
93  template <typename Graph, typename LengthMap, typename Heap >
94  void Dijkstra<Graph,LengthMap,Heap>::run(Node s) {
95   
96    NodeIt u;
97    for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
98      predecessor.set(u,INVALID);
99      // If a node is unreacheable, then why should be the dist=0?
100      // distance.set(u,0);
101      //      reach.set(u,false);
102    }
103   
104    //We don't need it at all.
105    //     //FIXME:
106    //     typename Graph::NodeMap<bool> scanned(G,false);
107    //     //typename Graph::NodeMap<int> scanned(G,false);
108    typename Graph::NodeMap<int> heap_map(G,-1);
109   
110    Heap heap(heap_map);
111   
112    heap.push(s,0);
113    //    reach.set(s, true);
114   
115      while ( !heap.empty() ) {
116       
117        Node v=heap.top();
118        ValueType oldvalue=heap[v];
119        heap.pop();
120        distance.set(v, oldvalue);
121       
122        for(OutEdgeIt e(G,v); G.valid(e); G.next(e)) {
123          Node w=G.head(e);
124         
125          switch(heap.state(w)) {
126          case Heap::PRE_HEAP:
127            //      reach.set(w,true);
128            heap.push(w,oldvalue+length[e]);
129            predecessor.set(w,e);
130            pred_node.set(w,v);
131            break;
132          case Heap::IN_HEAP:
133            if ( oldvalue+length[e] < heap[w] ) {
134              heap.decrease(w, oldvalue+length[e]);
135              predecessor.set(w,e);
136              pred_node.set(w,v);
137            }
138            break;
139          case Heap::POST_HEAP:
140            break;
141          }
142        }
143      }
144  }
145 
146} //END OF NAMESPACE HUGO
147
148#endif
149
150
Note: See TracBrowser for help on using the repository browser.