# HG changeset patch
# User deba
# Date 1109956811 0
# Node ID 7bce0ef61d6b5549aebee3aaef44d7973c2ab42c
# Parent c3585aec8cb3a92e4b191148dc192b9f36e8a267
Change test to be up to date.
Deprecated test, it should be used rather the heap_test.cc and heap_test.h.
diff -r c3585aec8cb3 -r 7bce0ef61d6b src/test/dijkstra_heap_test.cc
--- a/src/test/dijkstra_heap_test.cc Fri Mar 04 17:18:25 2005 +0000
+++ b/src/test/dijkstra_heap_test.cc Fri Mar 04 17:20:11 2005 +0000
@@ -31,49 +31,81 @@
#include <math.h>
#include <lemon/smart_graph.h>
+
+#include <lemon/graph_writer.h>
+#include <lemon/map_utils.h>
+
+
#include <lemon/dimacs.h>
#include <lemon/dijkstra.h>
#include <lemon/time_measure.h>
+#include <lemon/graph_utils.h>
+
#include <lemon/bin_heap.h>
#include <lemon/fib_heap.h>
+#include <lemon/radix_heap.h>
using namespace lemon;
-int main(int, char **) {
+typedef ListGraph Graph;
+
+typedef Graph::Edge Edge;
+typedef Graph::Node Node;
+typedef Graph::EdgeIt EdgeIt;
+typedef Graph::NodeIt NodeIt;
+typedef Graph::EdgeMap<int> LengthMap;
+
+
+struct FibTraits : public DijkstraDefaultTraits<Graph, LengthMap> {
+ typedef FibHeap<Graph::Node, LengthMap::Value, Graph::NodeMap<int> > Heap;
+};
+
+struct RadixTraits : public DijkstraDefaultTraits<Graph, LengthMap> {
+ typedef RadixHeap<Graph::Node, Graph::NodeMap<int> > Heap;
+};
+
+
+int main(int argc, const char* argv[]) {
- typedef SmartGraph Graph;
- typedef Graph::Edge Edge;
- typedef Graph::Node Node;
- typedef Graph::EdgeIt EdgeIt;
- typedef Graph::NodeIt NodeIt;
- typedef Graph::template EdgeMap<int> LengthMap;
+ Graph graph;
+ Node s, t;
+ LengthMap cap(graph);
+ readDimacs(std::cin, graph, cap, s, t);
+ Timer ts;
- Graph G;
- Node s, t;
- LengthMap cap(G);
- readDimacsMaxFlow(std::cin, G, s, t, cap);
- Timer ts;
+ GraphWriter<Graph> writer(std::cout, graph);
+
+ IdMap<Graph, Node> nodeIdMap(graph);
+ writer.addNodeMap("id", nodeIdMap);
+
+ IdMap<Graph, Edge> edgeIdMap(graph);
+ writer.addEdgeMap("id", edgeIdMap);
+
+ writer.addEdgeMap("cap", cap);
+
+ writer.run();
std::cout <<
"\n Testing dijkstra.h with binary heap implementation bin_heap.h,"
<<std::endl;
std::cout<<" on a graph with " <<
- G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
+ countNodes(graph) << " nodes and " << countEdges(graph) << " edges..."
<< std::endl<<std::endl;
-
+
+
Dijkstra<Graph, LengthMap>
- dijkstra_test(G, cap);
+ dijkstra_test(graph, cap);
ts.reset();
- dijkstra_test.run(s);
+ dijkstra_test.run(s);
std::cout << "elapsed time: " << ts << std::endl;
-
+
int error1=0;
int error2=0;
- for(EdgeIt e(G); e!=INVALID; ++e) {
- Node u=G.source(e);
- Node v=G.target(e);
+ for(EdgeIt e(graph); e!=INVALID; ++e) {
+ Node u=graph.source(e);
+ Node v=graph.target(e);
if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) > cap[e] )
if ( dijkstra_test.reached(u) ) {
std::cout<<"Error! dist(target)-dist(source)- edge_length= "
@@ -84,10 +116,10 @@
}
NodeIt v;
- for(NodeIt v(G); v!=INVALID; ++v) {
+ for(NodeIt v(graph); v!=INVALID; ++v) {
if ( dijkstra_test.reached(v) ) {
Edge e=dijkstra_test.pred(v);
- Node u=G.source(e);
+ Node u=graph.source(e);
if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) != cap[e] ) {
std::cout<<"Error in a shortest path tree edge! Difference: "
<<std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u)
@@ -108,11 +140,12 @@
"\n\n Testing dijkstra.h with Fibonacci heap implementation fib_heap.h,"
<<std::endl;
std::cout<<" on a graph with " <<
- G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
+ countNodes(graph) << " nodes and " << countEdges(graph) << " edges..."
<< std::endl<<std::endl;
- Dijkstra<Graph, LengthMap, FibHeap>
- dijkstra_test2(G, cap);
+
+ Dijkstra<Graph, LengthMap, FibTraits>
+ dijkstra_test2(graph, cap);
ts.reset();
dijkstra_test2.run(s);
std::cout << "elapsed time: " << ts << std::endl;
@@ -120,9 +153,9 @@
error1=0;
error2=0;
- for(EdgeIt e(G); e!=INVALID; ++e) {
- Node u=G.source(e);
- Node v=G.target(e);
+ for(EdgeIt e(graph); e!=INVALID; ++e) {
+ Node u=graph.source(e);
+ Node v=graph.target(e);
if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) > cap[e] )
if ( dijkstra_test2.reached(u) ) {
std::cout<<"Error! dist(target)-dist(source)- edge_length= "
@@ -132,10 +165,10 @@
}
}
- for(NodeIt n(G); v!=INVALID; ++v) {
+ for(NodeIt n(graph); v!=INVALID; ++v) {
if ( dijkstra_test2.reached(v) ) {
Edge e=dijkstra_test2.pred(v);
- Node u=G.source(e);
+ Node u=graph.source(e);
if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) != cap[e] ) {
std::cout<<"Error in a shortest path tree edge! Difference: "
<<std::abs(dijkstra_test2.dist(v) - dijkstra_test2.dist(u)
@@ -149,6 +182,52 @@
std::cout << error1 << " non-tree and " << error2
<< " shortest path tree edge is erroneous."<<std::endl;
+ std::cout <<
+ "\n\n Testing dijkstra.h with Radix heap implementation radix_heap.h,"
+ <<std::endl;
+ std::cout<<" on a graph with " <<
+ countNodes(graph) << " nodes and " << countEdges(graph) << " edges..."
+ << std::endl<<std::endl;
+
+
+ Dijkstra<Graph, LengthMap, RadixTraits>
+ dijkstra_test3(graph, cap);
+ ts.reset();
+ dijkstra_test3.run(s);
+ std::cout << "elapsed time: " << ts << std::endl;
+
+
+ error1=0;
+ error2=0;
+
+ for(EdgeIt e(graph); e!=INVALID; ++e) {
+ Node u=graph.source(e);
+ Node v=graph.target(e);
+ if ( dijkstra_test3.dist(v) - dijkstra_test3.dist(u) > cap[e] )
+ if ( dijkstra_test3.reached(u) ) {
+ std::cout<<"Error! dist(target)-dist(source)- edge_length= "
+ <<dijkstra_test3.dist(v) - dijkstra_test3.dist(u)
+ - cap[e]<<std::endl;
+ ++error1;
+ }
+ }
+
+ for(NodeIt n(graph); v!=INVALID; ++v) {
+ if ( dijkstra_test3.reached(v) ) {
+ Edge e=dijkstra_test3.pred(v);
+ Node u=graph.source(e);
+ if ( dijkstra_test3.dist(v) - dijkstra_test3.dist(u) != cap[e] ) {
+ std::cout<<"Error in a shortest path tree edge! Difference: "
+ <<std::abs(dijkstra_test3.dist(v) - dijkstra_test3.dist(u)
+ - cap[e])<<std::endl;
+ ++error2;
+ }
+ }
+ }
+
+
+ std::cout << error1 << " non-tree and " << error2
+ << " shortest path tree edge is erroneous."<<std::endl;
return 0;
}