Supported versions:

pgr_maxCardinalityMatch¶

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

_images/boost-inside.jpeg — Adentro: Boost Graph¶

Disponibilidad

Version 3.3.3
- directed optional parameter ignored and removed from the documentation as the algorithm works only on undirected graphs
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

Descripción¶

Las principales características son:

Funciona para grafos no dirigidos.
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.
Tiempo de ejecución: \(O( E*V * \alpha(E,V))\)
- \(\alpha(E,V)\) es inverso a Ackermann function.

Firmas¶

pgr_maxCardinalityMatch(SQL de aristas)

RETURNS SET OF (seq, edge_id, source, target)

OR EMPTY SET

Ejemplo:: Using all edges.

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

Parámetros¶

Parámetro	Tipo	Descripción
SQL de aristas	`TEXT`	SQL de aristas descritas más adelante.

Consultas Internas¶

SQL aristas¶

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

Columna	Tipo	x Defecto	Descripción
`id`	ENTEROS		Identificador de la arista.
`source`	ENTEROS		Identificador del primer vértice de la arista.
`target`	ENTEROS		Identificador del segundo vértice de la arista.
`going`	FLOTANTES		Un valor positivo representa la existencia de la arista (`source`, `target`).
`coming`	FLOTANTES	-1	Un valor positivo representa la existencia de la arista (`target`, `source`)

Donde:

ENTEROS:: SMALLINT, INTEGER, BIGINT
FLOTANTES:: SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Columnas de Resultados¶

Columna	Tipo	Descripción
`seq`	`INT`	Valor secuencial a partir de 1.
`edge`	`BIGINT`	Identificador de la arista en la consulta original.
`source`	`BIGINT`	Identifier of the first end point of the edge.
`target`	`BIGINT`	Identifier of the second end point of the edge.

Ver también¶

Índices y tablas