SPLZ is a fast algorithm for single source shortest path problem on large-scale road network
This program is an implement of SPLZ algorithm. It consist of three parts:
1). Graph partitioning.
2). Compressing the all-pair shortest path of a road network.
3). Decompressing a particular shortest path tree.
These three parts are included in one Visual Studio 2010 solution. It is easy to build. Partition and compression are parallelized with OpenMP. So a multi-core environment is better.
The benchmark we used is downloaded from http://www.dis.uniroma1.it/challenge9/download.shtml The graph file format is .gr, and the coordinate file format is .co. We would not recommend to use SPLZ on a graph with more than one million vertices. It needs too much time to pre-computing, unless you have a high performance workstation.
Note:
1.You must input all the parameters mentioned below.
2.Examples of commands are included in ~\x64\Release\
1).partition SPLZ_partition.exe gr_in co_in C len-to-dict regions_out
gr_in: the graph file to be partitioned.
co_in: the coordinate file of graph
C: the parameter that determine how many regions the graph will be partitioned into.
(recommand value of C: 1, 2, 4, 8)
len-to-dict: the parameter that can control the compression ratio and decompression speed.
lower len-to-dict leads to higher compression ratio and lower decompression speed.
regions_out: a file that records the result of partitioning.
2). compress SPLZ_compress.exe gr_in regions_in dir_out
gr_in: the graph to be calculated and compressed.
regions_in: the file generated by partitioning.
dir_out: the directory that stores the result of compressing.
3). decompress
Decompression part is just a demo for testing the performance of SPLZ.
It don't have commandline parameter.
In fact, all parameters are written in the code.
You can modify them and rebuild.
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent