pgRouting Concepts - pgRouting Manual (3.3)

Graph definition

A graph is an ordered pair \(G = (V ,E)\) where:

• \(V\) is a set of vertices, also called nodes.

• \(E \subseteq \{( u, v ) \mid u , v \in V \}\)

There are different kinds of graphs:

• Undirected graph

  • \(E \subseteq \{( u, v ) \mid u , v \in V\}\)

• Undirected simple graph

  • \(E \subseteq \{( u, v ) \mid u , v \in V, u \neq v\}\)

• Directed graph

  • \(E \subseteq \{( u, v ) \mid (u , v) \in (V X V) \}\)

• Directed simple graph

  • \(E \subseteq \{( u, v ) \mid (u , v) \in (V X V), u \neq v\}\)

Graphs:

• Do not have geometries.

• Some graph theory problems require graphs to have weights, called cost in pgRouting.

In pgRouting there are several ways to represent a graph on the database:

• With cost

  • ( id , source , target , cost )

• With cost and reverse_cost

  • ( id , source , target , cost , reverse_cost )

Where:

The decision of the graph to be directed or undirected is done when executing a pgRouting algorithm.

Graph with cost

The weighted directed graph, \(G_d(V,E)\) :

• Graph data is obtained with a query

  SELECT id, source, target, cost FROM edges

• the set of edges \(E\)

  • \(E = \{(source_{id}, target_{id}, cost_{id}) \text{ when } cost_{id} \ge 0 \}\)

  • Edges where cost is non negative are part of the graph.

• the set of vertices \(V\)

  • \(V = \{source_{id} \cup target_{id}\}\)

  • All vertices in source and target are part of the graph.

Directed graph

In a directed graph the edge \((source_{id}, target_{id}, cost_{id})\) has directionality: \(source_{id} \rightarrow target_{id}\)

For the following data:

SELECT *
FROM (VALUES (1, 1, 2, 5), (2, 1, 3, -3))
     AS t(id, source, target, cost);
 id  source  target  cost
----+--------+--------+------
  1       1       2     5
  2       1       3    -3
(2 rows)

Edge \(2\) ( \(1 \rightarrow 3\) ) is not part of the graph.

The data is representing the following graph:

Undirected graph

In an undirected graph the edge \((source_{id}, target_{id}, cost_{id})\) does not have directionality: \(source_{id} \frac{\;\;\;\;\;}{} target_{id}\)

• In terms of a directed graph is like having two edges: \(source_{id} \leftrightarrow target_{id}\)

For the following data:

SELECT *
FROM (VALUES (1, 1, 2, 5), (2, 1, 3, -3))
     AS t(id, source, target, cost);
 id  source  target  cost
----+--------+--------+------
  1       1       2     5
  2       1       3    -3
(2 rows)

Edge \(2\) ( \(1 \frac{\;\;\;\;\;}{} 3\) ) is not part of the graph.

The data is representing the following graph:

Graph with cost and reverse_cost

The weighted directed graph, \(G_d(V,E)\) , is defined by:

• Graph data is obtained with a query

  SELECT id, source, target, cost, reverse_cost FROM edges

• The set of edges \(E\) :

  • \(E = \begin{split} \begin{align} & {\{(source_{id}, target_{id}, cost_{id}) \text{ when } cost_{id} >=0 \}} \\ & \cup \\ & {\{(target_{id}, source_{id}, reverse\_cost_{id}) \text{ when } reverse\_cost_{id} >=0 \}} \end{align} \end{split}\)

  • Edges \((source \rightarrow target)\) where cost is non negative are part of the graph.

  • Edges \((target \rightarrow source)\) where reverse_cost is non negative are part of the graph.

• The set of vertices \(V\) :

  • \(V = \{source_{id} \cup target_{id}\}\)

  • All vertices in source and target are part of the graph.

Directed graph

In a directed graph both edges have directionality

• edge \((source_{id}, target_{id}, cost_{id})\) has directionality: \(source_{id} \rightarrow target_{id}\)

• edge \((target_{id}, source_{id}, reverse\_cost_{id})\) has directionality: \(target_{id} \rightarrow source_{id}\)

For the following data:

SELECT *
FROM (VALUES (1, 1, 2, 5, 2), (2, 1, 3, -3, 4), (3, 2, 3, 7, -1))
     AS t(id, source, target, cost, reverse_cost);
 id  source  target  cost  reverse_cost
----+--------+--------+------+--------------
  1       1       2     5             2
  2       1       3    -3             4
  3       2       3     7            -1
