Users guide: pgr_pastar - pgRouting/pgrouting GitHub Wiki
pgr_pastar
Overview
pgRouting has been working towards providing routing functionality on a PostGis/PostgreSql Geo spatial database. It already has support for shortest path algorithm like astar ,dijkstra , tdsp and trsp .But for a very large network there are memory constraints . Network partitioning is one such way which can prove to be helpful in improving the overall memory and time efficiency of routing querries. The main idea here is to first partition the whole network using a Quad tree approach and when the shortest path is computed these partitions are loaded on demand. hence , there is an on demand incremental graph generation while the shortest path is being computed.
How Does It Work?
There are two major components of my idea .
1. Network Partitioning
- For this part we are using a quad tree approach. Say , we start with a square and a condition like maximum number of nodes that can reside in a square . if the number of nodes in the square is greater than the max condition we further quarter it into four squares and allot the nodes appropriately to each of them.All these squares can be called grids and they all will be addressed uniquely using a grid cell number .Each node will be assigned a grid cell number based on the grid they are lying inside.
2. On demand graph generation and Routing.
- The user provides the source and destination node and their partition id's initially . The edges corresponding to these partition ids are first loaded and path computation starts using astar algorithm. These are the edges that will get appended to the present graph and the graph keeps growing dynamically this way.Suppose the algorithm explores a new node and the partition in which this node is lying is not loaded , then we fetch the edges belonging to this partition and append them to the existing graph. We maintain a record of all the partitions that have been loaded.
Where can I get the code?
In general you should be familiar with pgRouting v2.0.0 that can be found at the following link. The astar partition code can be found in the source repository under branch "gsoc-partition". For a more accurate description of building and installing pgRouting use the link below.
Or you can get it out of git source repository and build and install it with:
git clone https://github.com/pgRouting/pgrouting.git
cd pgrouting
git checkout gsoc-partition
mkdir build
cd build
cmake -DWITH_DOC=NO ..
make && make install
cd ..
How do I install and create a database?
The following commands will work from the command line or you can use pgadmin3 and perform the equivalent operations.
createdb -U postgres -h localhost mytest_partition
psql -U postgres -h localhost mytest_partition
create extension postgis;
create extension pgrouting;
\q
You can test it with the following commands:
psql -U postgres -h localhost mytest_partition
\i src/partition/test/partition-test-01.data
\i src/partition/test/partition-test-01.test
\q
How do I setup the tables?
Two tables need to be passed as input parameter. They are edges table and vertex table.
vertex table:
This is a relatively simple table consisting information about all the nodes that are present in the network.This table contains three attributes:
- id : A unique identifier.
- geom geometry .
- quadkey text.
Edge table:
Initially this table will contain only four attributes but we will need more attributes and they need to be generated automatically and manually as well ( explained later):
- id: A unique identifier of the order.
- source : Node id of the source vertex
- target : Node id of the target vertex
- cost : cost to traverse the edge from source to target.
- reverse_cost : cost to traverse the edge from target to source.
How do I partition the network ??
To partition the network we use the function :
pgr_partitionnodes(vtab text, etab text, maxnodes integer)
- vtab : vertex table
- etab :edge table.
- maxnodes : maximum number of nodes allowed in a single partition.
This function will generate partiton id for all the nodes and it will add two attributes to the edge table :
- s_pid : partition id of source vertex.
- t_pid :parttion id of target vertex.
So you need to just call this function with appropriate parameters.
Other attributes of edge table .
These are the coordinates of source vertex and target vertex.
- x1 : x coordinate of source vertex.
- y1 : y coordinate of source vertex.
- x2 : x coordinate of target vertex.
- y2 : y coordinate of target vertex.
the following command adds an attribute to the table.
alter table edge_table_name add column x1 float8;
\\ we need to add other attributes similarly.
To set the values of these attributes we need to run some very basic database querries.
update edge_table_name set x1=st_x(vertex_table_name.the_geom), y1=st_y(vertex_table_name.the_geom) from vertex_table_name where edge_table_name.source=vertex_table_name.id;
update edge_table_name set x2=st_x(vertex_table_name.the_geom), y2=st_y(vertex_table_name.the_geom) from vertex_table_name where edge_table_name.target=vertex_table_name.id;
Now the basic set up is now complete . We can now run the path computation querry .
How do i compute path ??
Once the tables are set one can solve the problem by calling the pg function pgr_pastar with the following input parameters:
pgr_pastar(tab text, snid integer, spid integer, tnid integer, tpid integer, has_rcost boolean DEFAULT false)
where ,
tab : edge_table_name
snid : node id of the source
spid : partition id of the source
tnid :node id of destination
tpid : parttion id of destination node
has_rcost : if true, the reverse_cost column of the SQL generated set of rows will be used for the cost of the traversal of the edge in the opposite direction.
Example
The querry will look something like this
select * from pgr_pastar(edge_table_name, 23, 1111, 45 ,3333,false); // just for example
It will return set of pgr_costResult[]:
-seq: row sequence
-id1: node ID
-id2: edge ID (-1 for the last row)
-cost: cost to traverse from id1 using id2