Multilanguage and multiparadigm navigator 1/n Introduction

In this series of post (where n > 1 and probably < 10) we’ll see how to implement a simple “navigator” in different languages.
This was a project I did for my university a long time ago that appeared to me interesting enough to improve it and publish it.
For navigator we mean a program that, given:

a table with distances between cities

a path

It returns the shortest path possible (if there’s one) with the total distance calculated.

The algorithm used is mainly Floyd Warshall which calculates iteratively the nth-distance between couple of cities and creates a table.

After that the only “problem” is building up the path of shortest paths.

The problem has been coded in very different languages (using the specified compiler):

Prolog: swi prolog

lisp: sbcl

Python: python

In plus there is an input generator (still in python), a performance analyzer (in bash + gnuplot) and a nice grapher (in python + pydot) to get a graphical view of the problem’s instances.
In this first chapter we’re just going to briefly analyze the how the input/output are formatted and the general structure of the program.

The full source code (and much more) that I’m going to show can be found (maybe more updated) on my github page navigator .

You can download everything by simply cloning

  git clone git://github.com/AndreaCrotti/navigator.git

We have for example a distance table:

5.AGLIE.AIRASCA.ALA.ALBIANO.ALICE.0.-1.2.1.5.-1.0.-1.7.-1.2.-1.0.-1.-1.1.7.-1.0.7.5.-1.-1.7.0.

Where the first number is the number of cities, then we find the list of cities and then a matrix (written as array) with the distances between them.
For example in this distance table we have:

distance(AGLIE,ALA) = 2

and there is no direct path between (AGLIE, AIRASCA), because as a convention the value “-1″ stands for no direct connection between the two cities.

In another text file we put the path that we need to follow:

ALICE.ALBIANO.ALA.ALBIANO.ALA.

And the output will simply be:

ALICE.AGLIE.ALBIANO.AGLIE.ALA.AGLIE.ALBIANO.AGLIE.ALA
15

So finally the tasks that we have to implement for every language are:

parse the input

run the Floyd Warshall algorithm

build a result and returns it as output

The input and output must be exactly the same for all the different implementations of the program, so we can easily check automatically if there are differences in the solutions proposed.

In the next post we’ll see how the input is generated and what are the criteria to evaluate the complexity of a particular instance.