34 |
34 |
35 using namespace lemon; |
35 using namespace lemon; |
36 using namespace std; |
36 using namespace std; |
37 |
37 |
38 int main(int argc, const char *argv[]) { |
38 int main(int argc, const char *argv[]) { |
39 srand(time(0)); |
|
40 typedef SmartGraph Graph; |
39 typedef SmartGraph Graph; |
41 typedef Graph::Node Node; |
40 typedef Graph::Node Node; |
42 typedef Graph::Edge Edge; |
41 typedef Graph::Edge Edge; |
43 typedef Graph::NodeIt NodeIt; |
42 typedef Graph::NodeIt NodeIt; |
44 typedef Graph::EdgeIt EdgeIt; |
43 typedef Graph::EdgeIt EdgeIt; |
45 |
44 |
46 typedef Graph::EdgeMap<double> LengthMap; |
45 typedef Graph::EdgeMap<int> LengthMap; |
47 typedef Graph::NodeMap<double> DistMap; |
46 typedef Graph::NodeMap<int> DistMap; |
48 |
47 |
49 const int n = argc > 1 ? atoi(argv[1]) : 20; |
48 const int n = argc > 1 ? atoi(argv[1]) : 20; |
50 const int e = argc > 2 ? atoi(argv[2]) : (int)(n * log((double)n)); |
49 const int e = argc > 2 ? atoi(argv[2]) : (int)(n * log((double)n)); |
51 const double m = argc > 3 ? (double)atoi(argv[3]) : 100.0; |
50 const int m = argc > 3 ? atoi(argv[3]) : 100; |
52 |
51 |
53 Graph graph; |
52 Graph graph; |
54 LengthMap length(graph); |
53 LengthMap length(graph); |
55 vector<Node> nodes; |
54 vector<Node> nodes; |
56 |
55 |
57 DistMap shift(graph); |
56 DistMap shift(graph); |
58 for (int i = 0; i < n; ++i) { |
57 for (int i = 0; i < n; ++i) { |
59 Node node = graph.addNode(); |
58 Node node = graph.addNode(); |
60 nodes.push_back(node); |
59 nodes.push_back(node); |
61 shift[node] = m * (double)rand() / (RAND_MAX + 1.0); |
60 shift[node] = rnd[m]; |
62 } |
61 } |
63 |
62 |
64 for (int i = 0; i < e; ++i) { |
63 for (int i = 0; i < e; ++i) { |
65 int s = (int)(n * (double)rand() / (RAND_MAX + 1.0)); |
64 int s = rnd[n]; |
66 int t = (int)(n * (double)rand() / (RAND_MAX + 1.0)); |
65 int t = rnd[n]; |
67 double c = m * (double)rand() / (RAND_MAX + 1.0); |
|
68 Edge edge = graph.addEdge(nodes[s], nodes[t]); |
66 Edge edge = graph.addEdge(nodes[s], nodes[t]); |
69 length[edge] = c - shift[nodes[s]] + shift[nodes[t]]; |
67 length[edge] = rnd[m] - shift[nodes[s]] + shift[nodes[t]]; |
70 } |
68 } |
71 |
69 |
72 Johnson<Graph, LengthMap> johnson(graph, length); |
70 Johnson<Graph, LengthMap> johnson(graph, length); |
73 { |
71 { |
74 Timer timer; |
72 Timer timer; |
75 johnson.run(); |
73 johnson.run(); |
76 cout << "Johnson: " << timer << endl; |
74 cout << "Johnson: " << timer << endl; |
77 } |
75 } |
78 |
76 |
79 typedef FibHeap<Node, double, Graph::NodeMap<int> > DoubleFibHeap; |
77 typedef FibHeap<Node, int, Graph::NodeMap<int> > IntFibHeap; |
80 Johnson<Graph, LengthMap>::DefStandardHeap<DoubleFibHeap> |
78 Johnson<Graph, LengthMap>::DefStandardHeap<IntFibHeap> |
81 ::Create fibJohnson(graph, length); |
79 ::Create fibJohnson(graph, length); |
82 { |
80 { |
83 Timer timer; |
81 Timer timer; |
84 fibJohnson.run(); |
82 fibJohnson.run(); |
85 cout << "Johnson with fibonacci heap: " << timer << endl; |
83 cout << "Johnson with fibonacci heap: " << timer << endl; |