(3 rows)

Edges not part of the graph:

• \(2\) ( \(1 \rightarrow 3\) )

• \(3\) ( \(3 \rightarrow 2\) )

The data is representing the following graph:

Undirected graph

In a directed graph both edges do not have directionality

• Edge \((source_{id}, target_{id}, cost_{id})\) is \(source_{id} \frac{\;\;\;\;\;}{} target_{id}\)

• Edge \((target_{id}, source_{id}, reverse\_cost_{id})\) is \(target_{id} \frac{\;\;\;\;\;}{} source_{id}\)

• In terms of a directed graph is like having four edges:

  • \(source_i \leftrightarrow target_i\)

  • \(target_i \leftrightarrow source_i\)

For the following data:

SELECT *
FROM (VALUES (1, 1, 2, 5, 2), (2, 1, 3, -3, 4), (3, 2, 3, 7, -1))
     AS t(id, source, target, cost, reverse_cost);
 id  source  target  cost  reverse_cost
----+--------+--------+------+--------------
  1       1       2     5             2
  2       1       3    -3             4
  3       2       3     7            -1
(3 rows)

Edges not part of the graph:

• \(2\) ( \(1 \frac{\;\;\;\;\;}{} 3\) )

• \(3\) ( \(3 \frac{\;\;\;\;\;}{} 2\) )

The data is representing the following graph:

Wiki example

Solve the example problem taken from wikipedia ):

Where:

• Problem is to find the shortest path from \(1\) to \(5\) .

• Is an undirected graph.

• Although visually looks like to have geometries, the drawing is not to scale.

  • No geometries associated to the vertices or edges

• Has 6 vertices \(\{1,2,3,4,5,6\}\)

• Has 9 edges:

  \(\begin{split} \begin{align} E = & \{(1,2,7), (1,3,9), (1,6,14), \\ & (2,3,10), (2,4,13), \\ & (3,4,11), (3,6,2), \\ & (4,5,6), \\ & (5,6,9) \} \end{align} \end{split}\)

• The graph can be represented in many ways for example:

$ createdb wiki
$ psql wiki
wiki =# CREATE EXTENSION pgRouting CASCADE;

CREATE TABLE wiki (
  id SERIAL,
  source INTEGER,
  target INTEGER,
  cost INTEGER);
CREATE TABLE

INSERT INTO wiki (source, target, cost) VALUES
(1, 2, 7),  (1, 3, 9), (1, 6, 14),
(2, 3, 10), (2, 4, 15),
(3, 6, 2),  (3, 4, 11),
(4, 5, 6),
(5, 6, 9);
INSERT 0 9

Find the shortest path

To solve this example pgr_dijkstra is used:

SELECT * FROM pgr_dijkstra(
  'SELECT id, source, target, cost FROM wiki',
  1, 5, false);
 seq  path_seq  node  edge  cost  agg_cost
-----+----------+------+------+------+----------
   1         1     1     2     9         0
   2         2     3     6     2         9
   3         3     6     9     9        11
   4         4     5    -1     0        20
(4 rows)

To go from \(1\) to \(5\) the path goes thru the following vertices: \(1 \rightarrow 3 \rightarrow 6 \rightarrow 5\)

SELECT id, in_edges, out_edges
FROM pgr_extractVertices('SELECT id, source, target FROM wiki');
 id  in_edges  out_edges
----+----------+-----------
  3  {2,4}     {6,7}
  5  {8}       {9}
  4  {5,7}     {8}
  2  {1}       {4,5}
  1            {1,2,3}
  6  {3,6,9}  
(6 rows)

Create a routing Database

The first step is to create a database and load pgRouting in the database.

Typically create a database for each project.

Once having the database to work in, load your data and build the routing application in that database.

createdb sampledata
psql sampledata -c "CREATE EXTENSION pgrouting CASCADE"

Load Data

There are several ways to load your data into pgRouting.

• Manually creating a database.

  • Graphs without geometries

  • Sample Data : a small graph used on the documentation examples

• Using osm2pgrouting

There are various open source tools that can help, like:

shp2pgsql :

• postgresql shapefile loader

ogr2ogr :

• vector data conversion utility

osm2pgsql :

• load OSM data into postgresql

Please note that these tools will not import the data in a structure compatible with pgRouting and when this happens the topology needs to be adjusted.

• Breakup a segments on each segment-segment intersection

• When missing, add columns and assign values to source , target , cost , reverse_cost .

