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

    • Es posible que el nombre no cambie. (Pero todavía puede)

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

    • Es posible que 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

    • Promoted to proposed signature

  • Versión 3.2.0

    • New experimental signature

Descripción

Sequential vertex coloring algorithm is a graph coloring algorithm in which color identifiers are assigned to the vertices of a graph in a sequential manner, such that no edge connects two identically colored vertices.

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)

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

Edges SQL

TEXT

Edges SQL as described below.

Inner Queries

SQL de aristas

Columna

Tipo

x Defecto

Descripción

id

ANY-INTEGER

Identificador de la arista.

source

ANY-INTEGER

Identificador del primer vértice de la arista.

target

ANY-INTEGER

Identificador del segundo vértice de la arista.

cost

ANY-NUMERICAL

Weight of the edge (source, target)

reverse_cost

ANY-NUMERICAL

-1

Weight of the edge (target, source)

  • When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

FLOTANTES:

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