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.