[PENDING] GSOC 2025: New function minDegreeOrdering to be added in pgRouting Functionality/experimental GSoC ordering

[wifiBlack]

pgr_minDegreeOrdering():

minDegreeOrdering(): In numerical linear algebra, the MinDegree ordering is a heuristic used to reduce the amount of fill-in during sparse matrix factorization, such as Cholesky decomposition for symmetric matrices. When eliminating variables in a sparse system, new nonzero entries—called fill-ins—can appear in positions that were originally zero, increasing storage and computation costs. The minimum degree approach attempts to reorder the vertices (or equivalently, the rows and columns of the matrix) so that, at each elimination step, the vertex with the smallest degree is removed first, thereby reducing potential fill-in.

Main characteristics of the function:

• The implementation targets undirected graphs.
• The algorithm is a heuristic; finding the true optimal ordering is NP-complete.
• The time complexity is: (O(|V| log |V| + |E|))
  • where (|V|) is the number of vertices,
  • (|E|) is the number of edges.

Signature:

• minDegreeOrdering()

pgr_minDegreeOrdering(Edges SQL)

Returns set of (seq, node)
OR EMPTY SET

Parameters:

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

Inner Query:

Edges SQL: It should be an 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		Weight of the edge (source, target). When negative: edge (source, target) does not exist on the graph.
reverse_cost	ANY-NUMERICAL	-1	Weight of the edge (target, source). When negative: edge (target, source) does not exist on the graph.

Where:
ANY-INTEGER = SMALLINT, INTEGER, BIGINT
ANY-NUMERICAL = SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Result Columns:

Returns SET OF (seq, node)

Column	Type	Description
seq	BIGINT	Sequence of the order starting from 1.
node	BIGINT	New ordering in reverse order.

[wifiBlack]

❗️Note (WIP):

This function is currently marked as Work in Progress. The Boost side implementation is not fully functional yet, so the related PR cannot be merged at this stage. Further debugging and fixes are required before moving it forward.