|
The experiments (running times in seconds)
were made using a Sun UltraSPARC IIi 440 Mhz with 256 MBytes running
Solaris 2.7 with gcc-3.0.3.
An ak(i)-network consists of 4i + 6 nodes and 6i
+ 7 edges. For a network of n nodes and m edges, the space requirement
is 12n + 11m words for the L E D A graph, 5n + 5m words for the static
bidirectional graph, and 5n +4m words for the static opposite graph.
For an ak(40.000)-network the L E D A graph uses 17.396 MBytes, the
static bidirectional graph 7.630 MBytes and the static opposite
graph 6.714 MBytes. We also tested several graph implementations
of other packages but did not find a single one beating the running
time of our static graph.
| Generator:
ak(n) |
5.000 |
10.000 |
15.000 |
20.000 |
25.000 |
30.000 |
35.000 |
40.000 |
|
| external
arrays |
|
|
|
|
|
|
|
|
| L E D A Graph
|
7.57 |
31.58 |
72.50 |
130.40 |
236.44 |
304.93 |
464.06 |
591.17 |
| static
bidirectional graph |
7.46 |
30.18 |
67.09 |
122.65 |
191.80 |
281.91 |
378.39 |
525.70 |
| static
opposite graph |
6.76 |
27.14 |
60.69 |
110.99 |
174.58 |
256.99 |
350.43 |
454.64 |
|
| dynamic
slot assignment |
|
|
|
|
|
|
|
|
| L E D A Graph
|
6.42 |
27.14 |
70.93 |
134.70 |
184.67 |
291.40 |
475.26 |
580.04 |
| static
bidirectional graph |
5.66 |
22.58 |
51.27 |
107.10 |
149.26 |
204.99 |
284.35 |
427.77 |
| static
opposite graph |
5.35 |
21.17 |
50.01 |
90.01 |
143.92 |
204.21 |
275.38 |
364.50 |
|
| static
slot assignment |
|
|
|
|
|
|
|
|
| L E D A Graph
|
3.66 |
15.38 |
48.16 |
94.75 |
117.38 |
205.68 |
382.37 |
435.24 |
| static
bidirectional graph |
2.29 |
9.28 |
21.28 |
48.94 |
58.35 |
85.38 |
118.00 |
196.80 |
| static
opposite graph |
2.30 |
9.30 |
22.12 |
38.49 |
67.05 |
85.39 |
113.06 |
150.64 |
|