# pgRouting Manual (3.6)

## pgr_extractVertices – Proposed

`pgr_extractVertices` — Extracts the vertices information

Warning

Proposed functions for next mayor release.

- They are not officially in the current release.

- They will likely officially be part of the next mayor release:

  - The functions make use of ANY-INTEGER and ANY-NUMERICAL

  - Name might not change. (But still can)

  - Signature might not change. (But still can)

  - Functionality might not change. (But still can)

  - pgTap tests have being done. But might need more.

  - Documentation might need refinement.

Availability

- Version 3.3.0

  - Classified as proposed function

- Version 3.0.0

  - New experimental function

## Description

This is an auxiliary function for extracting the vertex information of the set of edges of a graph.

- When the edge identifier is given, then it will also calculate the in and out edges

## Signatures

pgr_extractVertices(Edges SQL, [`dryrun`])
RETURNS SETOF `(id, in_edges, out_edges, x, y, geom)`
OR EMTPY SET

Example:

  Extracting the vertex information

    SELECT  * FROM pgr_extractVertices(
      'SELECT id, geom FROM edges');
     id | in_edges | out_edges |       x        |  y  |                    geom
    ----+----------+-----------+----------------+-----+--------------------------------------------
      1 |          | {6}       |              0 |   2 | 010100000000000000000000000000000000000040
      2 |          | {17}      |            0.5 | 3.5 | 0101000000000000000000E03F0000000000000C40
      3 | {6}      | {7}       |              1 |   2 | 0101000000000000000000F03F0000000000000040
      4 | {17}     |           | 1.999999999999 | 3.5 | 010100000068EEFFFFFFFFFF3F0000000000000C40
      5 |          | {1}       |              2 |   0 | 010100000000000000000000400000000000000000
      6 | {1}      | {2,4}     |              2 |   1 | 01010000000000000000000040000000000000F03F
      7 | {4,7}    | {8,10}    |              2 |   2 | 010100000000000000000000400000000000000040
      8 | {10}     | {12,14}   |              2 |   3 | 010100000000000000000000400000000000000840
      9 | {14}     |           |              2 |   4 | 010100000000000000000000400000000000001040
     10 | {2}      | {3,5}     |              3 |   1 | 01010000000000000000000840000000000000F03F
     11 | {5,8}    | {9,11}    |              3 |   2 | 010100000000000000000008400000000000000040
     12 | {11,12}  | {13}      |              3 |   3 | 010100000000000000000008400000000000000840
     13 |          | {18}      |            3.5 | 2.3 | 01010000000000000000000C406666666666660240
     14 | {18}     |           |            3.5 |   4 | 01010000000000000000000C400000000000001040
     15 | {3}      | {16}      |              4 |   1 | 01010000000000000000001040000000000000F03F
     16 | {9,16}   | {15}      |              4 |   2 | 010100000000000000000010400000000000000040
     17 | {13,15}  |           |              4 |   3 | 010100000000000000000010400000000000000840
    (17 rows)

## Parameters

Parameter | Type | Description
--- | --- | ---
Edges SQL | `TEXT` | Edges SQL as described below

## Optional parameters

Parameter | Type | Default | Description
--- | --- | --- | ---

`dryrun`

`BOOLEAN`

`false`

- When true do not process and get in a NOTICE the resulting query.

## Inner Queries

### Edges SQL

#### When line geometry is known

Column | Type | Description
--- | --- | ---
`id` | `BIGINT` | (Optional) identifier of the edge.
`geom` | `LINESTRING` | Geometry of the edge.

This inner query takes precedence over the next two inner query, therefore other columns are ignored when `geom` column appears.

- Ignored columns:

  - `startpoint`

  - `endpoint`

  - `source`

  - `target`

#### When vertex geometry is known

To use this inner query the column `geom` should not be part of the set of columns.

Column | Type | Description
--- | --- | ---
`id` | `BIGINT` | (Optional) identifier of the edge.
`startpoint` | `POINT` | POINT geometry of the starting vertex.
`endpoint` | `POINT` | POINT geometry of the ending vertex.

This inner query takes precedence over the next inner query, therefore other columns are ignored when `startpoint` and `endpoint` columns appears.

- Ignored columns:

  - `source`

  - `target`

#### When identifiers of vertices are known

To use this inner query the columns `geom`, `startpoint` and `endpoint` should not be part of the set of columns.

Column | Type | Description
--- | --- | ---
`id` | `BIGINT` | (Optional) identifier of the edge.
`source` | `ANY-INTEGER` | Identifier of the first end point vertex of the edge.
`target` | `ANY-INTEGER` | Identifier of the second end point vertex of the edge.

