pgr_lineGraph - Propuesto

pgr_lineGraph — Transforma un grafo dado en su grafo correspondiente basado en aristas.

Adentro: Boost Graph

Advertencia

Funciones propuestas para la próxima versión mayor.

• No están oficialmente en la versión actual.

• Es probable que oficialmente formen parte del próximo lanzamiento:

  • Las funciones hacen uso de ENTEROS y FLOTANTES

  • Probablemente el nombre no cambie. (Pero todavía puede)

  • Es posible que la firma no cambie. (Pero todavía puede)

  • Probablemente la funcionalidad no cambie. (Pero todavía puede)

  • Se han hecho pruebas con pgTap. Pero tal vez se necesiten más.

  • Es posible que la documentación necesite un refinamiento.

Disponibilidad

• Versión 3.7.0

  • Promovido a firma propuesta.

  • Funciona para grafos dirigidos y no dirigidos.

• Versión 2.5.0

  • Nueva función Experimental

Descripción

Dado un grafo \(G\), su grafo lineal \(L(G)\) es un grafo tal que:

• Cada vértice de \(L(G)\) representa una arista de \(G\).

• Dos vértices de \(L(G)\) son adyacentes si y sólo si sus aristas correspondientes comparten un punto final común en \(G\)

Las principales características son:

• Funciona para grafos dirigidos y no dirigidos.

• Las columnas cost y reverse_cost del resultado representan la existencia de la arista.

• Cuando el grafo es dirigido el resultado es dirigido.

  • Para obtener el Grafo lineal completo utilizar identificadores únicos en las aristas de doble sentido (Ver Ejemplos Adicionales).

• Cuando el grafo es no dirigido el resultado es no dirigido.

  • El reverse_cost es siempre \(-1\).

Firmas

pgr_lineGraph(SQL de aristas, [directed])

Regresa el conjunto de (seq, source, target, cost, reverse_cost)

O CONJUNTO VACÍO

Ejemplo:

Para un grafo no dirigido con aristas :math:”{2,4,5,8}”

SELECT * FROM pgr_lineGraph(
  'SELECT id, source, target, cost, reverse_cost
  FROM edges WHERE id IN (2,4,5,8)',
  false);
 seq | source | target | cost | reverse_cost
-----+--------+--------+------+--------------
   1 |      2 |      4 |    1 |           -1
   2 |      2 |      5 |    1 |           -1
   3 |      4 |      8 |    1 |           -1
   4 |      5 |      8 |    1 |           -1
(4 rows)

Parámetros

Parámetro	Tipo	Descripción
SQL de aristas	TEXT	SQL de aristas descritas más adelante.

Parámetros opcionales

Columna	Tipo	x Defecto	Descripción
directed	BOOLEAN	true	Cuando true el gráfo se considera Dirigido Cuando false el gráfo se considera No Dirigido.

Consultas Internas

SQL aristas

Columna	Tipo	x Defecto	Descripción
id	ENTEROS		Identificador de la arista.
source	ENTEROS		Identificador del primer vértice de la arista.
target	ENTEROS		Identificador del segundo vértice de la arista.
cost	FLOTANTES		Peso de la arista (source, target)
reverse_cost	FLOTANTES	-1	Peso de la arista (target, source) Cuando negativo: la arista (target, source) no existe, por lo tanto no es parte del grafo.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

FLOTANTES:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Columnas de resultados

Regresa el conjunto de (seq, source, target, cost, reverse_cost)

Columna	Tipo	Descripción
seq	INTEGER	Valor secuencial a partir de 1. Da un identificador local de la arista
source	BIGINT	Identificador del vértice de origen de la arista actual. Cuando es “negativo”: el origen es la arista inversa en el grafo original.
target	BIGINT	Identificador del vértice destino de la arista actual. Cuando es negativo: el destino es la arista inversa en el grafo original.
cost	FLOAT	Peso de la arista (source, target). Cuando negative: la arista (source, target) no existe, por lo tanto no es parte del grafo.
reverse_cost	FLOAT	Peso de la arista (target, source). Cuando negative: la arista (target, source) no existe, por lo tanto no es parte del grafo.

Ejemplos Adicionales

Dado el siguente grafo dirigido

\(G(V,E) = G(\{1,2,3,4\},\{ 1 \rightarrow 2, 1 \rightarrow 4, 2 \rightarrow 3, 3 \rightarrow 1, 3 \rightarrow 2, 3 \rightarrow 4, 4 \rightarrow 3})\)

Representación como dirigida con identificadores de arista compartidos

For the simplicity, the design of the edges table on the database, has the edge’s identifiers are represented with 3 digits:

cientos:

el vértice de origen

decenas:

siempre 0, actúa como separador

unidades:

el vértice de destino

En esta imagen,

• Las puntas de flechas simples o dobles representan una arista (fila) en la tabla de aristas.

• Los números en la sombra amarilla son los identificadores de las aristas.

Dos pares de aristas comparten el mismo identificador cuando se utiliza la columna reverse_cost.

• Las aristas \({2 \rightarrow 3, 3 \rightarrow 2}\) se representan con una fila de aristas con \(id=203\).

• Las aristas \({3 \rightarrow 4, 4 \rightarrow 3}\) se representan con una fila de aristas con \(id=304\).

El grafo puede crearse del siguiente modo:

