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.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 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))\)
- \(\alpha(E,V)\) es inverso a Ackermann function.

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.

Ver también¶

Índices y tablas