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 |
|
