18 |
18 |
19 #include <lemon/concepts/digraph.h> |
19 #include <lemon/concepts/digraph.h> |
20 #include <lemon/smart_graph.h> |
20 #include <lemon/smart_graph.h> |
21 #include <lemon/list_graph.h> |
21 #include <lemon/list_graph.h> |
22 #include <lemon/lgf_reader.h> |
22 #include <lemon/lgf_reader.h> |
23 |
|
24 #include <lemon/dijkstra.h> |
23 #include <lemon/dijkstra.h> |
25 #include <lemon/path.h> |
24 #include <lemon/path.h> |
26 |
25 |
27 #include "graph_test.h" |
26 #include "graph_test.h" |
28 #include "test_tools.h" |
27 #include "test_tools.h" |
74 l = dijkstra_test.dist(n); |
72 l = dijkstra_test.dist(n); |
75 e = dijkstra_test.predArc(n); |
73 e = dijkstra_test.predArc(n); |
76 n = dijkstra_test.predNode(n); |
74 n = dijkstra_test.predNode(n); |
77 d = dijkstra_test.distMap(); |
75 d = dijkstra_test.distMap(); |
78 p = dijkstra_test.predMap(); |
76 p = dijkstra_test.predMap(); |
79 // pn = dijkstra_test.predNodeMap(); |
|
80 b = dijkstra_test.reached(n); |
77 b = dijkstra_test.reached(n); |
81 |
78 |
82 Path<Digraph> pp = dijkstra_test.path(n); |
79 Path<Digraph> pp = dijkstra_test.path(n); |
83 } |
80 } |
84 |
81 |
89 typedef Digraph::Arc Arc; |
86 typedef Digraph::Arc Arc; |
90 typedef Digraph::Node Node; |
87 typedef Digraph::Node Node; |
91 typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap; |
88 typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap; |
92 |
89 |
93 Digraph g; |
90 Digraph g; |
94 dijkstra(g,LengthMap(),Node()).run(); |
91 bool b; |
95 dijkstra(g,LengthMap()).source(Node()).run(); |
92 dijkstra(g,LengthMap()).run(Node()); |
|
93 b=dijkstra(g,LengthMap()).run(Node(),Node()); |
96 dijkstra(g,LengthMap()) |
94 dijkstra(g,LengthMap()) |
97 .predMap(concepts::WriteMap<Node,Arc>()) |
95 .predMap(concepts::ReadWriteMap<Node,Arc>()) |
98 .distMap(concepts::WriteMap<Node,VType>()) |
96 .distMap(concepts::ReadWriteMap<Node,VType>()) |
|
97 .processedMap(concepts::WriteMap<Node,bool>()) |
99 .run(Node()); |
98 .run(Node()); |
|
99 b=dijkstra(g,LengthMap()) |
|
100 .predMap(concepts::ReadWriteMap<Node,Arc>()) |
|
101 .distMap(concepts::ReadWriteMap<Node,VType>()) |
|
102 .processedMap(concepts::WriteMap<Node,bool>()) |
|
103 .path(concepts::Path<Digraph>()) |
|
104 .dist(VType()) |
|
105 .run(Node(),Node()); |
100 } |
106 } |
101 |
107 |
102 template <class Digraph> |
108 template <class Digraph> |
103 void checkDijkstra() { |
109 void checkDijkstra() { |
104 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
110 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
120 dijkstra_test.run(s); |
126 dijkstra_test.run(s); |
121 |
127 |
122 check(dijkstra_test.dist(t)==3,"Dijkstra found a wrong path."); |
128 check(dijkstra_test.dist(t)==3,"Dijkstra found a wrong path."); |
123 |
129 |
124 Path<Digraph> p = dijkstra_test.path(t); |
130 Path<Digraph> p = dijkstra_test.path(t); |
125 check(p.length()==3,"getPath() found a wrong path."); |
131 check(p.length()==3,"path() found a wrong path."); |
126 check(checkPath(G, p),"path() found a wrong path."); |
132 check(checkPath(G, p),"path() found a wrong path."); |
127 check(pathSource(G, p) == s,"path() found a wrong path."); |
133 check(pathSource(G, p) == s,"path() found a wrong path."); |
128 check(pathTarget(G, p) == t,"path() found a wrong path."); |
134 check(pathTarget(G, p) == t,"path() found a wrong path."); |
129 |
135 |
130 for(ArcIt e(G); e!=INVALID; ++e) { |
136 for(ArcIt e(G); e!=INVALID; ++e) { |
131 Node u=G.source(e); |
137 Node u=G.source(e); |
132 Node v=G.target(e); |
138 Node v=G.target(e); |
133 check( !dijkstra_test.reached(u) || |
139 check( !dijkstra_test.reached(u) || |
134 (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= length[e]), |
140 (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= length[e]), |
135 "dist(target)-dist(source)-arc_length= " << |
141 "Wrong output. dist(target)-dist(source)-arc_length=" << |
136 dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]); |
142 dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]); |
137 } |
143 } |
138 |
144 |
139 for(NodeIt v(G); v!=INVALID; ++v) { |
145 for(NodeIt v(G); v!=INVALID; ++v) { |
140 if (dijkstra_test.reached(v)) { |
146 if (dijkstra_test.reached(v)) { |