Being a part of the Google Summer of Code Program, 2022

Implementation of Cuthill-Mckee Ordering Algorithm to pgRouting

Technologies Used: C, C++, Python, PostgreSQL, PostGIS, CMake, Sphinx, Doxygen, and Boost Graph Library

What is Google Summer of Code?

Google Summer of Code (GSoC) is a global annual program where Google accepts young contributors through an open-source coding project that the students choose themselves which is then published by a chosen mentoring open source organization during the summer. GSoC contributors work with an open-source organization on a 12+ week programming project under the guidance of mentors. Along with that, a stipend is also provided as an incentive.

How I prepared for GSoC:

It was like a dream come true. I’ve been working towards my goal of getting selected for the Google Summer of Code since 2019.

I also applied for GSoC in the year 2021 but wasn’t selected due to a late start. So, it’s crucial to start early and have an edge on other candidates. This time I began my preparations from the month of January.

Preparing for GSoC involves various stages. Firstly, we have to choose the organization which aligns with the tech stacks that we are good at. Then, we have to introduce ourselves in the public communication channel of that organization. The mentors are always there to guide us on how to get started by giving us small tasks or good first issues. Communication is key for GSoC. For choosing the idea, almost every organization publishes a possible idea list for the upcoming GSoC program. It’s good to choose the idea beforehand and start working on it. We have to build a proposal document which consists of many detailed sections on our chosen idea. Most importantly, it contains the timeline of the proposed work every week and how we are going to implement our idea. Along with earlier contributions, our proposal is the only judgment criteria for whether we will be selected or not.

About my Project and Organization:

You must be wondering what I am going to do in the Google Summer of Code this year. Let me give you a walkthrough of my project and all the technologies that I’ll be using and working on:

• We’ve all used Google Maps to get detailed information about geographic regions and sites around the world. Real-time traffic, route planning, finding the shortest distance between one place to another, all these functions are there in google maps. But, there are many alternatives present, such as OpenStreetMap, Pocket Earth, OsmAnd, Bing Maps, etc.

OpenStreetMap is a free, open source project which gives us a geographic database of the world. Its data is being used by various organizations such as OSGeo, the one in which I will be working on.

• Open Source Geospatial Foundation (OSGeo) is a non-profit organization that fosters the global adaptation of open geospatial technology and its collaborative development. OSGeo serves as an umbrella organization for GRASS GIS, PostGIS, pgRouting, etc.

I will be working for the pgRouting organization this summer.

pgRouting is a PostgreSQL / PostGIS extension for developing network routing applications, doing graph analysis and providing geospatial functionalities, and more.

It implements many algorithms, some of them are Floyd-Warshall, Johnson’s All Pair Shortest Path, A* Shortest Path, Dijkstra Algorithm, Driving Distance, K-Shortest Path, Traveling SalesPerson, Turn Restriction Path, Edge-Coloring, etc.

PostGIS is a spatial extender for the PostgreSQL DBMS but it lacks some functionalities such as doing analysis which involves constrained paths. pgRouting is a complement to PostGIS that allows us to do analysis using constrained paths.

• I am going to implement the Cuthill-Mckee Ordering Algorithm for pgRouting. This algorithm is provided in the Boost Graph Library. The Cuthill-Mckee Ordering is an algorithm used to reduce the bandwidth of a graph by reordering the indices assigned to each vertex. The vertices are basically assigned a breadth-first search order, except that at each step, the adjacent vertices are placed in the queue in order of increasing degree. Here, Bandwidth refers to the maximum distance between two adjacent vertices, with distance measured on a line upon which the vertices have been placed at unit intervals. This algorithm is applicable for undirected graphs. It has a time complexity of O(m log(m)|V|) where m = max { degree(v) | v in V }.

This algorithm is from the class of Sparse Matrix Ordering of Boost Graph Library. And as we all know that a sparse matrix is a matrix in which most of the elements are zero.

Adding this algorithm to pgRouting will result in more functionalities in pgRouting which will help the current and future users and developers to use and integrate it with other algorithms. Some of the benefits of this algorithm are, It is used to reduce the size needed to store the sparse matrix. Reordering a sparse matrix to reduce its bandwidth can speed up many sparse matrix computations for e.g In a linear system of equations let’s say A.x = B and if A is a sparse matrix then solving the equation becomes a challenging task. To overcome it, we convert the given sparse matrix A into a graph and apply the Cuthill-Mckee algorithm to reduce the bandwidth of the graph. So, it will become easier to solve the equation after we get a sparse matrix of reduced bandwidth. It is used to improve the usage of distributed memory. Recently, the bandwidth minimization problem is also being used in the compression of topological information from digital road networks.

• Some tools that I will be using are Cmake, Sphinx, and Doxygen. These all are building tools used to perfectly build the software. Cmake is a cross-platform free and open-source software for building automation, testing, and installation of software by using a compiler-independent method. Sphinx and Doxygen are documentation tools. Sphinx makes it easy to create intelligent and beautiful documentation using python. Whereas, Doxygen is a tool for generating documentation from annotated C++ sources.

My experience so far

It has been a rollercoaster ride so far. Apart from working on my technical skills I also had to work on my time management and communication skills.

Apart from academics and my work for the GSoC, I have been actively polishing my DSA and Competitive Programming skills through CodeChef and LeetCode.

After I have made my contribution to the GSoC, I’m considering becoming a mentor for the GSoC 2023 program for the pgRouting organization. I would be eager to mentor my juniors and fellow batchmates in the GSoC 2023 program.

At last, all I’d say is, that GSoC gives us a great learning curve and it helps us to get good opportunities in the future. It feels good when our code will be used by many developers and researchers around the world. After all, it’s all about Open Source!

Thanks for reading!

Shobhit Chaurasia