• Connect a disconnected graph.

• Create the complete graph topology

• Create one or more graphs based on the application to be developed.

  • Create a contracted graph for the high speed roads

  • Create graphs per state/country

In few words:

Prepare the graph

What and how to prepare the graph, will depend on the application and/or on the quality of the data and/or on how close the information is to have a topology usable by pgRouting and/or some other factors not mentioned.

The steps to prepare the graph involve geometry operations using PostGIS and some others involve graph operations like pgr_contraction to contract a graph.

The workshop has a step by step on how to prepare a graph using Open Street Map data, for a small application.

The use of indexes on the database design in general:

• Have the geometries indexed.

• Have the identifiers columns indexed.

Please consult the PostgreSQL documentation and the PostGIS documentation.

Build a routing topology

The basic information to use the majority of the pgRouting functions id, source, target, cost, [reverse_cost] is what in pgRouting is called the routing topology.

reverse_cost is optional but strongly recommended to have in order to reduce the size of the database due to the size of the geometry columns. Having said that, in this documentation reverse_cost is used in this documentation.

When the data comes with geometries and there is no routing topology, then this step is needed.

All the start and end vertices of the geometries need an identifier that is to be stored in a source and target columns of the table of the data. Likewise, cost and reverse_cost need to have the value of traversing the edge in both directions.

If the columns do not exist they need to be added to the table in question. (see ALTER TABLE )

The function pgr_extractVertices - Proposed is used to create a vertices table based on the edge identifier and the geometry of the edge of the graph.

Finally using the data stored on the vertices tables the source and target are filled up.

See Sample Data for an example for building a topology.

Data coming from OSM and using osm2pgrouting as an import tool, comes with the routing topology. See an example of using osm2pgrouting on the workshop .

Adjust costs

For this example the cost and reverse_cost values are going to be the double of the length of the geometry.

UPDATE edges SET
cost = sign(cost) * ST_length(geom) * 2,
reverse_cost = sign(reverse_cost) * ST_length(geom) * 2;
UPDATE 18

SELECT id, cost, reverse_cost FROM edges;
 id         cost            reverse_cost
----+--------------------+--------------------
  6                   2                   2
  7                   2                   2
  4                   2                   2
  5                   2                  -2
  8                   2                   2
 12                   2                  -2
 11                   2                  -2
 10                   2                   2
 17      2.999999999998      2.999999999998
 14                   2                   2
 18  3.4000000000000004  3.4000000000000004
 13                   2                  -2
 15                   2                   2
 16                   2                   2
  9                   2                   2
  3                  -2                   2
  1                   2                   2
  2                  -2                   2
(18 rows)

UPDATE edges SET
cost = sign(cost),
reverse_cost = sign(reverse_cost);
UPDATE 18

ALTER TABLE edges ADD COLUMN direction TEXT;
ALTER TABLE
UPDATE edges SET
direction = CASE WHEN (cost>0 AND reverse_cost>0) THEN 'B'
           WHEN (cost>0 AND reverse_cost<0) THEN 'FT'
           WHEN (cost<0 AND reverse_cost>0) THEN 'TF'
           ELSE '' END;
UPDATE 18

UPDATE edges SET
cost = CASE WHEN (direction = 'B' OR direction = 'FT')
       THEN ST_length(geom) * 2
       ELSE -1 END,
reverse_cost = CASE WHEN (direction = 'B' OR direction = 'TF')
       THEN ST_length(geom) * 2
       ELSE -1 END;
UPDATE 18

SELECT id, cost, reverse_cost FROM edges;
 id         cost            reverse_cost
----+--------------------+--------------------
  6                   2                   2
  7                   2                   2
  4                   2                   2
  5                   2                  -1
  8                   2                   2
 12                   2                  -1
 11                   2                  -1
 10                   2                   2
 17      2.999999999998      2.999999999998
 14                   2                   2
 18  3.4000000000000004  3.4000000000000004
 13                   2                  -1
 15                   2                   2
 16                   2                   2
  9                   2                   2
  3                  -1                   2
  1                   2                   2
  2                  -1                   2
(18 rows)

UPDATE edges SET
cost = sign(cost),
reverse_cost = sign(reverse_cost);
UPDATE 18
ALTER TABLE edges DROP COLUMN direction;
ALTER TABLE

Crossing edges

To get the crossing edges:

SELECT a.id, b.id
FROM edges AS a, edges AS b
WHERE a.id < b.id AND st_crosses(a.geom, b.geom);
 id  id
