GSoC 2026 Maximum Weighted Matching Algorithm - pgRouting/pgrouting GitHub Wiki
This project aims to implement the Maximum Weighted Matching Algorithm from the Boost Graph Library into pgRouting, is an algorithm for finding an optimal set of independent edges in a weighted graph such that the sum of their weights is maximized. The algorithm generates an optimal pairing of vertices that maximizes the total relationship value, improving the efficiency of resource allocation, fleet management, and complex assignment problems. The algorithm works by iteratively discovering augmenting paths and resolving odd-length cycles (using strategies like Edmonds' blossom shrinking) to systematically pair graph vertices, with a typical time complexity of O(V3 ) and space complexity of O(V + E), where V is the number of vertices and E is the number of edges. This implementation will enhance pgRouting's capabilities in combinatorial optimization, benefiting applications that require advanced pairing and relationship maximization.
Until now, maximum weighted matching has not been implemented in pgRouting. However, among the graph algorithms provided by the Boost C++ Libraries, no matching-related algorithm has been integrated into pgRouting so far.
- Implementation of pgr_maximumWeightedMatching().
- Code with clear and essential comments, following style guides and best practices.
- User documentation for the new function.
- Basic pgTap test cases.
- A wiki page detailing weekly progress.
- Detailed reports for the first and final evaluations.
| Title | GitHub Handle | Name |
|---|---|---|
| 1st Mentor | @krashish8 | Ashish Kumar |
| 2nd Mentor | @cvvergara | Vicky Vergara |
| Student Developer | @mayurgalhate | Mayur Galhate |
Note: in reverse order: the most recent is first
week 12
Dates: (August 10th β August 16th)
Proposed:
- Prepare and submit the final project report.
Plan for the week:
- TBD
- TBD
Report:
- foo
- bar
week 11
Dates: (August 3rd β August 9th)
Proposed:
- Preparing for Final Delivery
- Integrating to develop branch in the main repository
Plan for the week:
- TBD
- TBD
Report:
- foo
- bar
week 10
Dates: (July 27th β August 2nd)
Proposed:
- Fixing remaining bugs, test and documentation details
- Wiki page
Plan for the week:
- TBD
- TBD
Report:
- foo
- bar
week 9
Dates: (July 20th β July 26th)
Proposed:
- Developer and Userβs Documentation
- Suitable Query using sample data on pgrouting documentation.
Plan for the week:
- TBD
- TBD
Report:
- foo
- bar
week 8
Dates: (July 13th β July 19th)
Proposed:
- Internal tests for
pgr_maximumWeightedMatching() - No server crash test
- pgtAP Unit tests
Plan for the week:
- TBD
- TBD
Report:
- foo
- bar
week 7
Dates: (July 6h β July 12th)
Proposed:
- Work on the feedback as provided from the First Evaluation
- Bug fixing
- Prepare second coding period Synopsis
Plan for the week:
- TBD
- TBD
Report:
- foo
- bar
week 6
Dates: (June 29th β July 5th)
Proposed:
- Finalize the function and documentation
- Prepare report for first evaluation
Plan for the week:
- Complete the remaining implementation and documentation work.
- Prepare the evaluation report and review project progress.
Report:
- Worked on finalizing the implementation of the function.
- Updated and improved the project documentation.
- Prepared progress notes and report for the first evaluation.
week 5
Dates: (June 22nd β June 28th)
Proposed:
- Create sql query examples
- Prepare for midterm evaluation
Plan for the week:
- Work on sample SQL queries for testing and documentation.
- Prepare project updates and progress for the midterm evaluation.
Report:
- Worked on creating sample SQL query examples.
- Prepared documentation and progress updates for the midterm evaluation.
- Reviewed current implementation and fixed minor issues.
week 4
Dates: (June 15th β June 21st)
Proposed:
- Finalize the data flow from SQL input to the C layer
- Write helper class and wrappers
- C driver to use Boost C++ function
Plan for the week:
- Complete the connection between SQL input and the C layer.
- Work on helper classes, wrappers, and Boost function integration.
Report:
- Worked on finalizing the connection between SQL input and the C layer.
- Started writing helper classes and wrapper functions.
- Began integrating the C driver with the Boost C++ implementation.
week 3
Dates: (June 8th β June 14th)
Proposed:
- Read data from User
- Start building the pipeline from SQL input to the C interface.
Plan for the week:
- Handle input data from SQL queries.
- Start connecting SQL input with the C code.
Report:
- Worked on reading input data from SQL queries.
- Started connecting the SQL layer with the C interface.
- Added basic data handling for graph inputs.
- Fixed build and compilation issues.
week 2
Dates: (June 1st β June 7th)
Proposed:
- Set up the initial framework for tests and documentation.
- Start implementing
pgr_maximumWeightedMatching()
Plan for the week:
- Create basic test files and documentation setup.
- Start coding
pgr_maximumWeightedMatching().
Report:
- Set up the initial testing framework.
- Added basic documentation structure for the new function.
- Started implementing
pgr_maximumWeightedMatching(). - Added the initial function skeleton and integrated it into the build system.
week 1
Dates: (May 25th β May 31th)
Proposed:
- Go through BGL concepts
- Design data structures needed for
pgr_maximumWeightedMatching()
Plan for the week:
- Create initial implementation skeleton and project structure
- Prepare source, header, SQL, documentation, and test files
- Set up directory structure for future development
- Update related
CMakeLists.txtfiles
Report:
- Reviewed BGL concepts related to weighted matching
- Explored pgRouting module structure and workflow
- Added initial structure for:
sql/maximum_weighted_matching/maximum_weighted_matching.sqlsql/maximum_weighted_matching/_maximum_weighted_matching.sqlinclude/drivers/maximum_weighted_matching/maximum_weighted_matching.hinclude/maximum_weighted_matching/maximum_weighted_matching.hppsrc/maximum_weighted_matching/maximum_weighted_matching_driver.cppsrc/maximum_weighted_matching/maximum_weighted_matching.cpp
- Prepared documentation and testing file structure
- Updated related
CMakeLists.txtfiles
Bonding period
- Introduce myself to the pgRouting mentors and community members.
- Set up my local development environment and tools.
- Get familiar with the pgRouting codebase and how development is done.
- Learn pgTap and the Boost C++ Libraries to support the project work.
- Create a wiki page to track weekly progress and updates.
- Take part in community chats, meetings, and discussions.
- Learn how PostgreSQL and PostGIS are used with pgRouting.
- Introduce myself to the pgRouting mentors and community members.
- Take part in community chats, meetings, and discussions.
- Create a wiki page to track weekly progress and updates.
- Set up my local development environment and tools.
- Get familiar with the pgRouting codebase and how development is done.
- foo
- bar
Link to all the Pull Requests made in GSoC-pgRouting repository
| Pull Request | Description | Date | Status |
|---|---|---|---|
| # 1604 | TBD | TBD | TBD |
TBD
TBD
- Links:
(i) Code Documentation:
TBD
(ii) Tags:
TBD
(iii) Pull Requests:
TBD
(iv) Wiki Pages:
TBD
- Images:
TBD
- Media:
TBD
- https://www.boost.org/doc/libs/latest/libs/graph/doc/maximum_weighted_matching.html
- https://www.boost.org/doc/libs/latest/libs/graph/example/weighted_matching_example.cpp
- https://www.boost.org/doc/libs/1_82_0/libs/graph/doc/index.html
- https://en.wikipedia.org/wiki/Maximum-weight_matching
- https://docs.pgrouting.org/latest/en/sampledata.html
- https://github.com/pgRouting/pgrouting