Hello everyone,
With GSoC drawing to a close, I am sharing the final report of everything I worked on over the past three months. It has been a genuinely rewarding few months, and I am grateful for the time spent working alongside the pgRouting community and my mentors.
Title: Implementing Planar Face Extraction and K-Core Decomposition Algorithms for pgRouting
Organisation: pgRouting under the umbrella of OSGeo
Abstract: This GSoC project dealt with the implementation of two new structural graph algorithms in pgRouting, one in the planar family and one in the metrics family. The algorithms are described below:
pgr_planarFaces:
Given an undirected planar graph, this function computes a planar embedding and walks every face of that embedding,
returning each edge-face incidence as a row that says which face an edge borders and on which side. A face is a maximal connected region of the plane bounded by edges, which on a street network is simply the city block enclosed by the roads around it
because a fixed embedding gives every edge exactly two bordering faces, a graph with |E| edges produces 2|E| rows, and the face count obeys Euler’s formula, |V| - |E| + |F| = 2 on a connected planar graph and |V| - |E| + |F| = 2C on one with C components. It runs in O(V + E) and is built on the Boost Graph Library’s boyer_myrvold_planarity_test and planar_face_traversal.
pgr_coreNumbers:
This function assigns every vertex its core number,
the largest k for which that vertex still survives inside the k-core, the maximal subgraph where every vertex keeps at least k neighbours. It works by peeling away vertices whose degree drops below k and raising k until nothing is left, in O(E) time.
The result reads as a hierarchy of the network: core 1 picks out dead-ends and cul-de-sacs, core 2 picks out corridors and cycles, and core 3 and above marks the dense interior where alternate routes exist. Unlike the planar function this one is not available in Boost, so it was written from scratch following the Batagelj-Zaversnik degree-peeling algorithm, with Boost used only to hold the graph.
The two functions sit in different families and answer different questions, one about topology and one about hierarchy, but they compose well:
extracting the blocks of a street network and then ranking how deeply each intersection sits inside it are natural halves of the same urban analysis.
State of the Project Before GSoC:
The planar family contained only pgr_isPlanar and pgr_boyerMyrvold, both of which answer whether a graph is planar without ever exposing the faces of the embedding they compute, so the regions a planar network actually encloses were unreachable from SQL. The metrics family had pgr_betweennessCentrality, pgr_degree and pgr_bandwidth, all of which measure a vertex locally or by shortest paths, with nothing that described how deeply a vertex is embedded in the dense part of a network.
State of the Project After GSoC:
Both functions are complete. pgr_planarFaces returns the shared IID_t_rt type through its own planar_process and planar_driver pair, while pgr_coreNumbers returns II_t_rt and was folded into the existing coloring_process and coloring_driver pair, following the consolidation pattern my mentor demonstrated during the coding period. The deliverables include the C and C++ code, the SQL interface, full RST user documentation with worked examples and diagrams, documentation queries, and pgTAP suites covering empty input, self loops, parallel edges, disconnected graphs, higher cores and non-planar rejection.
Potential Future Work:
- Once both functions have had wider community testing, I would like to address whatever bugs and usability issues surface and work towards promoting them from experimental to official.
- The planar family gained several functions in this same cycle, so I would like to help settle a consistent process and driver arrangement across pgr_isPlanar, pgr_boyerMyrvold, pgr_planarFaces, pgr_makeMaximalPlanar and pgr_makeBiconnectedPlanar.
Links:
- Final Pull Requests:
- Function Request Issues: #3142 and #3143
- Intermediate Pull Requests
- Project Documentation Wiki Page
Being part of the GSoC and OSGeo communities has been a privilege. Beyond the two algorithms, what I take away is a much better sense of how a mature C++ codebase is actually organised, why shared process and driver layers matter, and how to verify a claim properly instead of assuming a passing test suite settles it. My thanks to my mentors and to everyone in the community for the steady guidance, the code reviews, and the patience with my questions throughout.
Thank you and Regards,
Md Sakir Ahmed