pgr_bipartite -Experimental

pgr_bipartite — Si el grafo es bipartito, la función devuelve la identificación del vértice junto con el color (0 y 1); de lo contrario, devolverá un conjunto vacío. En particular, el algoritmo is_bipartite () implementado por Boost.Graph

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

Un grafo bipartito es un grafo con dos conjuntos de vértices que están conectados entre sí, pero no dentro de sí mismos. Un gráfico bipartito es posible si el color del gráfico es posible utilizando dos colores, de modo que los vértices de un conjunto se colorean con el mismo color.

Las características principales son:

• El algoritmo solo funciona en un grafo no dirigido.

• Los valores devueltos no están ordenados.

• El algoritmo comprueba si el gráfico es bipartito o no. Si es bipartito, devuelve el nodo junto con dos colores “0” y “1” que representa dos conjuntos diferentes.

• Si el grafo no es bipartito, el algoritmo devuelve un conjunto vacío.

• Tiempo de ejecución: \(O(V + E)\)

Firmas

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

RETURNS SET OF (vertex_id, color_id)
OR EMPTY SET

Ejemplo

El algoritmo pgr_bipartite con edge_sql como parámetro cuando el grafo es bipartito:

SELECT * FROM pgr_bipartite(
    $$SELECT id,source,target,cost,reverse_cost FROM edge_table$$
);
 vertex_id | color_id
-----------+----------
         1 |        0
         2 |        1
         3 |        0
         4 |        1
         5 |        0
         6 |        1
         7 |        0
         8 |        1
         9 |        0
        10 |        1
        11 |        0
        12 |        1
        13 |        0
        14 |        0
        15 |        1
        16 |        0
        17 |        1
(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: el borde (origen, destino) existe en el grafo. Cuando es negativo: el borde (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.

Ejemplo Adicional

Ejemplo

El gráfico cíclico de longitud impar no puede ser bipartito.

En el siguiente borde se hará de el subgrafo con vértices {1, 2, 5, 7, 8} un grafo cíclico de longitud impar.

INSERT INTO edge_table (source, target, cost, reverse_cost) VALUES
(1, 7, 1, 1);
INSERT 0 1

El nuevo grafo no es bipartito porque tiene un ciclo de longitud impar de 5 vértices. Las aristas en azul representan un ciclo de longitud impar.

SELECT * FROM pgr_bipartite(
    $$SELECT id,source,target,cost,reverse_cost FROM edge_table$$
);
 vertex_id | color_id
-----------+----------
(0 rows)

Ver también

• Boost: documentación del algoritmo is_bipartite

• Wikipedia: grafo bipartito

• Red Datos Muestra .

Índices y tablas

• Índice

• Página de Búsqueda