CREATE TABLE edges_shared (
    id BIGINT,
    source BIGINT,
    target BIGINT,
    cost FLOAT,
    reverse_cost FLOAT,
    geom geometry
);
CREATE TABLE
INSERT INTO edges_shared (id, source, target, cost, reverse_cost, geom) VALUES
  (102, 1, 2, 1, -1, ST_MakeLine(ST_POINT(0,  2), ST_POINT(2,  2))),
  (104, 1, 4, 1, -1, ST_MakeLine(ST_POINT(0,  2), ST_POINT(0,  0))),
  (301, 3, 1, 1, -1, ST_MakeLine(ST_POINT(2,  0), ST_POINT(0,  2))),
  (203, 2, 3, 1,  1, ST_MakeLine(ST_POINT(2,  2), ST_POINT(2,  0))),
  (304, 3, 4, 1,  1, ST_MakeLine(ST_POINT(0,  0), ST_POINT(2,  0)));

Grafo lineal de un grafo dirigido representado con aristas compartidas

SELECT seq, source, target, cost, reverse_cost
FROM pgr_lineGraph(
  'SELECT id, source, target, cost, reverse_cost FROM edges_shared',
  true);
 seq | source | target | cost | reverse_cost
-----+--------+--------+------+--------------
   1 |    102 |    203 |    1 |           -1
   2 |    104 |    304 |    1 |           -1
   3 |    203 |    203 |    1 |            1
   4 |    203 |    301 |    1 |           -1
   5 |    203 |    304 |    1 |            1
   6 |    301 |    102 |    1 |           -1
   7 |    301 |    104 |    1 |           -1
   8 |    304 |    301 |    1 |           -1
   9 |    304 |    304 |    1 |            1
(9 rows)

• El resultado es un grafo dirigido.

• Para \(seq=4\) desde \(203 \leftrightarrow 304\) representa dos arsitas

• Todos los demás valores de seq representan una arista.

• Los valores cost y reverse_cost representan la existencia de la arista.

  • Cuando es positivo: la arista existe.

  • Cuando es negativo: la arista no existe.

Representación dirigida con identificadores de arista únicos

For the simplicity, the design of the edges table on the database, has the edge’s identifiers are represented with 3 digits:

cientos:

el vértice de origen

decenas:

siempre 0, actúa como separador

unidades:

el vértice de destino

En esta imagen,

• Las flechas de una cabeza representan una arista (fila) en la tabla de aristas.

• No hay flechas de doble punta

• Los números en la sombra amarilla son los identificadores de las aristas.

Dos pares de aristas comparten los mismos nodos finales y no se utiliza la columna reverse_cost.

• Las aristas \({2 \rightarrow 3, 3 \rightarrow 2}\) se representan con dos aristas \(id=203\) y \(id=302\) respectivamente.

• Edges \({3 \rightarrow 4, 4 \rightarrow 3}\) are represented with two edges \(id=304\) and \(id=403\) respectively.

El grafo puede crearse del siguiente modo:

CREATE TABLE edges_unique (
    id BIGINT,
    source BIGINT,
    target BIGINT,
    cost FLOAT,
    geom geometry
);
CREATE TABLE
INSERT INTO edges_unique (id, source, target, cost, geom) VALUES
  (102, 1, 2, 1, ST_MakeLine(ST_POINT(0,  2), ST_POINT(2,  2))),
  (104, 1, 4, 1, ST_MakeLine(ST_POINT(0,  2), ST_POINT(0,  0))),
  (301, 3, 1, 1, ST_MakeLine(ST_POINT(2,  0), ST_POINT(0,  2))),
  (203, 2, 3, 1, ST_MakeLine(ST_POINT(2,  2), ST_POINT(2,  0))),
  (304, 3, 4, 1, ST_MakeLine(ST_POINT(2,  0), ST_POINT(0,  0))),
  (302, 3, 2, 1, ST_MakeLine(ST_POINT(2,  0), ST_POINT(2,  2))),
  (403, 4, 3, 1, ST_MakeLine(ST_POINT(0,  0), ST_POINT(2,  0)));

Gráfico lineal de un grafo dirigido representado con aristas únicas

SELECT seq, source, target, cost, reverse_cost
FROM pgr_lineGraph(
  'SELECT id, source, target, cost FROM edges_unique',
  true);
 seq | source | target | cost | reverse_cost
-----+--------+--------+------+--------------
   1 |    102 |    203 |    1 |           -1
   2 |    104 |    403 |    1 |           -1
   3 |    203 |    301 |    1 |           -1
   4 |    203 |    304 |    1 |           -1
   5 |    301 |    102 |    1 |           -1
   6 |    301 |    104 |    1 |           -1
   7 |    302 |    203 |    1 |            1
   8 |    304 |    403 |    1 |            1
   9 |    403 |    301 |    1 |           -1
  10 |    403 |    302 |    1 |           -1
(10 rows)

• El resultado es un grafo dirigido.

• Para \(seq=7\) desde \(203 \leftrightarrow 302\) representan dos aristas.

• Para \(seq=8\) desde \(304 \leftrightarrow 403\) representan dos aristas.

• Todos los demás valores de seq representan una arista.

• Los valores cost y reverse_cost representan la existencia de la arista.

  • Cuando es positivo: la arista existe.

  • Cuando es negativo: la arista no existe.

Ver también

• wikipedia: Grafo lineal

• mathworld: Line Graph

• Datos Muestra

Índices y tablas

• Índice

• Página de Búsqueda