## Result columns

Column | Type | Description
--- | --- | ---
`id` | `BIGINT` | Vertex identifier

`in_edges`

`BIGINT[]`

Array of identifiers of the edges that have the vertex `id` as first end point.

- `NULL` When the `id` is not part of the inner query

`out_edges`

`BIGINT[]`

Array of identifiers of the edges that have the vertex `id` as second end point.

- `NULL` When the `id` is not part of the inner query

`x`

`FLOAT`

X value of the point geometry

- `NULL` When no geometry is provided

`y`

`FLOAT`

X value of the point geometry

- `NULL` When no geometry is provided

`geom`

`POINT`

Geometry of the point

- `NULL` When no geometry is provided

## Additional Examples

### Dry run execution

To get the query generated used to get the vertex information, use `dryrun := true`.

The results can be used as base code to make a refinement based on the backend development needs.

    SELECT  * FROM pgr_extractVertices(
      'SELECT id, geom FROM edges',
      dryrun => true);
    NOTICE:
            WITH

            main_sql AS (
              SELECT id, geom FROM edges
            ),

            the_out AS (
              SELECT id::BIGINT AS out_edge, ST_StartPoint(geom) AS geom
              FROM main_sql
            ),

            agg_out AS (
              SELECT array_agg(out_edge ORDER BY out_edge) AS out_edges, ST_x(geom) AS x, ST_Y(geom) AS y, geom
              FROM the_out
              GROUP BY geom
            ),

            the_in AS (
              SELECT id::BIGINT AS in_edge, ST_EndPoint(geom) AS geom
              FROM main_sql
            ),

            agg_in AS (
              SELECT array_agg(in_edge ORDER BY in_edge) AS in_edges, ST_x(geom) AS x, ST_Y(geom) AS y, geom
              FROM the_in
              GROUP BY geom
            ),

            the_points AS (
              SELECT in_edges, out_edges, coalesce(agg_out.geom, agg_in.geom) AS geom
              FROM agg_out
              FULL OUTER JOIN agg_in USING (x, y)
            )

            SELECT row_number() over(ORDER BY ST_X(geom), ST_Y(geom)) AS id, in_edges, out_edges, ST_X(geom), ST_Y(geom), geom
            FROM the_points;
     id | in_edges | out_edges | x | y | geom
    ----+----------+-----------+---+---+------
    (0 rows)

### Create a routing topology

#### Make sure the database does not have the `vertices_table`

    DROP TABLE IF EXISTS vertices_table;
    NOTICE:  table "vertices_table" does not exist, skipping
    DROP TABLE

#### Clean up the columns of the routing topology to be created

    UPDATE edges
    SET source = NULL, target = NULL,
    x1 = NULL, y1 = NULL,
    x2 = NULL, y2 = NULL;
    UPDATE 18

#### Create the vertices table

- When the `LINESTRING` has a SRID then use `geom::geometry(POINT, <SRID>)`

- For big edge tables that are been prepared,

  - Create it as `UNLOGGED` and

  - After the table is created `ALTER TABLE .. SET LOGGED`

    SELECT  * INTO vertices_table
    FROM pgr_extractVertices('SELECT id, geom FROM edges ORDER BY id');
    SELECT 17

#### Inspect the vertices table

    SELECT *
    FROM vertices_table;
     id | in_edges | out_edges |       x        |  y  |                    geom
    ----+----------+-----------+----------------+-----+--------------------------------------------
      1 |          | {6}       |              0 |   2 | 010100000000000000000000000000000000000040
      2 |          | {17}      |            0.5 | 3.5 | 0101000000000000000000E03F0000000000000C40
      3 | {6}      | {7}       |              1 |   2 | 0101000000000000000000F03F0000000000000040
      4 | {17}     |           | 1.999999999999 | 3.5 | 010100000068EEFFFFFFFFFF3F0000000000000C40
      5 |          | {1}       |              2 |   0 | 010100000000000000000000400000000000000000
      6 | {1}      | {2,4}     |              2 |   1 | 01010000000000000000000040000000000000F03F
      7 | {4,7}    | {8,10}    |              2 |   2 | 010100000000000000000000400000000000000040
      8 | {10}     | {12,14}   |              2 |   3 | 010100000000000000000000400000000000000840
      9 | {14}     |           |              2 |   4 | 010100000000000000000000400000000000001040
     10 | {2}      | {3,5}     |              3 |   1 | 01010000000000000000000840000000000000F03F
     11 | {5,8}    | {9,11}    |              3 |   2 | 010100000000000000000008400000000000000040
     12 | {11,12}  | {13}      |              3 |   3 | 010100000000000000000008400000000000000840
     13 |          | {18}      |            3.5 | 2.3 | 01010000000000000000000C406666666666660240
     14 | {18}     |           |            3.5 |   4 | 01010000000000000000000C400000000000001040
     15 | {3}      | {16}      |              4 |   1 | 01010000000000000000001040000000000000F03F
     16 | {9,16}   | {15}      |              4 |   2 | 010100000000000000000010400000000000000040
     17 | {13,15}  |           |              4 |   3 | 010100000000000000000010400000000000000840
    (17 rows)

