P2P Shortest Path: A-Star vs. Dijkstra

The following code is part of a research project in artificial intelligence at the University of British Columbia. The code and research was done by me and Michael Henderson. The sources can be downloaded here and the final project report in PDF can be downloaded here. For any questions contact me. Below is the content of the README file:

1. INTRODUCTION

aip2p is a program to compare the A-star search algorithm with the Dijkstra
search algorithm with the Dijkstra search algorithm on different kind of
graphs with different configurations. The graphs itself can be generated by
aip2p too. They are stored in a file in DIMACS format.


2. REQUIREMENTS

The source code compiles on Windows and on Linux. However, for the graph
generation scripts, a bash shell is needed. For the DNA search, gawk is
needed.

Linux:
No special requirements needed.

Windows:
dynamic_cast requires the Run-Time Type Information (RTTI) to keep track of
dynamic types. Some compilers include this feature as an option which is
disabled by default. This feature must be enabled for runtime type checking
using dynamic_cast.

GCC 4.0.3 does have RTTI enabled by default.


3. COMPILATION

Linux:
Go into the directory with the Makefile and the src and include directories
and type:

make

This creates you a directory called Release which contains the binary aip2p.
To clean up after usage, on might type:

make clean


4. USAGE

We wrote several bash script files to use aip2p to generate automatically
huge number of graphs and run a lot of tests. Following the explanation
to the scripts:

compare_dna.sh
Parses a file containing DNA sequences in raw format from the European 
Institute of Bioinformatics and compares the first pairs of sequences
100 characters of subsequent pairs of sequences.

create_graphs.sh
Creates different types of graphs with different kind of configurations.

search_graphs.sh
Runs a search on graphs in a directory or in the current directory and
compares the efficeny of A* and Dijkstra's.

The aip2p binary itself can be used in the following way (this is the
output if one types aip2p -h or aip2p --help):


localhost:~$ aip2p --help

Usage: aip2p [OPTIONS] [FILE]
Performs an A* and a Dijkstra search on a graph or
creates a new random, geometric or grid graph.

Search options

  -i, --iterations        perform search  times
  -s, --start             starting node, -1 means: choose randomly
  -g, --goal              goal node, -1 means: choose randomly

String edit distance search

  -d, --distance               perform string edit distance search
  -s, --start "string1"      first string sequence
  -g, --goal "string2"       second string sequence

Create options

  -t, --type           graph type: rand, geom, grid, str_edit

Create options for random and geometric graphs

  -n, --nodes             create a graph with  nodes
  -e, --edge-factor     rand: probability factor 0-1,
                               geom: distance factor 0-100

Create options for grid graphs

  -r, --rows              number of rows, even
  -c, --columns           number of columns, even

The output of a search is a line of the following format:

S,type,prop,size,exp,path,length,time

where S is search type (A = A-Star, D = Dijkstra), type is the graph type
(rand, geom, grid), properties is the edge factor for rand and geom graphs
and the row x cols dimension for a grid. size is the number of nodes in the
graph, exp is the number of nodes expanded and path is the number of nodes
in the shortes path. time is clock ticks the search needed on the system.

Valentin Koch