• Supported versions:

pgr_sequentialVertexColoring - Experimental

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

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

• Las consultas utilizan la red Datos Muestra .

• Boost: Sequential Vertex Coloring algorithm documentation

• “Wikipedia: Coloración de grafos <https://en.wikipedia.org/wiki/Graph_coloring>`__

Índices y tablas

• Índice

• Página de Búsqueda