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.