PolarDB:Path model

Graphs

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

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

• E ⊆ {(u, v) | u, v ∈ V} is a set of edges connecting those vertices.

Graph types include undirected graphs, undirected simple graphs, directed graphs, and directed simple graphs. In GanosBase Networking, graphs are stored in the database as either:

• Graphs with costs: each edge has a cost column representing the weight from source to target.

• Graphs with costs and reverse costs: each edge also has a reverse_cost column representing the weight in the opposite direction.

Both graph types can be treated as directed or undirected during calculation.

Columns for a graph with costs:

Additional column for a graph with costs and reverse costs:

Supported algorithms

GanosBase Networking supports 13 algorithms for path analysis and network analysis:

• Johnson's algorithm

• Floyd-Warshall algorithm

• A* algorithm / bidirectional A* algorithm

• Dijkstra's algorithm / bidirectional Dijkstra's algorithm

• Traveling salesman algorithm

• Prim's algorithm

• Kruskal's algorithm

• K shortest paths algorithm

• Flow analysis

• Topology operations

• Component operations

• Contractions

• Turn Restriction Shortest Path (TRSP) algorithm

Some algorithms also accept a cost or cost matrix for calculation.

Function structure

All GanosBase Networking functions follow the pgRouting function signature:

pgr_<name>(inner_queries, parameters, [optional_parameters])

• inner_queries: SQL statements that define the graph data the function consumes.

• parameters: required inputs for the function.

• optional_parameters: optional inputs; each has a default value when omitted.

Each function supports one or more of these overloads:

Inner query types

Inner queries pass graph data to the routing function. The type required depends on the algorithm.

General Edge SQL columns:

General Edge SQL without ID — same columns as above, but omit id.

General Edge SQL with x and y — same columns as General Edge SQL (without id), with four additional columns:

Restrictions SQL columns:

Points SQL columns:

Result columns

Path results — returned by single-path functions:

pgr_withPoints returns the same columns with the following differences:

• [start_vid]: positive = starting vertex ID; negative = ending vertex ID.

• [end_vid]: positive = ending vertex ID; negative = starting vertex ID.

• node: positive = vertex ID; negative = point ID.

• agg_cost: 0 for the first record of the path.

pgr_dijkstraNear always returns start_vid and end_vid (not conditional on query type).

Multiple-path results — returned by functions that find multiple paths:

For selective functions:

For non-selective functions, start_vid and end_vid are always returned (no brackets).

Cost function results — returned by cost and cost matrix functions:

Step 1: Install the extension

CREATE EXTENSION Ganos_Networking WITH SCHEMA public CASCADE;

Step 2: Create the edge table

CREATE TABLE edge_table (
    id BIGSERIAL,
    dir CHARACTER VARYING,
    source BIGINT,
    target BIGINT,
    cost FLOAT,
    reverse_cost FLOAT,
    capacity BIGINT,
    reverse_capacity BIGINT,
    category_id INTEGER,
    reverse_category_id INTEGER,
    x1 FLOAT,
    y1 FLOAT,
    x2 FLOAT,
    y2 FLOAT,
    the_geom GEOMETRY
);

Step 3: Insert edges

INSERT INTO edge_table (
    category_id, reverse_category_id,
    cost, reverse_cost,
    capacity, reverse_capacity,
    x1, y1,
    x2, y2) VALUES
(3, 1,    1,  1,  80, 130,   2,   0,    2, 1),
(3, 2,   -1,  1,  -1, 100,   2,   1,    3, 1),
(2, 1,   -1,  1,  -1, 130,   3,   1,    4, 1),
(2, 4,    1,  1, 100,  50,   2,   1,    2, 2),
(1, 4,    1, -1, 130,  -1,   3,   1,    3, 2),
(4, 2,    1,  1,  50, 100,   0,   2,    1, 2),
(4, 1,    1,  1,  50, 130,   1,   2,    2, 2),
(2, 1,    1,  1, 100, 130,   2,   2,    3, 2),
(1, 3,    1,  1, 130,  80,   3,   2,    4, 2),
(1, 4,    1,  1, 130,  50,   2,   2,    2, 3),
(1, 2,    1, -1, 130,  -1,   3,   2,    3, 3),
(2, 3,    1, -1, 100,  -1,   2,   3,    3, 3),
(2, 4,    1, -1, 100,  -1,   3,   3,    4, 3),
(3, 1,    1,  1,  80, 130,   2,   3,    2, 4),
(3, 4,    1,  1,  80,  50,   4,   2,    4, 3),
(3, 3,    1,  1,  80,  80,   4,   1,    4, 2),
(1, 2,    1,  1, 130, 100,   0.5, 3.5,  1.999999999999, 3.5),
(4, 1,    1,  1,  50, 130,   3.5, 2.3,  3.5, 4);

Step 4: Set edge geometry and direction

UPDATE edge_table
SET the_geom = ST_MakeLine(ST_Point(x1, y1), ST_Point(x2, y2)),
    dir = CASE
        WHEN (cost > 0 AND reverse_cost > 0) THEN 'B'   -- bidirectional
        WHEN (cost > 0 AND reverse_cost < 0) THEN 'FT'  -- forward only
        WHEN (cost < 0 AND reverse_cost > 0) THEN 'TF'  -- reverse only
        ELSE ''
    END;

Step 5: Build the topology

SELECT pgr_createTopology('edge_table', 0.001);

Step 6: Run path queries

All three examples below find a path in the same graph. They differ in algorithm and, as a result, in the path found and the required inner query columns.

Dijkstra's algorithm — shortest path from node 2 to node 3:

SELECT * FROM pgr_dijkstra(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
    2, 3
);

 seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
   1 |        1 |    2 |    4 |    1 |        0
   2 |        2 |    5 |    8 |    1 |        1
   3 |        3 |    6 |    9 |    1 |        2
   4 |        4 |    9 |   16 |    1 |        3
   5 |        5 |    4 |    3 |    1 |        4
   6 |        6 |    3 |   -1 |    0 |        5
(6 rows)

A* algorithm — shortest path from node 2 to node 12 (requires x, y coordinates; runs as undirected with heuristic 2):

SELECT * FROM pgr_astar(
    'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
    2, 12,
    directed := false, heuristic := 2
);

 seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
   1 |        1 |    2 |    2 |    1 |        0
   2 |        2 |    3 |    3 |    1 |        1
   3 |        3 |    4 |   16 |    1 |        2
   4 |        4 |    9 |   15 |    1 |        3
   5 |        5 |   12 |   -1 |    0 |        4
(5 rows)

Turn Restriction Shortest Path (TRSP) algorithm — shortest path from node 2 to node 7 with turn restrictions:

SELECT * FROM pgr_trsp(
    'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost FROM edge_table',
    2, 7, false, false,
    'SELECT to_cost, target_id::int4,
     from_edge || COALESCE('','' || via_path, '''') AS via_path
     FROM restrictions'
);

 seq | id1 | id2 | cost
-----+-----+-----+------
   0 |   2 |   4 |    1
   1 |   5 |  10 |    1
   2 |  10 |  12 |    1
   3 |  11 |  11 |    1
   4 |   6 |   8 |    1
   5 |   5 |   7 |    1
   6 |   8 |   6 |    1
   7 |   7 |  -1 |    0
(8 rows)

Step 7: Remove the extension (optional)

DROP EXTENSION Ganos_Networking CASCADE;