pgr_maxCardinalityMatch

pgr_maxCardinalityMatch - Calculates a maximum cardinality matching in a graph.

images/boost-inside.jpeg

Boost Graph Inside

Availability

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

  • Version 3.0.0

    • Official function

  • Version 2.5.0

    • Renamed from pgr_maximumCardinalityMatching

    • Proposed function

  • Version 2.3.0

    • New Experimental function

Description

The main characteristics are:

  • Works for undirected graphs.

  • A matching or independent edge set in a graph is a set of edges without common vertices.

  • A maximum matching is a matching that contains the largest possible number of edges.

    • There may be many maximum matchings.

    • Calculates one possible maximum cardinality matching in a graph.

  • Running time: \(O( E*V * \alpha(E,V))\)

Signatures

pgr_maxCardinalityMatch( Edges SQL )
RETURNS SET OF (edge)
OR EMPTY SET
Example :

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)

Parameters

Parameter

Type

Description

Edges SQL

TEXT

Edges SQL as described below.

Inner Queries

Edges SQL

SQL query, which should return a set of rows with the following columns:

Column

Type

Default

Description

id

ANY-INTEGER

Identifier of the edge.

source

ANY-INTEGER

Identifier of the first end point vertex of the edge.

target

ANY-INTEGER

Identifier of the second end point vertex of the edge.

cost

ANY-NUMERICAL

A positive value represents the existence of the edge ( source , target ).

reverse_cost

ANY-NUMERICAL

-1

A positive value represents the existence of the edge ( target , source )

Where:

ANY-INTEGER :

SMALLINT , INTEGER , BIGINT

ANY-NUMERICAL :

SMALLINT , INTEGER , BIGINT , REAL , FLOAT

Result Columns

Column

Type

Description

edge

BIGINT

Identifier of the edge in the original query.

See Also

Indices and tables