pgr_bipartite -Experimental

pgr_bipartite — Disjoint sets of vertices such that no two vertices within the same set are adjacent.

_images/boost-inside.jpeg

Adentro: Boost Graph

Advertencia

Posible bloqueo del servidor

  • Estas funciones pueden crear un bloque 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

    • New experimental signature

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.

  • The algorithm checks graph is bipartite or not. If it is bipartite then it returns the node along with two colors 0 and 1 which represents two different sets.

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

RETURNS SET OF (vertex_id, color_id)
OR EMPTY SET
Ejemplo:

When the graph is bipartite

SELECT * FROM pgr_bipartite(
    $$SELECT id, source, target, cost, reverse_cost FROM edges$$
) ORDER BY vertex_id;
 vertex_id | color_id
-----------+----------
         1 |        0
         2 |        0
         3 |        1
         4 |        1
         5 |        0
         6 |        1
         7 |        0
         8 |        1
         9 |        0
        10 |        0
        11 |        1
        12 |        0
        13 |        0
        14 |        1
        15 |        1
        16 |        0
        17 |        1
(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.

Ejemplo Adicional

Ejemplo:

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

The edge \(5 \rightarrow 1\) will make subgraph with vertices \(\{1, 3, 7, 6, 5\}\) an odd length cyclic graph, as the cycle has 5 vertices.

INSERT INTO edges (source, target, cost, reverse_cost) VALUES
(5, 1, 1, 1);
INSERT 0 1

Edges in blue represent odd length cycle subgraph.

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

Ver también

Índices y tablas