# Shortest Path Search in your Database

### ... and more with pgRouting

Presented by Vicky Vergara

# Celia Virginia Vergara Castillo

• Economist, Computer Scientist
• Work in Georepublic
• pgRouting developer
• Living in Mexico
• Known as Vicky

Please, enjoy FOSS4G Korea!!!

# A Library providing

## Let's Route ...

• Shortest Path Algorithm
• Dijkstra
• A-Star
• Alternative Routes
• Turn Restrictions
• Traveling Salesperson Algorithm
• Drivetime Analysis
• Vehicle Route Problem Solver

## Create a Database

pgRouting extends PostgreSQL/PostGIS


CREATE DATABASE routing;
\c routing
CREATE EXTENSION postgis;
CREATE EXTENSION pgrouting; 

## SQL Query

 SELECT * FROM pgr_dijkstra('
SELECT gid as id,
source,
target,
length as cost
FROM ways',
30, 60, false); 

## Query Result


seq | path_seq | node | edge |  cost  | agg_cost
----+----------+------+------+--------+----------
1 |        1 |   30 |   53 | 0.0591 |        0
2 |        2 |   44 |   52 | 0.0665 |   0.0591
3 |        3 |   14 |   15 | 0.0809 |   0.1256
4 |        4 |   13 |   14 | 0.0726 |   0.2065
5 |        5 |   12 |   13 | 0.0812 |   0.2791
6 |        6 |   11 |   12 | 0.0074 |   0.3603
7 |        7 |   10 | 6869 | 0.0164 |   0.3677
8 |        8 |   59 |   72 | 0.0109 |   0.3841
9 |        9 |   60 |   -1 |      0 |   0.3950
(9 rows) 

## Goals

### developers

• Boost
• Undirected Graph
• Directed Graph
• Internal library

## Goals

### users

• Support for big integer
• Avoid user contradictory input

# An Idea

## Cool code

 void existing_complicated_code() {
A  // 100 lines of code
B  // 500 lines of complicated code with an unsolved issue
C  // 50 more lines of code
} 

## copy / paste

 void new_complicated_code() {
D  // 100 lines of code
// TODO copy/paste 500 lines of existing complicated code
E  // 50 more lines of code
} 

### User contradictory input


select * from pgr_foo(
'select id, source, target, cost, reverse_cost from edges', 3, 5,
false -- directed flag,
false -- has_rcost flag
);


### and


select * from pgr_foo(
'select id, source, target, cost from edges', 3, 5,
false -- directed flag,
true  -- has_rcost flag
);


## Plan

• Precise definition of graphs
• Gradual creation of internal library
• Incremental releases

• INTEGER
• SMALLINT
• BIGINT

• INTEGER
• SMALLINT
• BIGINT
• REAL
• FLOAT

### Weighted Directed Graph

• Let $V$ be a set of vertices
$V = source \cup target \cup \{start_v\} \cup \{end_v\}$
• Let $E$ be a set of edges
• when $reverse\_cost = \varnothing$:
$E = \{ (source_i, target_i, cost_i) | cost_i \geq 0 \}$
• when $reverse\_cost \neq \varnothing$:
$E = \{ (source_i, target_i, cost_i) | cost_i \geq0 \}$
$\cup \quad \{ (target_i, source_i, reverse\_cost_i) | reverse\_cost_i \geq 0)\}$
• $G_d(V,E)$ is a weighted directed graph

### Weighted Directed Graph


source | target | cost | reverse_cost
-------+--------+------+------------
3 |      6 |   40 |   38
3 |      8 |   25 |  -25
6 |      8 |  -1  |   32


### Weighted Undirected Graph

• Let $V$ be a set of vertices
$V = source \cup target \cup \{start_v\} \cup \{end_v\}$
• Let $E$ be a set of edges
• when $reverse\_cost = \varnothing$:
$E = \{ (source_i, target_i, cost_i) | cost_i \geq 0 \}$
$\cup \quad \{ (target_i, source_i, cost_i) | cost_i \geq 0 \}$
• when $reverse\_cost \neq \varnothing$:
$E = \{ (source_i, target_i, cost_i) | cost_i \geq0 \}$
$\cup \quad \{ (target_i, source_i, cost_i) | cost_i \geq 0 \}$
$\cup \quad \{ (target_i, source_i, reverse\_cost_i) | reverse\_cost_i \geq 0)\}$
$\cup \quad \{ (source_i, target_i, reverse\_cost_i) | reverse\_cost_i \geq 0)\}$
• $G_u(V,E)$ is a weighted undirected graph

### Weighted Undirected Graph


source | target | cost | reverse_cost
-------+--------+------+-------------
3 |      6 |   40 |   38
3 |      8 |   25 |  -25
6 |      8 |  -1  |   32


### pgr_Dijkstra

• Given a graph:
$G(V,E) = \begin{cases} G_d(V,E) & \quad \text{when } directed = true\\ G_u(V,E) & \quad \text{when } directed = false\\ \end{cases}$
• and the starting and ending vertices:
$start_v$ and $end_v$
• The algorithm returns a path $\pi$, if it exists, which is the shortest path using Dijsktra algorithm between $start_v$ and $end_v$ in terms of a sequence of vertices and of edges:
$\pi = \{(path\_seq_i, node_i, edge_i, cost_i, agg\_cost_i) | \\ path\_seq_i = i \\ node_1 = start_v \\ \land node_{|\pi|} = end_v \\ \land edge_i = \begin{cases} id(node_i, node_{i+i}, cost_{(node_i, node_{i+i})} ) & \quad \text{when } i \neq |\pi| \\ -1 & \quad \text{when } i = |\pi| \\ \end{cases} \\ \land agg\_cost_i = \sum_{j=1}^{i-1} cost_j \}$
• If there is no path, $\pi = \varnothing$

## pgr_dijkstra

### on undirected graph

#### With reverse cost


SELECT * FROM pgr_Dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edges',
3, -- start_vid
5, -- end_vid
false -- directed flag
);


#### Without reverse cost


SELECT * FROM pgr_Dijkstra(
'SELECT id, source, target, cost FROM edges',
3, 5,
false);


## pgr_dijkstra

### directed graph

#### With reverse cost


SELECT * FROM pgr_Dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edges',
3, 5,
true);


#### Without reverse cost


SELECT * FROM pgr_Dijkstra(
'SELECT id, source, target, cost FROM edges',
3, 5,
true);