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))\)

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