Supported versions:

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.4.0
- Usa cost y reverse_cost en la consulta interna
- Los resultados son ordenados
- Funciona para grafos no dirigidos.
- Nueva firma
  - pgr_maxCardinalityMatch(text) regresa solamente la columna edge.
- Deprecated signature
  - pgr_maxCardinalityMatch(text,boolean)
    - directed => false when used.
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)

REGRESA CONJUNTO DE (edge)

OR EMPTY SET

Ejemplo:: Using all edges.

SELECT * FROM pgr_maxCardinalityMatch(
  'SELECT id, source, target, cost, reverse_cost FROM edges');
 edge
------
    1
    5
    6
   13
   14
   16
   17
   18
(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.
`cost`	FLOTANTES		Un valor positivo representa la existencia de la arista (`source`, `target`).
`reverse_cost`	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
`edge`	`BIGINT`	Identificador de la arista en la consulta original.

Ver también¶

Índices y tablas