PolarDB:Modelo de caminho

Grafos

Um grafo é um par ordenado G = (V, E), onde:

• V é um conjunto de vértices (também chamados de nós).

• E ⊆ {(u, v) | u, v ∈ V} é um conjunto de arestas que conectam esses vértices.

Os tipos de grafo incluem grafos não direcionados, grafos simples não direcionados, grafos direcionados e grafos simples direcionados. No GanosBase Networking, os grafos são armazenados no banco de dados das seguintes formas:

• Grafos com custos: cada aresta possui uma coluna cost que representa o peso da origem ao destino.

• Grafos com custos e custos reversos: cada aresta também possui uma coluna reverse_cost que representa o peso na direção oposta.

Ambos os tipos de grafo podem ser tratados como direcionados ou não direcionados durante o cálculo.

Colunas para um grafo com custos:

Coluna adicional para um grafo com custos e custos reversos:

Algoritmos suportados

O GanosBase Networking suporta 13 algoritmos para análise de caminhos e de redes:

• Algoritmo de Johnson

• Algoritmo de Floyd-Warshall

• Algoritmo A / algoritmo A bidirecional

• Algoritmo de Dijkstra / algoritmo de Dijkstra bidirecional

• Algoritmo do caixeiro-viajante

• Algoritmo de Prim

• Algoritmo de Kruskal

• Algoritmo de K caminhos mais curtos

• Análise de fluxo

• Operações de topologia

• Operações de componentes

• Contrações

• Algoritmo de Caminho Mais Curto com Restrição de Conversão (TRSP)

Alguns algoritmos também aceitam um custo ou matriz de custos para cálculo.

Estrutura das funções

Todas as funções do GanosBase Networking seguem a assinatura de função do pgRouting:

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

• inner_queries: instruções SQL que definem os dados do grafo consumidos pela função.

• parameters: entradas obrigatórias para a função.

• optional_parameters: entradas opcionais; cada uma possui um valor padrão quando omitida.

Cada função suporta uma ou mais destas sobrecargas:

Tipos de consulta interna

As consultas internas passam os dados do grafo para a função de roteamento. O tipo necessário depende do algoritmo.

Colunas do General Edge SQL:

General Edge SQL sem ID — mesmas colunas acima, mas omitindo id.

General Edge SQL com x e y — mesmas colunas do General Edge SQL (sem id), com quatro colunas adicionais:

Colunas do Restrictions SQL:

Colunas do Points SQL:

Colunas de resultado

Resultados de caminho — retornados por funções de caminho único:

A função pgr_withPoints retorna as mesmas colunas com as seguintes diferenças:

• [start_vid]: positivo = ID do vértice inicial; negativo = ID do vértice final.

• [end_vid]: positivo = ID do vértice final; negativo = ID do vértice inicial.

• node: positivo = ID do vértice; negativo = ID do ponto.

• agg_cost: 0 para o primeiro registro do caminho.

A função pgr_dijkstraNear sempre retorna start_vid e end_vid (independentemente do tipo de consulta).

Resultados de múltiplos caminhos — retornados por funções que encontram vários caminhos:

Para funções seletivas:

Para funções não seletivas, start_vid e end_vid são sempre retornados (sem colchetes).

Resultados de função de custo — retornados por funções de custo e matriz de custos:

Etapa 1: Instale a extensão

CREATE EXTENSION Ganos_Networking WITH SCHEMA public CASCADE;

Etapa 2: Crie a tabela de arestas

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

Etapa 3: Inserir arestas

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

Etapa 4: Defina geometria e direção das arestas

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;

Etapa 5: Construir a topologia

SELECT pgr_createTopology('edge_table', 0.001);

Etapa 6: Execute consultas de caminho

Todos os três exemplos abaixo encontram um caminho no mesmo grafo. Eles diferem no algoritmo e, consequentemente, no caminho encontrado e nas colunas de consulta interna necessárias.

Algoritmo de Dijkstra — caminho mais curto do nó 2 ao nó 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)

Algoritmo A* — caminho mais curto do nó 2 ao nó 12 (requer coordenadas x, y; executa como não direcionado com heurística 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)

Algoritmo de Caminho Mais Curto com Restrição de Conversão (TRSP) — caminho mais curto do nó 2 ao nó 7 com restrições de conversão:

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)

Etapa 7: Remover a extensão (opcional)

DROP EXTENSION Ganos_Networking CASCADE;