PolarDB:Path model

Overview

Path model is a graph structure described by nodes and edges, which is used for path planning on a road network, path search and planning in GPS navigation on an electronic map, and routing. The path model is fully compatible with pgRouting functions and allows you to smoothly migrate existing applications. Path data is a geometric network diagram that consists of edges and nodes. It is used to build road and traffic networks.

GanosBase Networking is a spatio-temporal engine extension of PostgreSQL (PolarDB for PostgreSQL). GanosBase Networking provides a set of functions and stored procedures to find the fastest, shortest, or even optimal path based on the cost model. GanosBase Networking provides the geospatial routing feature and supports multiple algorithms for path analysis and network analysis. The path analysis and network analysis are supported for databases.

Features

GanosBase Networking provides a set of functions for path planning and network analysis:

• Johnson's algorithm.

• Floyd-Warshall algorithm.

• A* or bidirectional A* pathfinding algorithm.

• Dijkstra's or bidirectional Dijkstra's pathfinding algorithm.

• The traveling salesman algorithm.

• Prim's algorithm.

• Kruskal's algorithm.

• K shortest path algorithm.

• Flow analysis.

• Topology operations.

• Component operations.

• Contractions.

• Turn restriction shortest path algorithm.

Some functions also allow you to set the cost or cost matrix for calculation.

Scenarios

GanosBase Networking can be used in the following scenarios:

• Route planning

  In industries such as logistics, delivery services, and taxi services, GanosBase Networking can be used to calculate the shortest or fastest path between two points for route planning and optimization. For non-geographic paths, such as the connections between Internet nodes, you can use GanosBase Networking to obtain a better network topology.

• Geospatial analysis

  GanosBase Networking can be used to perform analysis based on road network, such as nearest neighbor search and service zone analysis. These analysis tasks allows you to understand the distribution and relationships of geospatial data for further decision-making and planning.

• Traffic flow management

  GanosBase Networking can be used to analyze traffic volume data, predict congestion, and provide optimization recommendations. This helps optimize applications such as urban traffic management and intelligent transportation systems.

Components

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

Data structure of result columns

Different columns are returned for different functions.

Result columns for a path

The pgr_withPoints function returns the following columns:

The pgr_dijkstraNear function returns the following columns:

Result columns for multiple paths

The following columns are returned for functions that are selective for multiple paths:

The following columns are returned for functions that are not selective for multiple paths:

Result columns for cost functions

The following columns are returned for cost or cost matrix functions:

Overview

This section describes the basic usage of the GanosBase Networking engine, including extended creation, table creation, data insertion, attribute update, topology creation, and path query.

Syntax

• Create the extension.

   CREATE Extension Ganos_Networking cascade;

  Note

  Install the extension into the public schema to avoid possible 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
   );

• Inserted 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 attributes.

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

• Create a topology.

   SELECT pgr_createTopology('edge_table',0.001);

• Query the shortest path.

  -- Use the Dijkstra's pathfinding algorithm.
   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)
  
   -- Use the A* pathfinding 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)
  
   -- Use the turn restricted shortest path (TRSP) 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)

• Delete the extension (optional)

   Drop Extension Ganos_Networking cascade;

SQL statements

For more information about SQL statements, see the official pgRouting documentation.