GSOC 2026: New function pgr_maxWeightedMatching to be added in pgRouting

[mayurgalhate]

pgr_maxWeightedMatching():

maxWeightedMatching(): Maximum weighted matching is an algorithm that finds a set of edges in a graph such that no two edges share a common vertex and the total sum of edge weights is maximized. Unlike maximum cardinality matching, this algorithm prioritizes the weight of edges over the number of matched pairs, making it useful in resource allocation, scheduling, and optimization problems where costs or profits are associated with pairings. This implementation uses the Boost Graph Library's maximum_weighted_matching algorithm with a time complexity of O(n³), where n is the number of vertices. This will enhance pgRouting's capabilities in weighted graph optimization problems.

The algorithm:

• Works on undirected graphs.
• Each vertex is matched with at most one other vertex.
• Maximizes the total sum of edge weights (not the number of matched edges).
• There may be many maximum weighted matchings; calculates one possible matching.
• Results are symmetric: the agg_cost of (u, v) is the same as for (v, u).
• Running time: O(n³) where n is the number of vertices.

Signature:

• maxWeightedMatching()

pgr_maxWeightedMatching(Edges SQL [, directed])

Returns set of (start_vid, end_vid, agg_cost)
OR EMPTY SET

Parameters

Parameter	Type	Description
Edges SQL	TEXT	Inner SQL query, as described below.

Optional Parameters

Parameter	Type	Default	Description
directed	BOOLEAN	false	Ignored. The algorithm always works on undirected graphs.

Inner Query

Edges SQL: An SQL query returning 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 endpoint vertex of the edge.
target	ANY-INTEGER		Identifier of the second endpoint vertex of the edge.
cost	ANY-NUMERICAL		Weight of the edge (source, target). When negative, the edge does not exist.
reverse_cost	ANY-NUMERICAL	-1	Weight of the edge (target, source). When negative, the edge does not exist.

Where:

• ANY-INTEGER = SMALLINT, INTEGER, BIGINT
• ANY-NUMERICAL = SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Result Columns

Returns SETOF (start_vid, end_vid, agg_cost).

Column	Type	Description
start_vid	BIGINT	Identifier of the first endpoint vertex of the matched edge.
end_vid	BIGINT	Identifier of the second endpoint vertex of the matched edge.
agg_cost	FLOAT	Weight of the matched edge.