----+----
 13  18
(1 row)

That information is correct, for example, when in terms of vehicles, is it a tunnel or bride crossing over another road.

It might be incorrect, for example:

1. When it is actually an intersection of roads, where vehicles can make turns.

2. When in terms of electrical lines, the electrical line is able to switch roads even on a tunnel or bridge.

When it is incorrect, it needs fixing:

1. For vehicles and pedestrians

   • If the data comes from OSM and was imported to the database using osm2pgrouting , the fix needs to be done in the OSM portal and the data imported again.

   • In general when the data comes from a supplier that has the data prepared for routing vehicles, and there is a problem, the data is to be fixed from the supplier

2. For very specific applications

   • The data is correct when from the point of view of routing vehicles or pedestrians.

   • The data needs a local fix for the specific application.

Once analyzed one by one the crossings, for the ones that need a local fix, the edges need to be split .

SELECT ST_AsText((ST_Dump(ST_Split(a.geom, b.geom))).geom)
FROM edges AS a, edges AS b
WHERE a.id = 13 AND b.id = 18
UNION
SELECT ST_AsText((ST_Dump(ST_Split(b.geom, a.geom))).geom)
FROM edges AS a, edges AS b
WHERE a.id = 13 AND b.id = 18;
         st_astext
---------------------------
 LINESTRING(3.5 2.3,3.5 3)
 LINESTRING(3 3,3.5 3)
 LINESTRING(3.5 3,4 3)
 LINESTRING(3.5 3,3.5 4)
(4 rows)

The new edges need to be added to the edges table, the rest of the attributes need to be updated in the new edges, the old edges need to be removed and the routing topology needs to be updated.

WITH
first_edge AS (
  SELECT (ST_Dump(ST_Split(a.geom, b.geom))).path[1],
    (ST_Dump(ST_Split(a.geom, b.geom))).geom,
    ST_LineLocatePoint(a.geom,ST_Intersection(a.geom,b.geom)) AS factor
  FROM edges AS a, edges AS b
  WHERE a.id = 13 AND b.id = 18),
first_segments AS (
  SELECT path, first_edge.geom,
    capacity, reverse_capacity,
    CASE WHEN path=1 THEN factor * cost
         ELSE (1 - factor) * cost END AS cost,
    CASE WHEN path=1 THEN factor * reverse_cost
         ELSE (1 - factor) * reverse_cost END AS reverse_cost
  FROM first_edge , edges WHERE id = 13),
second_edge AS (
  SELECT (ST_Dump(ST_Split(b.geom, a.geom))).path[1],
    (ST_Dump(ST_Split(b.geom, a.geom))).geom,
    ST_LineLocatePoint(b.geom,ST_Intersection(a.geom,b.geom)) AS factor
  FROM edges AS a, edges AS b
  WHERE a.id = 13 AND b.id = 18),
second_segments AS (
  SELECT path, second_edge.geom,
    capacity, reverse_capacity,
    CASE WHEN path=1 THEN factor * cost
         ELSE (1 - factor) * cost END AS cost,
    CASE WHEN path=1 THEN factor * reverse_cost
         ELSE (1 - factor) * reverse_cost END AS reverse_cost
  FROM second_edge , edges WHERE id = 18),
all_segments AS (
  SELECT * FROM first_segments
  UNION
  SELECT * FROM second_segments)
INSERT INTO edges
  (capacity, reverse_capacity,
    cost, reverse_cost,
    x1, y1, x2, y2,
    geom)
(SELECT capacity, reverse_capacity, cost, reverse_cost,
  ST_X(ST_StartPoint(geom)), ST_Y(ST_StartPoint(geom)),
  ST_X(ST_EndPoint(geom)), ST_Y(ST_EndPoint(geom)),
  geom
  FROM all_segments);
INSERT 0 4

INSERT INTO vertices (in_edges, out_edges, x, y, geom)
(SELECT nv.in_edges, nv.out_edges, nv.x, nv.y, nv.geom
FROM pgr_extractVertices('SELECT id, geom FROM edges') AS nv
LEFT JOIN vertices AS v USING(geom) WHERE v.geom IS NULL);
INSERT 0 1

/* -- set the source information */
UPDATE edges AS e
SET source = v.id
FROM vertices AS v
WHERE source IS NULL AND ST_StartPoint(e.geom) = v.geom;
UPDATE 4
/* -- set the target information */
UPDATE edges AS e
SET target = v.id
FROM vertices AS v
WHERE target IS NULL AND ST_EndPoint(e.geom) = v.geom;
UPDATE 4

