<div dir="ltr"><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,47);font-family:-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji"">Hello everyone,</p><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,47);font-family:-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji"">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 experience and great learning, working with the pgRouting community and mentors. This report follows the guidelines set by <a href="https://developers.google.com/open-source/gsoc/help/work-product" rel="nofollow" style="box-sizing:border-box;background-color:transparent;text-decoration-line:none">Google</a> and <a href="https://lists.osgeo.org/pipermail/soc/2022-September/004962.html" rel="nofollow" style="box-sizing:border-box;background-color:transparent;text-decoration-line:none">OSGeo GSoC Admins</a>.</p><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,47);font-family:-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji""><span style="box-sizing:border-box;font-weight:600">Title:</span> Implement Cuthill-Mckee Ordering Algorithm for pgRouting by the Boost Graph Library</p><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,47);font-family:-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji""><span style="box-sizing:border-box;font-weight:600">Organisation:</span> pgRouting under OSGeo</p><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,47);font-family:-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji""><span style="box-sizing:border-box;font-weight:600">Abstract:</span> This GSoC project dealt with the implementation of one new Graph algorithm in pgRouting. The algorithm is described below:</p><ul style="box-sizing:border-box;padding-left:2em;margin-top:0px;margin-bottom:16px;color:rgb(36,41,47);font-family:-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji""><li style="box-sizing:border-box"><span style="box-sizing:border-box;font-weight:600">Cuthill-Mckee Ordering:</span> It 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. This algorithm is from the class of Sparse Matrix Ordering of Boost Graph Library.</li></ul><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,47);font-family:-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji"">It is used in a linear system of equations, can be used to reduce the size needed to store the sparse matrix, improve the usage of distributed memory, enhance data locality, in constraint satisfaction problems, etc. It is implemented in Boost Graph Library (BGL) as <a href="https://www.boost.org/doc/libs/1_78_0/libs/graph/doc/cuthill_mckee_ordering.html" rel="nofollow" style="box-sizing:border-box;background-color:transparent;text-decoration-line:none"><code style="box-sizing:border-box;font-family:ui-monospace,SFMono-Regular,"SF Mono",Menlo,Consolas,"Liberation Mono",monospace;padding:0.2em 0.4em;margin:0px;border-radius:6px">boost::cuthill_mckee_ordering</code></a>. It is applicable for <span style="box-sizing:border-box;font-weight:600">undirected</span> graphs. It has a time complexity of O(m log(m)|V|) where m = max { degree(v) | v in V }.</p><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,47);font-family:-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji""><span style="box-sizing:border-box;font-weight:600">State of the Project Before GSoC:</span> pgRouting currently does not have this algorithm implemented. A single standard function does not exist for this ordering algorithm. This algorithm will be the first one from the Sparse Matrix Ordering family.</p><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,47);font-family:-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji""><span style="box-sizing:border-box;font-weight:600">The addition that my project brought to pgRouting:</span> The deliverables are code, documentation, documentation tests, and the pgTAP tests of the function.</p><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,47);font-family:-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji""><span style="box-sizing:border-box;font-weight:600">Potential Future Work:</span></p><ul style="box-sizing:border-box;padding-left:2em;margin-top:0px;margin-bottom:16px;color:rgb(36,41,47);font-family:-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji""><li style="box-sizing:border-box">The implementation of Cuthill-Mckee Ordering completes one algorithm out of five algorithms of the Boost Graph Library in pgRouting. In future, we can implement <code style="box-sizing:border-box;font-family:ui-monospace,SFMono-Regular,"SF Mono",Menlo,Consolas,"Liberation Mono",monospace;padding:0.2em 0.4em;margin:0px;border-radius:6px">King Ordering</code>, <code style="box-sizing:border-box;font-family:ui-monospace,SFMono-Regular,"SF Mono",Menlo,Consolas,"Liberation Mono",monospace;padding:0.2em 0.4em;margin:0px;border-radius:6px">Sloan Ordering</code>, <code style="box-sizing:border-box;font-family:ui-monospace,SFMono-Regular,"SF Mono",Menlo,Consolas,"Liberation Mono",monospace;padding:0.2em 0.4em;margin:0px;border-radius:6px">Minimum Degree Ordering</code>, etc.</li></ul><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,47);font-family:-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji"">Cuthill-Mckee Ordering has 3 versions defined in the Boost Graph Library. I have implemented the most practical version which is version 2. There are still left version 1 and version 3. If I will get time then I will definitely implement version 1 myself. It basically lets the user choose the starting vertex i.e. we have to give the starting vertex in the query of the Cuthill-Mckee ordering function. Whereas, version 2 finds the starting vertex itself.</p><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,47);font-family:-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji""><span style="box-sizing:border-box;font-weight:600">Links:</span></p><ul style="box-sizing:border-box;padding-left:2em;margin-top:0px;margin-bottom:16px;color:rgb(36,41,47);font-family:-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji""><li style="box-sizing:border-box"><p style="box-sizing:border-box;margin-top:16px;margin-bottom:16px"><span style="box-sizing:border-box;font-weight:600">Tags:</span></p><ul style="box-sizing:border-box;padding-left:2em;margin-top:0px;margin-bottom:0px"><li style="box-sizing:border-box">Cuthill-Mckee Ordering (2022-shobhit162-cuthillMckeeOrdering-function): <a href="https://github.com/pgRouting/GSoC-pgRouting/releases/tag/2022-shobhit162-cuthillMckeeOrdering-function" style="box-sizing:border-box;background-color:transparent;text-decoration-line:none">https://github.com/pgRouting/GSoC-pgRouting/releases/tag/2022-shobhit162-cuthillMckeeOrdering-function</a></li></ul></li><li style="box-sizing:border-box;margin-top:0.25em"><p style="box-sizing:border-box;margin-top:16px;margin-bottom:16px"><span style="box-sizing:border-box;font-weight:600">Pull Requests:</span></p><ul style="box-sizing:border-box;padding-left:2em;margin-top:0px;margin-bottom:0px"><li style="box-sizing:border-box"><p style="box-sizing:border-box;margin-top:16px;margin-bottom:16px"><span style="box-sizing:border-box;font-weight:600">Final Pull Request:</span> <a href="https://github.com/pgRouting/pgrouting/pull/2364" style="box-sizing:border-box;background-color:transparent;text-decoration-line:none">(#2364)</a> Experimental Function - cuthillMckeeOrdering (<a href="https://github.com/pgRouting/pgrouting/pull/2364" style="box-sizing:border-box;background-color:transparent;text-decoration-line:none">https://github.com/pgRouting/pgrouting/pull/2364</a>).</p></li><li style="box-sizing:border-box;margin-top:0.25em"><p style="box-sizing:border-box;margin-top:16px;margin-bottom:16px"><span style="box-sizing:border-box;font-weight:600">Intermediate pull requests:</span> <a href="https://github.com/pgRouting/GSoC-pgRouting/pulls?q=is%3Apr+author%3Ashobhit162" style="box-sizing:border-box;background-color:transparent;text-decoration-line:none">https://github.com/pgRouting/GSoC-pgRouting/pulls?q=is%3Apr+author%3Ashobhit162</a></p></li></ul></li><li style="box-sizing:border-box;margin-top:0.25em"><p style="box-sizing:border-box;margin-top:16px;margin-bottom:16px"><span style="box-sizing:border-box;font-weight:600">Project Documentation (Wiki Page):</span> <a href="https://github.com/pgRouting/pgrouting/wiki/GSoC-2022-Implement-Cuthill-Mckee-Ordering-Algorithm-for-pgRouting-by-the-Boost-Graph-Library" style="box-sizing:border-box;background-color:transparent;text-decoration-line:none">https://github.com/pgRouting/pgrouting/wiki/GSoC-2022-Implement-Cuthill-Mckee-Ordering-Algorithm-for-pgRouting-by-the-Boost-Graph-Library</a></p></li></ul><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,47);font-family:-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji""><span style="box-sizing:border-box;font-weight:600">Images:</span></p><ul style="box-sizing:border-box;padding-left:2em;margin-top:0px;margin-bottom:16px;color:rgb(36,41,47);font-family:-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji""><li style="box-sizing:border-box"><span style="box-sizing:border-box;font-weight:600">cuthillMckeeOrdering:</span> <a href="https://drive.google.com/file/d/1MwY9RagANABOTdctxyOxAKu3n7c7T7Ie/view?usp=sharing" rel="nofollow" style="box-sizing:border-box;background-color:transparent;text-decoration-line:none">https://drive.google.com/file/d/1MwY9RagANABOTdctxyOxAKu3n7c7T7Ie/view?usp=sharing</a></li></ul><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,47);font-family:-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji""><span style="box-sizing:border-box;font-weight:600">Media:</span></p><ul style="box-sizing:border-box;padding-left:2em;margin-top:0px;margin-bottom:16px;color:rgb(36,41,47);font-family:-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji""><li style="box-sizing:border-box"><span style="box-sizing:border-box;font-weight:600">Slide Demonstration:</span> <a href="https://docs.google.com/presentation/d/1zaQNMn-A8hT8l-9tK0krTOzF8JADkCtzVN_oSNfoRFo/edit?usp=sharing" rel="nofollow" style="box-sizing:border-box;background-color:transparent;text-decoration-line:none">https://docs.google.com/presentation/d/1zaQNMn-A8hT8l-9tK0krTOzF8JADkCtzVN_oSNfoRFo/edit?usp=sharing</a></li></ul><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,47);font-family:-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji"">I am so glad to be a part of the amazing GSoC and OSGeo communities. I have learned a lot during this period and I am sure that it will help me in my future development journey. I would be happy if my code proves beneficial to the community. Last but not the least, thank you everyone for the support!</p><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,47);font-family:-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji"">Thanks and Regards,</p><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,47);font-family:-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji"">Shobhit Chaurasia</p></div>