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 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 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 CONJUNTO DE (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
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¶

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.

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 .

Índices y tablas