Changeset 1194:7bce0ef61d6b in lemon0.x for src/test/dijkstra_heap_test.cc
 Timestamp:
 03/04/05 18:20:11 (19 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1606
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/test/dijkstra_heap_test.cc
r1164 r1194 32 32 33 33 #include <lemon/smart_graph.h> 34 35 #include <lemon/graph_writer.h> 36 #include <lemon/map_utils.h> 37 38 34 39 #include <lemon/dimacs.h> 35 40 #include <lemon/dijkstra.h> 36 41 #include <lemon/time_measure.h> 42 #include <lemon/graph_utils.h> 43 37 44 #include <lemon/bin_heap.h> 38 45 #include <lemon/fib_heap.h> 46 #include <lemon/radix_heap.h> 39 47 40 48 using namespace lemon; 41 49 42 int main(int, char **) { 43 44 typedef SmartGraph Graph; 45 46 typedef Graph::Edge Edge; 47 typedef Graph::Node Node; 48 typedef Graph::EdgeIt EdgeIt; 49 typedef Graph::NodeIt NodeIt; 50 typedef Graph::template EdgeMap<int> LengthMap; 51 52 Graph G; 50 typedef ListGraph Graph; 51 52 typedef Graph::Edge Edge; 53 typedef Graph::Node Node; 54 typedef Graph::EdgeIt EdgeIt; 55 typedef Graph::NodeIt NodeIt; 56 typedef Graph::EdgeMap<int> LengthMap; 57 58 59 struct FibTraits : public DijkstraDefaultTraits<Graph, LengthMap> { 60 typedef FibHeap<Graph::Node, LengthMap::Value, Graph::NodeMap<int> > Heap; 61 }; 62 63 struct RadixTraits : public DijkstraDefaultTraits<Graph, LengthMap> { 64 typedef RadixHeap<Graph::Node, Graph::NodeMap<int> > Heap; 65 }; 66 67 68 int main(int argc, const char* argv[]) { 69 70 71 Graph graph; 53 72 Node s, t; 54 LengthMap cap( G);55 readDimacs MaxFlow(std::cin, G, s, t, cap);73 LengthMap cap(graph); 74 readDimacs(std::cin, graph, cap, s, t); 56 75 Timer ts; 76 77 GraphWriter<Graph> writer(std::cout, graph); 78 79 IdMap<Graph, Node> nodeIdMap(graph); 80 writer.addNodeMap("id", nodeIdMap); 81 82 IdMap<Graph, Edge> edgeIdMap(graph); 83 writer.addEdgeMap("id", edgeIdMap); 84 85 writer.addEdgeMap("cap", cap); 86 87 writer.run(); 57 88 58 89 std::cout << … … 60 91 <<std::endl; 61 92 std::cout<<" on a graph with " << 62 G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."93 countNodes(graph) << " nodes and " << countEdges(graph) << " edges..." 63 94 << std::endl<<std::endl; 64 95 96 65 97 Dijkstra<Graph, LengthMap> 66 dijkstra_test( G, cap);98 dijkstra_test(graph, cap); 67 99 ts.reset(); 68 dijkstra_test.run(s);100 dijkstra_test.run(s); 69 101 std::cout << "elapsed time: " << ts << std::endl; 70 102 71 103 int error1=0; 72 104 int error2=0; 73 105 74 for(EdgeIt e( G); e!=INVALID; ++e) {75 Node u= G.source(e);76 Node v= G.target(e);106 for(EdgeIt e(graph); e!=INVALID; ++e) { 107 Node u=graph.source(e); 108 Node v=graph.target(e); 77 109 if ( dijkstra_test.dist(v)  dijkstra_test.dist(u) > cap[e] ) 78 110 if ( dijkstra_test.reached(u) ) { … … 85 117 86 118 NodeIt v; 87 for(NodeIt v( G); v!=INVALID; ++v) {119 for(NodeIt v(graph); v!=INVALID; ++v) { 88 120 if ( dijkstra_test.reached(v) ) { 89 121 Edge e=dijkstra_test.pred(v); 90 Node u= G.source(e);122 Node u=graph.source(e); 91 123 if ( dijkstra_test.dist(v)  dijkstra_test.dist(u) != cap[e] ) { 92 124 std::cout<<"Error in a shortest path tree edge! Difference: " … … 109 141 <<std::endl; 110 142 std::cout<<" on a graph with " << 111 G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."143 countNodes(graph) << " nodes and " << countEdges(graph) << " edges..." 112 144 << std::endl<<std::endl; 113 145 114 Dijkstra<Graph, LengthMap, FibHeap> 115 dijkstra_test2(G, cap); 146 147 Dijkstra<Graph, LengthMap, FibTraits> 148 dijkstra_test2(graph, cap); 116 149 ts.reset(); 117 150 dijkstra_test2.run(s); … … 121 154 error2=0; 122 155 123 for(EdgeIt e( G); e!=INVALID; ++e) {124 Node u= G.source(e);125 Node v= G.target(e);156 for(EdgeIt e(graph); e!=INVALID; ++e) { 157 Node u=graph.source(e); 158 Node v=graph.target(e); 126 159 if ( dijkstra_test2.dist(v)  dijkstra_test2.dist(u) > cap[e] ) 127 160 if ( dijkstra_test2.reached(u) ) { … … 133 166 } 134 167 135 for(NodeIt n( G); v!=INVALID; ++v) {168 for(NodeIt n(graph); v!=INVALID; ++v) { 136 169 if ( dijkstra_test2.reached(v) ) { 137 170 Edge e=dijkstra_test2.pred(v); 138 Node u= G.source(e);171 Node u=graph.source(e); 139 172 if ( dijkstra_test2.dist(v)  dijkstra_test2.dist(u) != cap[e] ) { 140 173 std::cout<<"Error in a shortest path tree edge! Difference: " … … 150 183 << " shortest path tree edge is erroneous."<<std::endl; 151 184 185 std::cout << 186 "\n\n Testing dijkstra.h with Radix heap implementation radix_heap.h," 187 <<std::endl; 188 std::cout<<" on a graph with " << 189 countNodes(graph) << " nodes and " << countEdges(graph) << " edges..." 190 << std::endl<<std::endl; 191 192 193 Dijkstra<Graph, LengthMap, RadixTraits> 194 dijkstra_test3(graph, cap); 195 ts.reset(); 196 dijkstra_test3.run(s); 197 std::cout << "elapsed time: " << ts << std::endl; 198 199 200 error1=0; 201 error2=0; 202 203 for(EdgeIt e(graph); e!=INVALID; ++e) { 204 Node u=graph.source(e); 205 Node v=graph.target(e); 206 if ( dijkstra_test3.dist(v)  dijkstra_test3.dist(u) > cap[e] ) 207 if ( dijkstra_test3.reached(u) ) { 208 std::cout<<"Error! dist(target)dist(source) edge_length= " 209 <<dijkstra_test3.dist(v)  dijkstra_test3.dist(u) 210  cap[e]<<std::endl; 211 ++error1; 212 } 213 } 214 215 for(NodeIt n(graph); v!=INVALID; ++v) { 216 if ( dijkstra_test3.reached(v) ) { 217 Edge e=dijkstra_test3.pred(v); 218 Node u=graph.source(e); 219 if ( dijkstra_test3.dist(v)  dijkstra_test3.dist(u) != cap[e] ) { 220 std::cout<<"Error in a shortest path tree edge! Difference: " 221 <<std::abs(dijkstra_test3.dist(v)  dijkstra_test3.dist(u) 222  cap[e])<<std::endl; 223 ++error2; 224 } 225 } 226 } 227 228 229 std::cout << error1 << " nontree and " << error2 230 << " shortest path tree edge is erroneous."<<std::endl; 152 231 153 232 return 0;
Note: See TracChangeset
for help on using the changeset viewer.