r420:cb5f50e6c78b
Mon, 01 Dec 2008 14:48:26
[Not Reviewed]
0 comments (0 inline)
0
2
0
| ... | ... |
@@ -33,71 +33,48 @@ |
| 33 | 33 |
#include <lemon/path.h> |
| 34 | 34 |
|
| 35 | 35 |
namespace lemon {
|
| 36 | 36 |
|
| 37 | 37 |
/// \brief Default operation traits for the Dijkstra algorithm class. |
| 38 | 38 |
/// |
| 39 | 39 |
/// This operation traits class defines all computational operations and |
| 40 | 40 |
/// constants which are used in the Dijkstra algorithm. |
| 41 | 41 |
template <typename Value> |
| 42 | 42 |
struct DijkstraDefaultOperationTraits {
|
| 43 | 43 |
/// \brief Gives back the zero value of the type. |
| 44 | 44 |
static Value zero() {
|
| 45 | 45 |
return static_cast<Value>(0); |
| 46 | 46 |
} |
| 47 | 47 |
/// \brief Gives back the sum of the given two elements. |
| 48 | 48 |
static Value plus(const Value& left, const Value& right) {
|
| 49 | 49 |
return left + right; |
| 50 | 50 |
} |
| 51 | 51 |
/// \brief Gives back true only if the first value is less than the second. |
| 52 | 52 |
static bool less(const Value& left, const Value& right) {
|
| 53 | 53 |
return left < right; |
| 54 | 54 |
} |
| 55 | 55 |
}; |
| 56 | 56 |
|
| 57 |
/// \brief Widest path operation traits for the Dijkstra algorithm class. |
|
| 58 |
/// |
|
| 59 |
/// This operation traits class defines all computational operations and |
|
| 60 |
/// constants which are used in the Dijkstra algorithm for widest path |
|
| 61 |
/// computation. |
|
| 62 |
/// |
|
| 63 |
/// \see DijkstraDefaultOperationTraits |
|
| 64 |
template <typename Value> |
|
| 65 |
struct DijkstraWidestPathOperationTraits {
|
|
| 66 |
/// \brief Gives back the maximum value of the type. |
|
| 67 |
static Value zero() {
|
|
| 68 |
return std::numeric_limits<Value>::max(); |
|
| 69 |
} |
|
| 70 |
/// \brief Gives back the minimum of the given two elements. |
|
| 71 |
static Value plus(const Value& left, const Value& right) {
|
|
| 72 |
return std::min(left, right); |
|
| 73 |
} |
|
| 74 |
/// \brief Gives back true only if the first value is less than the second. |
|
| 75 |
static bool less(const Value& left, const Value& right) {
|
|
| 76 |
return left < right; |
|
| 77 |
} |
|
| 78 |
}; |
|
| 79 |
|
|
| 80 | 57 |
///Default traits class of Dijkstra class. |
| 81 | 58 |
|
| 82 | 59 |
///Default traits class of Dijkstra class. |
| 83 | 60 |
///\tparam GR The type of the digraph. |
| 84 | 61 |
///\tparam LM The type of the length map. |
| 85 | 62 |
template<class GR, class LM> |
| 86 | 63 |
struct DijkstraDefaultTraits |
| 87 | 64 |
{
|
| 88 | 65 |
///The type of the digraph the algorithm runs on. |
| 89 | 66 |
typedef GR Digraph; |
| 90 | 67 |
|
| 91 | 68 |
///The type of the map that stores the arc lengths. |
| 92 | 69 |
|
| 93 | 70 |
///The type of the map that stores the arc lengths. |
| 94 | 71 |
///It must meet the \ref concepts::ReadMap "ReadMap" concept. |
| 95 | 72 |
typedef LM LengthMap; |
| 96 | 73 |
///The type of the length of the arcs. |
| 97 | 74 |
typedef typename LM::Value Value; |
| 98 | 75 |
|
| 99 | 76 |
/// Operation traits for Dijkstra algorithm. |
| 100 | 77 |
|
| 101 | 78 |
/// This class defines the operations that are used in the algorithm. |
| 102 | 79 |
/// \see DijkstraDefaultOperationTraits |
| 103 | 80 |
typedef DijkstraDefaultOperationTraits<Value> OperationTraits; |
| ... | ... |
@@ -68,49 +68,49 @@ |
| 68 | 68 |
DType::PredMap p(G); |
| 69 | 69 |
LengthMap length; |
| 70 | 70 |
Path<Digraph> pp; |
| 71 | 71 |
|
| 72 | 72 |
{
|
| 73 | 73 |
DType dijkstra_test(G,length); |
| 74 | 74 |
|
| 75 | 75 |
dijkstra_test.run(s); |
| 76 | 76 |
dijkstra_test.run(s,t); |
| 77 | 77 |
|
| 78 | 78 |
l = dijkstra_test.dist(t); |
| 79 | 79 |
e = dijkstra_test.predArc(t); |
| 80 | 80 |
s = dijkstra_test.predNode(t); |
| 81 | 81 |
b = dijkstra_test.reached(t); |
| 82 | 82 |
d = dijkstra_test.distMap(); |
| 83 | 83 |
p = dijkstra_test.predMap(); |
| 84 | 84 |
pp = dijkstra_test.path(t); |
| 85 | 85 |
} |
| 86 | 86 |
{
|
| 87 | 87 |
DType |
| 88 | 88 |
::SetPredMap<concepts::ReadWriteMap<Node,Arc> > |
| 89 | 89 |
::SetDistMap<concepts::ReadWriteMap<Node,VType> > |
| 90 | 90 |
::SetProcessedMap<concepts::WriteMap<Node,bool> > |
| 91 | 91 |
::SetStandardProcessedMap |
| 92 |
::SetOperationTraits< |
|
| 92 |
::SetOperationTraits<DijkstraDefaultOperationTraits<VType> > |
|
| 93 | 93 |
::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > > |
| 94 | 94 |
::SetStandardHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > > |
| 95 | 95 |
::Create dijkstra_test(G,length); |
| 96 | 96 |
|
| 97 | 97 |
dijkstra_test.run(s); |
| 98 | 98 |
dijkstra_test.run(s,t); |
| 99 | 99 |
|
| 100 | 100 |
l = dijkstra_test.dist(t); |
| 101 | 101 |
e = dijkstra_test.predArc(t); |
| 102 | 102 |
s = dijkstra_test.predNode(t); |
| 103 | 103 |
b = dijkstra_test.reached(t); |
| 104 | 104 |
pp = dijkstra_test.path(t); |
| 105 | 105 |
} |
| 106 | 106 |
|
| 107 | 107 |
} |
| 108 | 108 |
|
| 109 | 109 |
void checkDijkstraFunctionCompile() |
| 110 | 110 |
{
|
| 111 | 111 |
typedef int VType; |
| 112 | 112 |
typedef concepts::Digraph Digraph; |
| 113 | 113 |
typedef Digraph::Arc Arc; |
| 114 | 114 |
typedef Digraph::Node Node; |
| 115 | 115 |
typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap; |
| 116 | 116 |
|
0 comments (0 inline)