DELETE FROM edges WHERE id IN (13, 18);
DELETE 2

UPDATE vertices AS v SET
in_edges = nv.in_edges, out_edges = nv.out_edges
FROM (SELECT * FROM pgr_extractVertices('SELECT id, geom FROM edges')) AS nv
WHERE v.geom = nv.geom;
UPDATE 18

SELECT a.id, b.id
FROM edges AS a, edges AS b
WHERE a.id < b.id AND st_crosses(a.geom, b.geom);
 id  id
----+----
(0 rows)

Disconnected graphs

To get the graph connectivity:

SELECT * FROM pgr_connectedComponents(
  'SELECT id, source, target, cost, reverse_cost FROM edges'
);
 seq  component  node
-----+-----------+------
   1          1     1
   2          1     3
   3          1     5
   4          1     6
   5          1     7
   6          1     8
   7          1     9
   8          1    10
   9          1    11
  10          1    12
  11          1    13
  12          1    14
  13          1    15
  14          1    16
  15          1    17
  16          1    18
  17          2     2
  18          2     4
(18 rows)

In this example, the component \(2\) consists of vertices \(\{2, 4\}\) and both vertices are also part of the dead end result set.

This graph needs to be connected.

ALTER TABLE vertices ADD COLUMN component BIGINT;
ALTER TABLE
ALTER TABLE edges ADD COLUMN component BIGINT;
ALTER TABLE

UPDATE vertices SET component = c.component
FROM (SELECT * FROM pgr_connectedComponents(
  'SELECT id, source, target, cost, reverse_cost FROM edges'
)) AS c
WHERE id = node;
UPDATE 18

UPDATE edges SET component = v.component
FROM (SELECT id, component FROM vertices) AS v
WHERE source = v.id;
UPDATE 20

WITH
edges_sql AS (SELECT id, geom FROM edges WHERE component = 1),
point_sql AS (SELECT geom AS point FROM vertices WHERE component = 2),
results AS (
  SELECT
    id::BIGINT AS edge_id,
    ST_LineLocatePoint(geom, point) AS fraction,
    CASE WHEN ST_Intersects(ST_Buffer(geom, 2, 'side=right endcap=flat'), point)
         THEN 'r'
         ELSE 'l' END::CHAR AS side,
    geom <-> point AS distance,
    point,
    ST_MakeLine(point, ST_ClosestPoint(geom, point)) AS new_line
  FROM  edges_sql, point_sql
  WHERE ST_DWithin(geom, point, 2)
  ORDER BY geom <-> point),
prepare_cap AS (
  SELECT row_number() OVER (PARTITION BY point ORDER BY point, distance) AS rn, *
  FROM results),
cap AS (
  SELECT edge_id, fraction, side, distance, point, new_line
  FROM prepare_cap
  WHERE rn <= 1
)
SELECT edge_id, fraction, side, distance, point AS geom, new_line AS edge, id AS closest_vertex
INTO closest
FROM cap JOIN vertices ON (point = geom) ORDER BY distance LIMIT 1;
SELECT 1

WITH
info AS (
  SELECT
    edge_id, fraction, side, distance, ce.geom, edge, v.id AS closest,
    source, target, capacity, reverse_capacity, e.geom AS e_geom
  FROM closest AS ce
  JOIN vertices AS v USING (geom)
  JOIN edges AS e ON (edge_id = e.id)
  ORDER BY distance LIMIT 1),
three_options AS (
  SELECT
    closest AS source, target, 0 AS cost, 0 AS reverse_cost,
    capacity, reverse_capacity,
    ST_X(geom) AS x1, ST_Y(geom) AS y1,
    ST_X(ST_EndPoint(e_geom)) AS x2, ST_Y(ST_EndPoint(e_geom)) AS y2,
    ST_MakeLine(geom, ST_EndPoint(e_geom)) AS geom
  FROM info

  UNION

  SELECT closest, source, 0, 0, capacity, reverse_capacity,
    ST_X(geom) AS x1, ST_Y(geom) AS y1,
    ST_X(ST_StartPoint(e_geom)) AS x2, ST_Y(ST_StartPoint(e_geom)) AS y2,
    ST_MakeLine(info.geom, ST_StartPoint(e_geom))
  FROM info
  /*
  UNION
  -- This option requires splitting the edge
  SELECT closest, NULL, 0, 0, capacity, reverse_capacity,
    ST_X(geom) AS x1, ST_Y(geom) AS y1,
    ST_X(ST_EndPoint(edge)) AS x2, ST_Y(ST_EndPoint(edge)) AS y2,
    edge
  FROM info */
  )

