GSOC 2025: New function sloanOrdering to be added in pgRouting

[bipashabg]

pgr_sloanOrdering():

sloanOrdering(): Sloan ordering is an algorithm for profile and wavefront reduction of sparse matrices. The algorithm generates an optimal vertex ordering that reduces the profile and bandwidth of a graph, improving the efficiency of matrix operations, finite element analysis, and graph-based computational methods. The Sloan algorithm works by selecting a starting vertex and using a pseudo-peripheral node strategy to systematically reorder graph vertices, with a time complexity of O(V + E) and space complexity of O(V), where V is the number of vertices and E is the number of edges. This implementation will enhance pgRouting's capabilities in graph optimization, benefiting with sparse graph representations.

The algorithm:

• Uses a priority queue based on degree and distance from the goal.
• Assigns node orderings that minimize the matrix bandwidth.
• Supports undirected graphs.

Signature:

• sloanOrdering()

pgr_sloanOrdering(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 order.