GSoC 2026 Week 10 Report: Implementation of Planar Face Extraction and K-Core Decomposition Algorithms to pgRouting

Initiatives Google Summer of Code
1

Md Sakir Ahmed
Github id: sakirr05
Mentors: @cvvergara, @robe
Organization: OSGeo / pgRouting
OSGeo Profile: OSGeo Profile Link
Project Wiki: Github Wiki Link
Repository: Repo Link

Hello everyone,

This is my tenth weekly report of Official coding period for GSoC 2026

Week 10 Report (2 august ~ 9 august)

What did I get done this week?

pgr_planarFaces - PR #614:

  • Added pgtap tests checking the face count actually satisfies Euler’s formula, V - E + F = 2 on a connected subgraph
  • While writing them found test 4 was wrong. It said “Triangle has 6 rows (2 faces x 3 edges)” but edges 8, 10, 12 are 7-11, 7-8, 8-12, which is an open path not a triangle, it has 1 face not 2. Row count of 6 was right for the wrong reason, fixed the description
  • Checked the numbers by hand on a few subgraphs first: edges 8,10,12 gives V=4 E=3 F=1, id < 10 gives V=9 E=9 F=2, full graph gives V=17 E=18 F=7
  • The full graph works out to 6 not 2 because it has 3 components (confirmed with pgr_connectedComponents), the traversal walks the outer face of each component separately so it generalises to V - E + F = 2C
  • Added tests for both the connected and disconnected case, documented the formula in the rst. pgtap went 8 → 10

pgr_coreNumbers - PR #616:

  • Self loop fix: a vertex whose only edge was a self loop was coming back as core 2, because boost counts a self loop as degree 2 on an undirected graph. That is wrong for k-core since a k-core needs real neighbours. Added a filter to drop self loops before peeling, so a self-loop-only vertex now returns no result and a self loop next to a real edge no longer inflates the core number

  • Updated the pgtap test for that case and documented the corrected behaviour in the rst

  • Mentor’s @cvvergara and @robe did a live demo folding pgr_coreNumbers into the shared coloring_process.h / coloring_driver.cpp, the same pattern already used for coloring and components. Went through it step by step on my own code: switched coreNumbers.c to use coloring_process.h, added CORENUMBERS to the enum and to get_name, joined the self loop removal, the insert_min_edges_no_parallel call and a case CORENUMBERS into coloring_driver.cpp

  • Removed the now unused coreNumbers_process.cpp, coreNumbers_process.h, coreNumbers_driver.cpp, coreNumbers_driver.hpp, fixed CMakeLists.txt after

  • Verified none of the other functions sharing coloring_driver.cpp broke: makeConnected, connectedComponents, biconnectedComponents, strongComponents, sequentialVertexColoring, bipartite, edgeColoring all still return correct results

  • Synced with pgrouting/develop along the way, merged clean, no conflicts

Am I blocked on anything?

No

References:

1] Link to wiki page:
wiki page

2] Link to github repository:
github repository

3] Link to pull requests:
- PR #616
- PR #614