Contributor
Shobhit Chaurasia

Implement Cuthill-Mckee Ordering Boost Graph Library Algorithm for pgRouting


Mentors
Veenit Kumar, dkastl
Organization
OSGeo (Open Source Geospatial Foundation)
Technologies
c, postgresql, c++
Topics
geolocation, mapping, Graph Theory
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. This algorithm is from the class of Sparse Matrix Ordering of Boost Graph Library. It is used to speed up various computations. It is implemented in Boost Graph Library (BGL). 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 }.