Download Latest Version tway-0.2.2.tar.gz (13.8 kB)
Email in envelope

Get an email when there's a new version of tway

Home / 0.2.1
Name Modified Size InfoDownloads / Week
Parent folder
tway-0.2.1.tar.gz 2012-06-21 13.4 kB
tway-0.2.1.tar.bz2 2012-06-21 13.4 kB
README 2012-06-21 1.6 kB
Totals: 3 Items   28.4 kB 0
Tway: Two-way astar and more
============================

This currently implements two-way astar search. You need to have boost , 
Note: I have updated for Boost 1.47 for fedora 16.
Note that older versions of boost require older releases.


Compile:
=======

To compile ion linux, just type make in src directory
$ make
$make test

test_tway : test program for two-way astar
test_tway : test program for regular boost astar, used for benchmarking.

Syntax
======
Interactive version:
$ ./test_tway GRAPHFILE COORDSFILE 
QueryFile Version:
$ ./test_tway GRAPHFILE COORDSFILE QUERYFILE
Command Line Version:
$ ./test_tway GRAPHFILE COORDSFILE SOURCE TARGET

where

GRAPHFILE : dimacs format Graph File, see data/sample.gr
COORDSFILE : dimacs format Graph File, see data/sample.gr
QUERYFILE : Dimacs p2p Query File, see data/sample.p2p

You can find more details on dimacs format at http://www.dis.uniroma1.it/~challenge9/

Test Data and Benchmarking
==========================

You can find several data files on http://www.dis.uniroma1.it/~challenge9/download.shtml

For example to use data for NY city

http://www.dis.uniroma1.it/~challenge9/data/USA-road-d/USA-road-d.NY.gr.gz
http://www.dis.uniroma1.it/~challenge9/data/USA-road-d/USA-road-d.NY.co.gz

You can use tools/generate_problem.sh to generate a sample test file 
generate_problem.sh 264346 100 > USA-road-d.NY.test.p2p


./test_astar USA-road-d.NY.gr USA-road-d.NY.co USA-road-d.NY.test.p2p
./test_tway USA-road-d.NY.gr USA-road-d.NY.co USA-road-d.NY.test.p2p


On my machine, the above takes 36 (+1) ms for astar , 27 (+1) ms for tway

Have Fun,
SRC
Source: README, updated 2012-06-21