INSERT INTO edges
  (source, target,
    cost, reverse_cost,
    capacity, reverse_capacity,
    x1, y1, x2, y2,
    geom)
(SELECT
    source, target, cost, reverse_cost, capacity, reverse_capacity,
    x1, y1, x2, y2, geom
  FROM three_options);
INSERT 0 2

SELECT * FROM pgr_connectedComponents(
  'SELECT id, source, target, cost, reverse_cost FROM edges'
);
 seq  component  node
-----+-----------+------
   1          1     1
   2          1     2
   3          1     3
   4          1     4
   5          1     5
   6          1     6
   7          1     7
   8          1     8
   9          1     9
  10          1    10
  11          1    11
  12          1    12
  13          1    13
  14          1    14
  15          1    15
  16          1    16
  17          1    17
  18          1    18
(18 rows)

Contraction of a graph

The graph can be reduced in size using Contraction - Family of functions

When to contract will depend on the size of the graph, processing times, correctness of the data, on the final application, or any other factor not mentioned.

A fairly good method of finding out if contraction can be useful is because of the number of dead ends and/or the number of linear edges.

A complete method on how to contract and how to use the contracted graph is described on Contraction - Family of functions

SELECT id FROM vertices
WHERE array_length(in_edges  out_edges, 1) = 1;
 id
----
  1
  5
  9
 13
 14
  2
  4
(7 rows)

SELECT id FROM vertices
WHERE array_length(in_edges  out_edges, 1) = 2;
 id
----
  3
 15
 17
(3 rows)

One to One

When routing from:

• From one starting vertex

• to one ending vertex

One to Many

When routing from:

• From one starting vertex

• to many ending vertices

Many to One

When routing from:

• From many starting vertices

• to one ending vertex

Many to Many

When routing from:

• From many starting vertices

• to many ending vertices

Combinations

When routing from:

• From many different starting vertices

• to many different ending vertices

• Every tuple specifies a pair of a start vertex and an end vertex

• Users can define the combinations as desired.

• Needs a Combinations SQL

Edges SQL

Combinations SQL

Used on combination signatures

Where:

ANY-INTEGER :

SMALLINT , INTEGER , BIGINT

Restrictions SQL

Where:

ANY-INTEGER :

SMALLINT , INTEGER , BIGINT

ANY-NUMERICAL :

SMALLINT , INTEGER , BIGINT , REAL , FLOAT

Points SQL

Points SQL for

• withPoints - Family of functions

Where:

ANY-INTEGER :

SMALLINT , INTEGER , BIGINT

ANY-NUMERICAL :

SMALLINT , INTEGER , BIGINT , REAL , FLOAT

Parameters for the Via functions

• pgr_dijkstraVia - Proposed

For the TRSP functions

• pgr_trsp - Turn Restriction Shortest Path (TRSP)

Where:

ANY-INTEGER :

SMALLINT , INTEGER , BIGINT

Return columns for a path

Used on functions that return one path solution

Returns set of (seq, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)

Used on functions the following:

• pgr_withPoints - Proposed

Returns set of (seq, path_seq [, start_pid] [, end_pid], node, edge, cost, agg_cost)

Used on functions the following:

• pgr_dijkstraNear - Proposed

Returns (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)

Multiple paths

Return columns for cost functions

Used in the following

• Cost - Category

• Cost Matrix - Category

• All Pairs - Family of Functions

Set of (start_vid, end_vid, agg_cost)

Return columns for flow functions

Edges SQL for the following

• Flow - Family of functions

Edges SQL for the following functions of Flow - Family of functions

• pgr_maxFlowMinCost - Experimental

Return columns for spanning tree functions

Edges SQL for the following

• pgr_prim

• pgr_kruskal

Returns SET OF (edge, cost)

For the Routing functions

To get faster results bound the queries to an area of interest of routing.

In this example Use an inner query SQL that does not include some edges in the routing function and is within the area of the results.

SELECT * FROM pgr_dijkstra($$
  SELECT id, source, target, cost, reverse_cost from edges
  WHERE geom && (SELECT st_buffer(geom, 1) AS myarea
    FROM edges WHERE id = 2)$$,
  1, 2);
 seq  path_seq  node  edge  cost  agg_cost
-----+----------+------+------+------+----------
(0 rows)