#### Create the routing topology on the edge table

Updating the `source` information

    WITH
    out_going AS (
      SELECT id AS vid, unnest(out_edges) AS eid, x, y
      FROM vertices_table
    )
    UPDATE edges
    SET source = vid, x1 = x, y1 = y
    FROM out_going WHERE id = eid;
    UPDATE 18

Updating the `target` information

    WITH
    in_coming AS (
      SELECT id AS vid, unnest(in_edges) AS eid, x, y
      FROM vertices_table
    )
    UPDATE edges
    SET target = vid, x2 = x, y2 = y
    FROM in_coming WHERE id = eid;
    UPDATE 18

#### Inspect the routing topology

    SELECT id, source, target, x1, y1, x2, y2
    FROM edges ORDER BY id;
     id | source | target | x1  | y1  |       x2       | y2
    ----+--------+--------+-----+-----+----------------+-----
      1 |      5 |      6 |   2 |   0 |              2 |   1
      2 |      6 |     10 |   2 |   1 |              3 |   1
      3 |     10 |     15 |   3 |   1 |              4 |   1
      4 |      6 |      7 |   2 |   1 |              2 |   2
      5 |     10 |     11 |   3 |   1 |              3 |   2
      6 |      1 |      3 |   0 |   2 |              1 |   2
      7 |      3 |      7 |   1 |   2 |              2 |   2
      8 |      7 |     11 |   2 |   2 |              3 |   2
      9 |     11 |     16 |   3 |   2 |              4 |   2
     10 |      7 |      8 |   2 |   2 |              2 |   3
     11 |     11 |     12 |   3 |   2 |              3 |   3
     12 |      8 |     12 |   2 |   3 |              3 |   3
     13 |     12 |     17 |   3 |   3 |              4 |   3
     14 |      8 |      9 |   2 |   3 |              2 |   4
     15 |     16 |     17 |   4 |   2 |              4 |   3
     16 |     15 |     16 |   4 |   1 |              4 |   2
     17 |      2 |      4 | 0.5 | 3.5 | 1.999999999999 | 3.5
     18 |     13 |     14 | 3.5 | 2.3 |            3.5 |   4
    (18 rows)

Generated topology

### 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 bridge 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.

#### Adding split edges

For each pair of crossing edges a process similar to this one must be performed.

The columns inserted and the way are calculated are based on the application. For example, if the edges have a trait name, then that column is to be copied.

For pgRouting calculations

- factor based on the position of the intersection of the edges can be used to adjust the `cost` and `reverse_cost` columns.

- Capacity information, used in the Flow - Family of functions functions does not need to change when splitting edges.

    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

#### Adding new vertices

After adding all the split edges required by the application, the newly created vertices need to be added to the vertices table.

    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

#### Updating edges topology

    /* -- 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

#### Removing the surplus edges

Once all significant information needed by the application has been transported to the new edges, then the crossing edges can be deleted.

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

There are other options to do this task, like creating a view, or a materialized view.

#### Updating vertices topology

To keep the graph consistent, the vertices topology needs to be updated

    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

#### Checking for crossing edges

There are no crossing edges on the graph.

    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)

### Graphs without geometries

Using this table design for this example:

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

#### Insert the data

    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 | start_vid | end_vid | node | edge | cost | agg_cost
    -----+----------+-----------+---------+------+------+------+----------
       1 |        1 |         1 |       5 |    1 |    2 |    9 |        0
       2 |        2 |         1 |       5 |    3 |    6 |    2 |        9
       3 |        3 |         1 |       5 |    6 |    9 |    9 |       11
       4 |        4 |         1 |       5 |    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\)

#### Vertex information

To obtain the vertices information, use pgr_extractVertices – Proposed

    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)

## See Also

- Topology - Family of Functions

- pgr_createVerticesTable

Indices and tables

- Index

- Search Page