Skip to content

GSoC 2025 Sloan Ordering Algorithm

Jump to bottom Edit New page
Bipasha Gayary edited this page Jun 23, 2025 · 16 revisions

Table of Contents

Proposal

Brief Description

The project aims to add the following algorithm to in pgRouting during GSoC 2024:

  • Sloan Ordering

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.

State of the Project Before GSoC

The absence of the Sloan ordering algorithm creates a functionality gap for users working with large network problems where matrix ordering significantly impacts computational efficiency. Current workarounds require users to export data to external tools, apply ordering algorithms, and re-import results, breaking workflow continuity and efficiency. Some proprietary GIS solutions include matrix ordering capabilities, but no open-source spatial database extension currently offers this functionality. The project aligns with pgRouting's roadmap for expanding advanced graph analysis capabilities beyond basic routing functions.

Deliverables

  • Fully implemented Sloan ordering algorithm
  • PostgreSQL/pgRouting integration
  • Comprehensive documentation
  • Performance benchmarks
  • Extensive test suite
  • Usage examples and tutorials plus prepare wiki report.

Detailed Proposal

Detailed Proposal Link (Google Doc)

Participants

Title GitHub Handle Name
1st Mentor @cvvergara Vicky Vergara
2nd Mentor @robe2 Regina Obe
3rd Mentor @iosefa Iosefa Percival
4th Mentor @sanak Ko Nagase
Student Developer @bipashabg Bipasha Gayary

Timeline

Community Bonding Period (May 8th- June 1st)

  • Introduce myself to the pgRouting mentor(s) and other community members
  • Set up my development environment
  • Familiarize myself with the pgRouting codebase and development practices
  • Learn pgTap and Boost Graph Library to help with the project
  • Setup wiki page for tracking weekly progress of the project
  • Participate in community discussions, meetings, or forums to engage with the project
  • Engage with PostgreSQL and PostGIS to gain more insight and comfort for working on the project

Week -1 and 0 (What have I got done?)

  • Set up my development environment
  • Familiarize myself with the pgRouting codebase and development practices
  • Go over pgTap practices and Boost Graph Library to help with the project and also go through the posgresql docs for the C-language functions.
  • Setup wiki page for tracking weekly progress of the project.
  • Update proposal for minor changes to ensure proper implementation of the function.
  • Attended two weekly meetings during the bonding period.
  • Created my own branch in the GSoC-pgRouting repository and laid out a folder structure where I would be writing the code in.

First Coding Period

Week 1

(2nd June- 8th June)

Original plan from proposal

  • Review Boost Graph Library's bandwidth calculation algorithms
  • Design data structures needed for pgr_bandwidth()

Revised plan

  • Create initial C++ implementation skeleton

  • sql/ordering/pgr_sloanOrdering.sql

  • sql/ordering/_pgr_sloanOrdering.sql

  • include/drivers/ordering_driver.hpp

  • include/process/ordering_process.h

  • src/ordering/ordering_driver.cpp

  • src/ordering/ordering_process.cpp

  • src/ordering/_sloanOrdering.c

What I got done?

  • Attended this week's weekly meeting on 2/06/2025

  • Added basic structure of the following files:-

  • sql/ordering/pgr_sloanOrdering.sql

  • sql/ordering/_pgr_sloanOrdering.sql

  • include/drivers/ordering_driver.hpp

  • include/process/ordering_process.h

  • src/ordering/ordering_driver.cpp

  • src/ordering/ordering_process.cpp

  • src/ordering/_sloanOrdering.c

  • Also updated CMakeLists.txt files.

Pull requests:

Week 2

(9th June- 15th June)

Original plan from proposal

  • Implement core Sloan ordering algorithm logic
  • Begin writing unit tests

Revised Plan

  • Fix naming of files.
  • Fix the licenses.
  • Fix compilation errors.
  • Add include/ordering/sloanOrdering.hpp file.
  • Update the CMakeLists.txt files.

What I got done?

  • Attended this week's weekly meetings on 8/06/2025 and 9/06/2025
  • Add include/ordering/sloanOrdering.hpp file.
  • Update the CMakeLists.txt files.
  • Fix naming of files.
    • [src/ordering] sloanOrdering_process.cpp -> ordering_process.cpp
    • [src/ordering] sloanOrdering_driver.cpp -> ordering_driver.cpp
    • [include/drivers] ordering_driver.hpp
    • [include/process] sloanOrdering_process.h -> ordering_process.h
  • Fix the licenses.
  • Fix compilation errors.

Pull requests:

Week 3

(9th June- 15th June)

Original plan from proposal

  • Set up continuous integration framework
  • Initial code review and mentor feedback

Revised Plan

  • Clear all compilation errors and warnings so far.
  • Fix parameters and data types according to Boost implementation.

What I got done?

  • Attended this week's weekly meeting on 16/06/2025
  • Clear all compilation errors and warnings so far.
  • Fix parameters and data types according to Boost implementation.
  • Update ordering_process.cpp file.
  • Fix code in SQL file.

Pull requests:

Week 4

(23rd June- 29th June)

Original plan from proposal

  • Refine Sloan ordering implementation
  • Develop PostgreSQL integration methods

Week 5

  • Create comprehensive test cases
  • Begin performance optimization

Week 6

  • Implement error handling and edge cases
  • Midpoint code review with mentors

Second Coding Period

Week 7

  • Implement weighted graph support
  • Add advanced configuration options

Week 8

  • Develop detailed user and developer documentation
  • Begin pgTAP test suite

Week 9

  • Prepare integration examples
  • Continue performance improvements

Week 10

  • Final code optimization
  • Comprehensive documentation review

Week 11

  • Create usage tutorials and examples
  • Final round of testing and bug fixing

Week 12

  • Prepare submission package
  • Final polish

Log of Pull Requests

Link to all the Pull Requests made in GSoC-pgRouting repository

Pull Request Description Date Status
https://github.com/pgRouting/GSoC-pgRouting/pull/440 Add my name into doc/src/pgRouting-introduction.rst 02-06-2025 Closed
https://github.com/pgRouting/GSoC-pgRouting/pull/442 GSoC 2025 Week-1 07-06-2025 Closed and Merged
https://github.com/pgRouting/GSoC-pgRouting/pull/446 GSoC 2025 Week-2 09-06-2025 Closed and Merged
https://github.com/pgRouting/GSoC-pgRouting/pull/451 GSoC 2025 Week-3 16-06-2025 Closed and Merged

Final Report

TBD

Potential Future Work:

TBD

Links:

  • Pull Requests:

    • Final Pull Request: TBD

    • Intermediate pull requests: TBD

References

  1. Boost sloan_ordering

  2. Parallelization of Reordering of Sparse Matrices

Contact: https://discourse.osgeo.org/c/pgrouting/pgrouting-dev

pgRouting Project

pgRouting Project

Quick Links

Clone this wiki locally