[SoC] GSoC-2022 Introduction: Shobhit Chaurasia- Implement Cuthill-Mckee Ordering Algorithm for pgRouting by the Boost Graph Library

shobhit chaurasia 000shobhitchaurasia at gmail.com
Mon May 30 09:07:48 PDT 2022


Hello Community Members,

I am Shobhit Chaurasia from Hindustan College of Science and Technology,
Mathura, India. I'm currently in my third year of Bachelor of Technology in
Computer Science. Here is my Github [1] and LinkedIn profile [2].

I would like to thank the OSGeo and pgRouting community and GSoC admins for
selecting me and giving me this opportunity to work as a Student Developer
in GSoC 2022.

I am going to work on the project "Implement Cuthill-Mckee Ordering Boost
Graph Library Algorithm to pgRouting" [3].
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.
This algorithm is from the class of Sparse Matrix Ordering of Boost Graph
Library.
It is implemented in Boost Graph Library (BGL) as Boost::Cuthill-Mckee [4].
It is applicable for undirected graphs. It has a time complexity of O(m
log(m)|V|) where m = max { degree(v) | v in V }.

I have done the following work as a part of the community bonding period
including this mail.

   - Created my GSoC project wiki page where all the weekly reports and
   final report will be documented [5].
   - Forked the pgRouting's GSoC-pgRouting repository [6] where I will be
   working and making PR and at the end, this will be merged to pgRouting [7].
   - Added the links to both the wiki pages and public repository on the
   accepted student's wiki page [8].
   - Read Google's GSoC students guide and OGGeo's specific instructions.

I request the community members to please provide some feedback or
suggestions on my project as it will improve the project's development and
my overall performance. Please have a look at my timeline for each week and
its respective proposed work and let me know if there are some mistakes.

I am super excited and looking forward to learning this summer with OSGeo
and pgRouting.

Thanks!
Shobhit Chaurasia

[1] https://github.com/shobhit162/
[2] https://www.linkedin.com/in/shobhit-chaurasia-8842531b6
[3] https://summerofcode.withgoogle.com/programs/2022/projects/4OxG2uIw
[4]
https://www.boost.org/doc/libs/1_78_0/libs/graph/doc/cuthill_mckee_ordering.html
[5]
https://github.com/pgRouting/pgrouting/wiki/GSoC-2022-Implement-Cuthill-Mckee-Ordering-Algorithm-for-pgRouting-by-the-Boost-Graph-Library
[6] https://github.com/shobhit162/GSoC-pgRouting
[7] https://github.com/pgRouting/pgrouting
[8] https://wiki.osgeo.org/wiki/Google_Summer_of_Code_2022_Accepted
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/soc/attachments/20220530/a993d190/attachment.htm>


More information about the SoC mailing list