- Start
- User Group
- Applications
- Functions
- Algorithms
- Interface
- License Model
- Order
- Resources
- Contact
- <
- >

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