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

_images/boost-inside.jpeg

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.

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