pgr_sequentialVertexColoring - Propuesto

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

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.3.0

    • Promovido a firma propuesta

  • Versión 3.2.0

    • Nueva firma 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 conecte dos vértices de colores idénticos.

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(SQL de aristas)
Regresa el conjunto de (vertex_id, color_id)
O CONJUNTO VACÍO
Ejemplo:

Coloración de grafos de pgRouting Datos Muestra

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

Parámetros

Parámetro

Tipo

Descripción

SQL de aristas

TEXT

SQL de aristas descritas más adelante.

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 (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