63 } |
63 } |
64 } |
64 } |
65 |
65 |
66 |
66 |
67 |
67 |
68 template <typename _Traits, typename _Heap> |
|
69 struct DefHeapTraits : public _Traits { |
|
70 typedef _Heap Heap; |
|
71 }; |
|
72 |
|
73 template <typename _Graph, typename _LengthMap, typename _Heap> |
68 template <typename _Graph, typename _LengthMap, typename _Heap> |
74 void dijkstraHeapTest(_Graph& graph, _LengthMap& length, |
69 void dijkstraHeapTest(_Graph& graph, _LengthMap& length, |
75 typename _Graph::Node& start) { |
70 typename _Graph::Node& start) { |
76 |
71 |
77 typedef _Heap Heap; |
72 typedef _Heap Heap; |
81 typedef typename Graph::Node Node; |
76 typedef typename Graph::Node Node; |
82 typedef typename Graph::Edge Edge; |
77 typedef typename Graph::Edge Edge; |
83 typedef typename Graph::NodeIt NodeIt; |
78 typedef typename Graph::NodeIt NodeIt; |
84 typedef typename Graph::EdgeIt EdgeIt; |
79 typedef typename Graph::EdgeIt EdgeIt; |
85 |
80 |
86 Dijkstra<Graph, LengthMap, |
81 typename Dijkstra<Graph, LengthMap>::template DefHeap<Heap>:: |
87 DefHeapTraits<DijkstraDefaultTraits<Graph, LengthMap>, Heap> > |
82 Create dijkstra(graph, length); |
88 dijkstra(graph, length); |
|
89 |
83 |
90 dijkstra.run(start); |
84 dijkstra.run(start); |
91 |
85 |
92 for(EdgeIt e(graph); e!=INVALID; ++e) { |
86 for(EdgeIt e(graph); e!=INVALID; ++e) { |
93 Node u=graph.source(e); |
87 Node u=graph.source(e); |
94 Node v=graph.target(e); |
88 Node v=graph.target(e); |
95 if (dijkstra.reached(u)) { |
89 if (dijkstra.reached(u)) { |
96 check( dijkstra.dist(v) - dijkstra.dist(u) <= length[e], |
90 check( dijkstra.dist(v) - dijkstra.dist(u) <= length[e], |
97 "Error in a shortest path tree edge!"); |
91 "Error in a shortest path tree edge!"); |
98 } |
92 } |
99 } |
93 } |
100 |
94 |
101 for(NodeIt v(graph); v!=INVALID; ++v) { |
95 for(NodeIt v(graph); v!=INVALID; ++v) { |
102 if ( dijkstra.reached(v) && dijkstra.pred(v) != INVALID ) { |
96 if ( dijkstra.reached(v) && dijkstra.pred(v) != INVALID ) { |