pgr_maxCardinalityMatch

pgr_maxCardinalityMatch — Calcula una coincidencia de cardinalidad máxima en un grafo.

_images/boost-inside.jpeg

Adentro: Boost Graph

Disponibilidad

  • Versión 3.0.0

    • Función oficial

  • Versión 2.5.0

    • Renombrado de pgr_maximumCardinalityMatching

    • Función propuesta

  • Versión 2.3.0

    • Nueva función Experimental

Soporte

Descripción

Las características principales son:

  • Un conjunto de aristas coincidente o independiente en un grafo es un conjunto de aristas sin vértices comunes.

  • Una coincidencia máxima es una coincidencia que contiene el mayor número posible de aristas.

    • Puede haber muchas coincidencias máximas.

    • Calcula una posible coincidencia máxima de cardinalidad en un grafo.

  • El grafo puede ser dirigido o no dirigido.

  • Tiempo de ejecución: \(O( E*V * \alpha(E,V))\)

Firmas

pgr_maxCardinalityMatch(Edges SQL [, directed])

RETURNS SET OF (seq, edge_id, source, target)
OR EMPTY SET
Ejemplo

Para un grafo no dirigido

SELECT * FROM pgr_maxCardinalityMatch(
    'SELECT id, source, target, cost AS going, reverse_cost AS coming FROM edge_table',
    directed := false
);
 seq | edge | source | target
-----+------+--------+--------
   1 |    1 |      1 |      2
   2 |    3 |      3 |      4
   3 |    9 |      6 |      9
   4 |    6 |      7 |      8
   5 |   14 |     10 |     13
   6 |   13 |     11 |     12
   7 |   17 |     14 |     15
   8 |   18 |     16 |     17
(8 rows)

Parámetros

Parámetro

Tipo

Valores predeterminados

Descripción

edges_sql

TEXT

Consulta SQL como se describió anteriormente.

dirigido

BOOLEAN

true

Determina el tipo del grafo. - En caso de “”true”” el grafo se considera Directed - En caso de “”false”” el grafo se considera como Undirected.

Consulta interna

Edges SQL

Una consulta SQL, que debe regresar un conjunto de filas con las siguientes columnas:

Columna

Tipo

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.

ir

ANY-NUMERIC

Un valor positivo representa la existencia de la arista (source, target).

venir

ANY-NUMERIC

Un valor positivo representa la existencia de la arista (target, source).

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERIC

SMALLINT, INTEGER, BIGINT, REAL FLOAT

Columnas de Resultados

Columna

Tipo

Descripción

seq

INT

Valor secuencial a partir de 1.

arista

BIGINT

Identificador de la arista en la consulta original.

origen

BIGINT

Identificador del primer punto final de la arista.

objetivo

BIGINT

Identificador del segundo punto final de la arista.