Editorial/Data Protection
High Performance
Although the package is written in the Mathematica language, it shows a very good performance, because all time consuming functions are compiled and only those features of Mathematica are used that are inherently fast.

Care was taken for example to avoid list operations that affect the size of a list, like appending. Instead, fields of constant lengths and indices are used.

For all algorithms the dependance of the calculation time on the size of the problem was investigated and is shown in plots in the reference manual of the package. By means of this information, users can estimate in advance how long their own problems will be processed and what problem sizes can be calculated in practice with a specific algorithm.

Some available implementations and typical calclation times in seconds of the comfortable interface for complete graphs with 50 and 200 vertices (40,000 edges) are sumarized in the next table. The timings include all automatic consistency checks and were obtained on a computer with a Pentium 4 running at 1.6 GHz with 800 MHz Rambus memory.

Algorithm    50  200
Minimum Spanning Tree    0.453  5.437
Shortest Path    0.532  6.312
Traveling Salesman    0.875  17.203
Chinese Postman    0.640  5.141
Maximum Flow    0.953  28.329
Minimum Cost Flow    0.719  30.734
Bipartite Matching    0.312  4.204
General Matching    0.312  4.500

The table below shows the dependance on the vertex count of the algorithm of Dijkstra to get the shortest paths in a graph without negative weighted edges.

Vertices Calculation Time [s]
30 0.250
60 0.688
90 1.375
120 2.359
150 3.593
180 5.094
210 6.937
240 9.078
270 11.328
300 13.640
Editorial/Data Protection • page checked on Sep. 27th 2005