1.1 --- a/src/work/alpar/dijkstra/bin_heap.hh Sun Mar 21 14:58:48 2004 +0000
1.2 +++ b/src/work/alpar/dijkstra/bin_heap.hh Sun Mar 21 14:59:51 2004 +0000
1.3 @@ -65,6 +65,7 @@
1.4
1.5 namespace hugo {
1.6
1.7 + /// A Binary Heap implementation.
1.8 template <typename Key, typename Val, typename KeyIntMap,
1.9 typename Compare = std::less<Val> >
1.10 class BinHeap {
2.1 --- a/src/work/alpar/dijkstra/dijkstra.h Sun Mar 21 14:58:48 2004 +0000
2.2 +++ b/src/work/alpar/dijkstra/dijkstra.h Sun Mar 21 14:59:51 2004 +0000
2.3 @@ -32,14 +32,37 @@
2.4 namespace hugo {
2.5
2.6 //Alpar: Changed the order of the parameters
2.7 +
2.8 + ///Dijkstra algorithm class.
2.9 +
2.10 + ///This class provides an efficient implementation of Dijkstra algorithm.
2.11 + ///The edge lengths are passed to the algorithm using a
2.12 + ///\ref ReadMapSkeleton "readable map",
2.13 + ///so it is easy to change it to any kind of length.
2.14 + ///
2.15 + ///The type of the length is determined by the \c ValueType of the length map.
2.16 + ///
2.17 + ///It is also posible to change the underlying priority heap.
2.18 + ///
2.19 + ///\param Graph The graph type the algorithm runs on.
2.20 + ///\param LengthMap This read-only EdgeMap determines the
2.21 + ///lengths of the edges. It is read once for each edge, so the map
2.22 + ///may involve in relatively time consuming process to compute the edge
2.23 + ///length if it is necessary.
2.24 + ///\param Heap The heap type used by the Dijkstra
2.25 + ///algorithm. The default
2.26 + ///is using \ref BinHeap "binary heap".
2.27 template <typename Graph,
2.28 typename LengthMap=typename Graph::EdgeMap<int>,
2.29 - typename Heap=FibHeap<typename Graph::Node,
2.30 + typename Heap=BinHeap<typename Graph::Node,
2.31 typename LengthMap::ValueType,
2.32 typename Graph::NodeMap<int> > >
2.33 class Dijkstra{
2.34 public:
2.35 typedef typename LengthMap::ValueType ValueType;
2.36 + typedef typename Graph::NodeMap<Edge> PredMap;
2.37 + typedef typename Graph::NodeMap<Node> PredNodeMap;
2.38 + typedef typename Graph::NodeMap<ValueType> DistMap;
2.39
2.40 private:
2.41 typedef typename Graph::Node Node;
2.42 @@ -49,12 +72,9 @@
2.43
2.44 const Graph& G;
2.45 const LengthMap& length;
2.46 - typedef typename Graph::NodeMap<Edge> PredMap;
2.47 PredMap predecessor;
2.48 //In place of reach:
2.49 - typedef typename Graph::NodeMap<Node> PredNodeMap;
2.50 PredNodeMap pred_node;
2.51 - typedef typename Graph::NodeMap<ValueType> DistMap;
2.52 DistMap distance;
2.53 //I don't like this:
2.54 // //FIXME:
2.55 @@ -72,30 +92,76 @@
2.56
2.57 void run(Node s);
2.58
2.59 + ///The distance of a node from the source.
2.60 +
2.61 + ///Returns the distance of a node from the source.
2.62 + ///\pre \ref run() must be called before using this function.
2.63 + ///\warning If node \c v in unreachable from \c s the return value
2.64 + ///of this funcion is undefined.
2.65 ValueType dist(Node v) const { return distance[v]; }
2.66 + ///Returns the edges of the shortest path tree.
2.67 +
2.68 + ///For a node \c v it returns the last edge of the shortest path
2.69 + ///from \c s to \c v or INVALID if \c v is unreachable from \c s.
2.70 + ///\pre \ref run() must be called before using this function.
2.71 Edge pred(Node v) const { return predecessor[v]; }
2.72 + ///Returns the nodes of the shortest paths.
2.73 +
2.74 + ///For a node \c v it returns the last but one node of the shortest path
2.75 + ///from \c s to \c v or INVALID if \c v is unreachable from \c s.
2.76 + ///\pre \ref run() must be called before using this function.
2.77 Node predNode(Node v) const { return pred_node[v]; }
2.78
2.79 + ///Returns a reference to the NodeMap of distances.
2.80 +
2.81 + ///\pre \ref run() must be called before using this function.
2.82 + ///
2.83 const DistMap &distMap() const { return distance;}
2.84 + ///Returns a reference to the shortest path tree map.
2.85 +
2.86 + ///Returns a reference to the NodeMap of the edges of the
2.87 + ///shortest path tree.
2.88 + ///\pre \ref run() must be called before using this function.
2.89 const PredMap &predMap() const { return predecessor;}
2.90 + ///Returns a reference to the map of nodes of shortest paths.
2.91 +
2.92 + ///Returns a reference to the NodeMap of the last but one nodes of the
2.93 + ///shortest paths.
2.94 + ///\pre \ref run() must be called before using this function.
2.95 const PredNodeMap &predNodeMap() const { return pred_node;}
2.96
2.97 // bool reached(Node v) { return reach[v]; }
2.98 - ///\warning \c s is not reached!
2.99 +
2.100 + ///Chech if a node is reachable from \c s.
2.101 +
2.102 + ///Returns \c true if \c v is reachable from \c s.
2.103 + ///\warning \c s is reported to be unreached!
2.104 + ///\todo Is this what we want?
2.105 + ///\pre \ref run() must be called before using this function.
2.106 ///
2.107 bool reached(Node v) { return G.valid(predecessor[v]); }
2.108
2.109 };
2.110
2.111
2.112 - // IMPLEMENTATIONS
2.113 + // **********************************************************************
2.114 + // IMPLEMENTATIONS
2.115 + // **********************************************************************
2.116
2.117 + ///Runs Dijkstra algorithm from node \c s.
2.118 +
2.119 + ///This method runs the Dijkstra algorithm from node \c s in order to
2.120 + ///compute the
2.121 + ///shortest path to each node. The algorithm computes
2.122 + ///- The shortest path tree.
2.123 + ///- The distance of each node.
2.124 template <typename Graph, typename LengthMap, typename Heap >
2.125 void Dijkstra<Graph,LengthMap,Heap>::run(Node s) {
2.126
2.127 NodeIt u;
2.128 for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
2.129 predecessor.set(u,INVALID);
2.130 + pred_node.set(u,INVALID);
2.131 // If a node is unreacheable, then why should be the dist=0?
2.132 // distance.set(u,0);
2.133 // reach.set(u,false);
3.1 --- a/src/work/alpar/dijkstra/fib_heap.h Sun Mar 21 14:58:48 2004 +0000
3.2 +++ b/src/work/alpar/dijkstra/fib_heap.h Sun Mar 21 14:59:51 2004 +0000
3.3 @@ -57,11 +57,11 @@
3.4
3.5 namespace hugo {
3.6
3.7 + /// A Fibonacci Heap implementation.
3.8 template <typename Item, typename Prio, typename ItemIntMap,
3.9 - typename Compare = std::less<Prio> >
3.10 -
3.11 + typename Compare = std::less<Prio> >
3.12 class FibHeap {
3.13 -
3.14 +
3.15 typedef Prio PrioType;
3.16
3.17 class store;