GSoC 2026 : Final Report | Implementing Maximum Weighted Matching Algorithm to pgRouting

Initiatives Google Summer of Code
1

Hello everyone,

With GSoC coming to an end, I hereby present my final report of the work I have done over the past three months. It has been an amazing learning experience and a great time working with the pgRouting community and mentors.

Title: Implementing Maximum Weighted Matching Algorithm to pgRouting from the Boost Graph Library

Organisation: pgRouting under the umbrella of OSGeo

Abstract: This GSoC project dealt with the implementation of one new graph algorithm in pgRouting. The algorithm is described below:

  • Maximum Weighted Matching: It is an algorithm that finds a matching in an undirected graph with the maximum possible total edge weight, where no two selected edges share a common vertex. The implementation uses the Boost Graph Library’s maximum weighted matching algorithm and returns the selected matching edges along with their associated costs. The algorithm has a time complexity of O(V³) and a space complexity of O(V + E), where V is the number of vertices and E is the number of edges. This addition enhances pgRouting’s capabilities for solving weighted graph matching and optimization problems.

It is implemented in Boost Graph Library (BGL) as boost::maximum_weighted_matching

State of the Project Before GSoC: pgRouting did not have a Maximum Weighted Matching algorithm implemented. The project lacked a built-in function for finding a maximum_weighted_matching in an undirected graph.

State of the Project After GSoC: The deliverables include the implementation of pgr_maxWeightedMatching, along with its documentation, documentation tests, and pgTAP tests. The new function provides maximum weighted matching capabilities within pgRouting.

Potential Future Work:

  • Continue improving pgr_maxWeightedMatching() by addressing potential bugs, edge cases, and usability issues identified through community feedback and extended testing.
  • Explore optimizations to improve the algorithm’s performance and memory usage for larger graphs.
  • Investigate support for additional graph configurations and matching use cases to expand the applicability of pgr_maxWeightedMatching().
  • Explore parallel or performance-oriented improvements where applicable to make weighted matching more efficient for large-scale graph processing.

Links:

I am so grateful to be a part of the amazing GSoC and OSGeo communities. I have learned a massive amount during this program, which has helped me improve my C++ architecture skills, my understanding of the Boost Graph Library, and how to effectively contribute to open source. Last but not least, a huge thank you to my mentors and the entire community for the continuous support, guidance, and helpful communication!

Thank you and Regards,

Mayur Galhate