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

    • Use cost and reverse_cost on the inner query

    • Results are ordered

    • Works for undirected graphs.

    • New signature

      • pgr_maxCardinalityMatch(text) returns only edge column.

    • 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.

    • Calculates one possible maximum cardinality matching in a graph.

  • Tiempo de ejecución: \(O( E*V * \alpha(E,V))\)

Firmas

pgr_maxCardinalityMatch(Edges SQL)
RETURNS SET OF (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 Aristas

TEXT

SQL 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

A positive value represents the existence of the edge (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