pgr_sequentialVertexColoring - Experimental

pgr_sequentialVertexColoring — Devuelve el color de vértice de un grafo no dirigido, utilizando un enfoque codicioso.

_images/boost-inside.jpeg

Adentro: Boost Graph

Advertencia

Posible bloqueo del servidor

  • Estas funciones pueden crear un bloqueo del servidor

Advertencia

Funciones experimentales

  • No son oficialmente de la versión actual.

  • Es probable que oficialmente no formen parte de la siguiente versión:

    • Las funciones no podrían hacer uso de ANY-INTEGER ni ANY-NUMERICAL

    • El nombre puede cambiar.

    • La firma (declaración de funciones) podría cambiar.

    • La funcionalidad puede cambiar.

    • Las pruebas de pgTap pueden estar ausentes.

    • Posiblemente necesite codificación c/c++.

    • Puede haber carencia de documentación.

    • Hay documentación que, en dado caso, podría ser necesario reescribir.

    • Ejemplos de documentación que puede ser necesario generar automáticamente.

    • Puede ser necesaria más retroalimentación por parte de la comunidad.

    • Puede depender de una función propuesta de pgRouting.

    • Podría depender de una función obsoleta de pgRouting

Disponibilidad

  • Versión 3.2.0

    • Nueva función experimental

Descripción

El algoritmo de Coloración de Vértices Secuenciales es un algoritmo de coloración de grafos en el que se asignan identificadores de color a los vértices de un grafo de forma secuencial, de modo que ninguna arista conecta dos vértices de color idéntico.

Las características principales son:

  • La implementación solo es aplicable a los grafos no dirigidos.

  • Proporciona el color que se asignará a todos los vértices presentes en el grafo.

  • Los valores de los identificadores de color se encuentran en el rango \([1, |V|]\)

  • El algoritmo intenta asignar el menor color posible a cada vértice.

  • El color de grafos eficientes es un problema NP-Hard, y por lo tanto, este algoritmo no siempre produce un coloración óptima. Sigue una estrategia expansiva recorriendo en iteración todos los vértices secuencialmente y asignando el color más pequeño posible que no sea utilizado por sus vecinos, a cada vértice.

  • Las filas devueltas se ordenan en orden ascendente del valor de vértice.

  • Tiempo de Ejecución de Coloración de Vértices Secuenciales: \(O(|V|*(d + k))\)

    • donde \(|V|\) es el número de vértices,

    • \(d\) es el grado máximo de los vértices en el grafo,

    • \(k\) es el número de colores utilizados.

Firmas

pgr_sequentialVertexColoring(Edges SQL) -- Experimental on v3.2

RETURNS SET OF (vertex_id, color_id)
OR EMPTY SET
Ejemplo

Coloración de grafos de pgRouting Datos Muestra

SELECT * FROM pgr_sequentialVertexColoring(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table
    ORDER BY id'
);
 vertex_id | color_id
-----------+----------
         1 |        1
         2 |        2
         3 |        1
         4 |        2
         5 |        1
         6 |        2
         7 |        1
         8 |        2
         9 |        1
        10 |        2
        11 |        1
        12 |        2
        13 |        1
        14 |        1
        15 |        2
        16 |        1
        17 |        2
(17 rows)

Parámetros

Parámetro

Tipo

Descripción

Edges SQL

TEXT

Consulta interna como se describe a continuación.

Consulta interna

Edges SQL

Una consulta SQL de un grafo no dirigido, que debería devolver un conjunto de filas con las siguientes columnas:

Columna

Tipo

Valores predeterminados

Descripción

id

ANY-INTEGER

Identificador de la arista.

origen

ANY-INTEGER

Identificador del primer punto final en el vértice de la arista.

objetivo

ANY-INTEGER

Identificador del segundo punto final en el vértice de la arista.

cost

ANY-NUMERICAL

  • Cuando es positivo: el borde (origen, destino) existe en el grafo.

  • Cuando es negativo: el borde (origen, desitno) no existe en el grafo.

reverse_cost

ANY-NUMERICAL

-1

  • Cuando es positivo: la arista (origen, destino) existe en el grafo.

  • Cuando es negativo: la arista (destino, origen) no existe en el grafo.

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Columnas de Resultados

Devuelve SET OF (vertex_id, color_id)

Columna

Tipo

Descripción

vertex_id

BIGINT

Identificador del vértice.

color_id

BIGINT

Identificador del color del vértice.

  • El valor mínimo de color es 1.

Ver también

Índices y tablas