Path model

Introduction

The path model is a graph structure composed of points and edges. It is used to solve problems such as road network-based path planning, GPS navigation for electronic maps, and routing. The path model is fully compatible with PGRouting interfaces and supports the smooth migration of existing applications. Path data forms a geometric network graph of edges and nodes, which is primarily used to build road and traffic networks.

Ganos Networking is a spatiotemporal engine extension for PolarDB for PostgreSQL. The Networking extension provides functions and stored procedures to find the fastest, shortest, or optimal path based on a cost model. It offers geospatial routing features and supports various path and network analysis algorithms. This adds path and network analysis capabilities to the database.

Function overview

Ganos Networking provides a series of path planning and network analysis functions:

• Johnson's algorithm.

• Floyd-Warshall algorithm.

• A* and bidirectional A* shortest path algorithms.

• Dijkstra and bidirectional Dijkstra shortest path algorithms.

• Traveling Salesperson algorithm.

• Prim's algorithm.

• Kruskal's algorithm.

• K-shortest path algorithm.

• Flow analysis.

• Graph topology operations.

• Graph component operations.

• Graph contraction.

• Turn Restriction Shortest Path (TRSP) algorithm.

Some functions also support calculations using a cost or a cost matrix.

Key business scenarios

Ganos Networking can be used in a wide range of scenarios:

• Optimal route planning

  In industries such as logistics, express delivery, and taxi services, you can use Ganos Networking to calculate the shortest or fastest path between two points for route planning and optimization. For non-geographic paths, such as connections between Internet nodes, Ganos Networking also helps find an optimal network topology.

• Geospatial analysis

  You can use Ganos Networking to perform road network-based analysis, such as nearest neighbor searches and service area analysis. This analysis helps you understand the distribution and relationships of geospatial data to improve decision-making and planning.

• Traffic flow management

  You can combine Ganos Networking with traffic flow data to analyze traffic, predict congestion, and obtain optimization suggestions. This is valuable for applications such as urban traffic management and intelligent transportation systems.

Basic components

pgr_<name>(Inner_queries, Parameters, [ Optional_parameters ])

Result column data structures

The returned columns vary depending on the function.

Result for a single path

Applies to the pgr_withPoints function:

Applies to the pgr_dijkstraNear function:

Result for multiple paths

Applies to functions that are selective for multiple paths:

Applies to functions that are not selective for multiple paths:

Result for cost functions

Applies to functions that use a cost or cost matrix:

Introduction

This quick start guide describes the basic usage of the Ganos Networking engine, including how to create an extension, create a table, insert data, update properties, create a topology, and query paths.

Syntax description

• Create the extension.

   CREATE Extension Ganos_Networking cascade;

  Note

  Install the extension in the public schema to avoid permission issues.

  CREATE extension Ganos_Networking WITH schema public cascade;

• Create a 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
   );

• Insert records.

   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);

• Update table properties.

   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'   -- Both ways
              WHEN (cost>0 AND reverse_cost<0) THEN 'FT'  -- In the direction of the LINESTRING
              WHEN (cost<0 AND reverse_cost>0) THEN 'TF'  -- In the reverse direction of the LINESTRING
              ELSE '' END;

• Create a topology.

   SELECT pgr_createTopology('edge_table',0.001);

• Query the shortest path.

   -- Dijkstra shortest path
   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* path algorithm
   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)
  
   -- TRSP path algorithm
   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)

• Drop the extension (optional).

   Drop Extension Ganos_Networking cascade;

SQL reference

For a detailed SQL manual, see the official pgRouting documentation.