GSoC 2026 Planar Face Extraction and K‐Core Decomposition - pgRouting/pgrouting GitHub Wiki
This project aims to implement Planar Face Extraction and K-Core Decomposition algorithms from the Boost Graph Library into pgRouting. These algorithms extend pgRouting’s capabilities in structural graph analysis.
Planar face extraction identifies the bounded regions (faces) formed by edges in a planar graph, which is useful for applications such as road network partitioning and spatial analysis. K-core decomposition assigns a core number to each vertex, representing its level of connectivity within the graph, and is widely used in network analysis and clustering.
By integrating these algorithms, pgRouting will support more advanced graph analysis directly within PostgreSQL, enabling efficient processing of large-scale geospatial and network data.
Currently, pgRouting does not provide functions for planar face extraction or k-core decomposition. While planar face extraction algorithms is available in the Boost Graph Library also k-core decomposition would be implemented from sctratch with standalone function, they have not yet been integrated into pgRouting.
This project will bridge that gap by implementing these algorithms within pgRouting’s existing architecture and exposing them through SQL interfaces.
- Implementation of
pgr_planarFaces()function. - Implementation of
pgr_coreNumbers()function. - Integration with Boost Graph Library algorithms.
- SQL interface for both functions.
- User documentation for the new functions.
- pgTap test cases to ensure correctness and stability.
- A wiki page documenting weekly progress.
- Final and evaluation reports.
Delivered:
-
pgr_coreNumbers— pgrouting#3137 -
pgr_planarFaces— pgrouting#3138
| Title | GitHub Handle | Name |
|---|---|---|
| 1st Mentor | @cvvergara | Vicky Vergara |
| 2nd Mentor | @robe2 | Regina Obe |
| Student Developer | @sakirr05 | Md Sakir Ahmed |
Note: in reverse order: the most recent is first
week 12
Dates: (August 17 ~ August 23)
Proposed: Final project polishing, retrospective cleanup, and post-review integration validation.
-
Revised plan:
- Settle the process/driver architecture question for the planar family with the mentors
- Finish the Boost version proof of concept for both algorithms
- Run a full verification pass over both algorithms and fix whatever it turns up
- Open the final pull requests against
pgrouting/develop
-
Work Done:
- Architecture question:
- Asked on Discourse whether the process/driver pair is organised per family or per return type, since
pgr_planarFacesreturnsIID_t_rtandallpairs_processalready uses that type - @cvvergara answered that the return type is the organising unit: if an existing pair matches, use it; if none does, create one; and if two students independently need the same new type, both create their own and she consolidates later
- Checked
do_allpairsand found it dispatches withif (which == JOHNSON) {...} else {floydWarshall}rather than aswitch, and routes everything throughmatrix_to_tuple, which cannot shape face-traversal output.betweennessCentralityandboyerMyrvoldalso returnIID_t_rtand still have standalone drivers, soplanar_process/planar_driverstays as it is
- Asked on Discourse whether the process/driver pair is organised per family or per return type, since
- pgr_planarFaces #627:
- Corrected
pgr_isPlanarinplanar-family.rst: it was listed underofficial-startalthoughpgr_isPlanar.rstdeclares itself Experimental - Corrected the main sample-graph diagram. Edges 9 through 18 did not match the
edgestable: edge 9 was drawn as1 -- 9instead of11 -- 16, edge 10 as3 -- 12instead of7 -- 8, edge 18 as8 -- 12instead of13 -- 14. All 18 edges now matchsampledata, verified by diffing the diagram against a live query - Named the exact error raised on non-planar input,
ERROR: Graph is not planar, confirmed by running a K5 through the function - Removed non-ASCII quotes, fixed a duplicated word, and tightened the description
- Corrected
- pgr_coreNumbers #637:
- Corrected the 2-core vertex list in the full-graph example. It described the 2-core as vertices 6 through 12 plus 15, 16 and 17, but that range wrongly includes vertex 9. Vertex 9 hangs off vertex 8 by edge 14 alone, so it is peeled first and is core 1. The 2-core is 6, 7, 8, 10, 11, 12, 15, 16, 17, confirmed against the docquery result file
- Replaced three descriptive paragraphs with a bullet list
- Boost version proof of concept #625 and #636:
- Pinned
boost_minorto[55, 56, 57]so that 1.55 fails and proves 1.56 is genuinely the floor, matchingBOOST_MINIMUM_VERSIONinCMakeLists.txt - Switched the download from SourceForge to
archives.boost.ioafter finding that a SourceForge timeout in another PR was being read as a Boost incompatibility rather than an infrastructure failure
- Pinned
- Full verification pass before opening the final PRs:
- Both algorithms built clean against
pgrouting/develop, not just against their own integration branches - pgTap: 94/94 for
pgr_coreNumbers, 76/76 forpgr_planarFaces, each run ten times consecutively with zero backend crashes - docqueries passing, cpplint 0 findings, Sphinx
html-enbuild succeeded with no warnings - Checked the results independently of the test suite:
pgr_planarFacessatisfies the documented|V| - |E| + |F| = 2C(17 - 18 + 7 = 6 = 2 x 3 components) andpgr_coreNumberssatisfiescore(v) <= degree(v)with zero violations
- Both algorithms built clean against
- Final pull requests to
pgrouting/develop:- Filed the function request issues pgrouting#3142 and pgrouting#3143
- Opened pgrouting#3137 for
pgr_coreNumbers: 25 files in 6 layer-scoped commits - Opened pgrouting#3138 for
pgr_planarFaces: 28 files in 6 layer-scoped commits
- Architecture question:
- PR links: #625, #627, #636, #637, pgrouting#3137, pgrouting#3138
week 11
Dates: (August 3 ~ August 9)
Proposed: Finalize merge-ready stabilization, rebasing, and review resolution.
-
Revised plan:
- Start the routine of diffing against
pgrouting/developand merging the changes in, as asked by the mentor - Apply the process/driver consolidation to
pgr_planarFacesas well
- Start the routine of diffing against
-
Work Done:
- pgr_coreNumbers #620:
- Started the habit requested by @cvvergara of running
git diff --name-statusagainstpgrouting/developand catching the changes with a merge instead of waiting for them to come up in a meeting - Merged
pgrouting/developinto the coreNumbers branch: 34 files, bringing in thebreadthFirstSearchtotraversaldirectory reorganisation, theBINARYBFSenumeration, thepgr_dijkstraViastd::bad_allocfix and the driving distance negative value fix - The merge was clean; the
CORENUMBERSentries inenums.handutilities.cppsit in different regions from the newBINARYBFSentries so nothing conflicted - Rebuilt and reran the suites after the merge: metrics 338 tests, coloring and components 652 tests, all passing
- Started the habit requested by @cvvergara of running
- pgr_planarFaces #621:
- Changed the return type from the custom
PlanarFace_rtto the sharedIID_t_rt, mappingface_idtofrom_vid,edge_idtoto_vidandsidetocost.sideonly ever takes the values 1 and 2, both exactly representable, so the SQL output is unchanged:sideis stillINTEGERwith values 1 and 2 - Added
PLANARFACESto the enumeration and toget_name - Created
planar_process.h,planar_driver.hpp,planar_process.cppandplanar_driver.cppfor the planar family, with aswitchdispatch and acase PLANARFACES - Pointed
planarFaces.catpgr_process_planarand removed the now unusedplanarFaces_process.cpp,planarFaces_process.h,planarFaces_driver.cpp,planarFaces_driver.hppandplanarFaces_rt.h, then fixedCMakeLists.txt - Verified after the change that the output is identical, each edge still borders exactly two faces, both Euler checks still hold, the non-planar graph still raises the error and
pgr_isPlanaragrees, and the 155 planar pgTap tests still pass
- Changed the return type from the custom
- pgr_coreNumbers #620:
week 10
Dates: (July 27 ~ August 2)
Proposed: Perform large-scale validation and review-driven stabilization for both features.
-
Revised plan:
- Verify the face count against Euler's formula for
pgr_planarFaces - Handle self loops in
pgr_coreNumbers - Apply the process/driver consolidation shown by the mentor in the August 7 meeting
- Verify the face count against Euler's formula for
-
Work Done:
- pgr_planarFaces #614:
- Added pgTap tests checking that the face count satisfies Euler's formula,
V - E + F = 2on a connected subgraph - While writing them found that 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 and not a triangle, so it has 1 face and not 2. The row count of 6 was right for the wrong reason, so the description was corrected
- Verified the numbers by hand on several subgraphs first: edges 8,10,12 give V=4 E=3 F=1;
id < 10gives V=9 E=9 F=2; the full graph gives V=17 E=18 F=7 - The full graph works out to 6 and not 2 because it has 3 connected components (confirmed with
pgr_connectedComponents); the traversal walks the outer face of each component separately, so the relation generalises toV - E + F = 2C - Added tests for both the connected and the disconnected case and documented the formula in the rst;
edge_cases.pgwent from 8 to 10 plans
- Added pgTap tests checking that the face count satisfies Euler's formula,
- pgr_coreNumbers #616:
- Self loop fix: a vertex whose only edge was a self loop was returning 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 requires k actual neighbours in the subgraph
- Added a filter that drops 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
pgr_coreNumbers.rst - Applied the consolidation demonstrated by @cvvergara in the August 7 meeting: switched
coreNumbers.cto usecoloring_process.h, addedCORENUMBERSto the enumeration and toget_name, and joined the self loop removal, theinsert_min_edges_no_parallelcall and acase CORENUMBERSintocoloring_driver.cpp - Removed the now unused
coreNumbers_process.cpp,coreNumbers_process.h,coreNumbers_driver.cppandcoreNumbers_driver.hpp, then fixedCMakeLists.txt - Verified that none of the other functions sharing
coloring_driver.cppbroke:makeConnected,connectedComponents,biconnectedComponents,strongComponents,sequentialVertexColoring,bipartiteandedgeColoringall still return correct results
- pgr_planarFaces #614:
week 9
Dates: (July 20 ~ July 26)
Proposed: Complete documentation, validation, and integration cleanup for both algorithms.
-
Revised plan:
- Act on the Discourse answer about multigraph input semantics for
pgr_coreNumbers - Sync both integration branches with upstream
pgrouting/develop - Complete the git hygiene exercise assigned by the mentors on a separate branch
- Act on the Discourse answer about multigraph input semantics for
-
Work Done:
- pgr_coreNumbers #602:
- Acted on the Discourse thread about parallel edges and self loops; @cvvergara pointed at
insert_min_edges_no_parallelinbase_graph.hpp, already used bypgr_prim, so used that instead of writing new code - Switched
coreNumbers_driver.cppfrominsert_edges()toinsert_min_edges_no_parallel()so parallel edges collapse to a single minimum-cost edge before peeling starts - Two parallel edges between the same pair previously gave both vertices core 2 and three gave core 3; both now correctly give core 1, since edge multiplicity is not additional neighbours under k-core
- Verified no regressions: K4 clique unchanged (all core 3), sampledata
id < 10unchanged, self loop plus edge unchanged - Extended
edge_cases.pgfrom 25 to 26 plans: rewrote the two-parallel-edge test and added a three-parallel-edge test; documented the collapsing behaviour under Description inpgr_coreNumbers.rst
- Acted on the Discourse thread about parallel edges and self loops; @cvvergara pointed at
- Develop sync #611:
- Merged
pgrouting/developinto both integration branches, bringing in the components refactor (62 files) which removes the individual*_driver.cppfiles and moves component functions onto the shared process pattern -
sakir-2026-face-extractionhad conflicts only in the two generated locale files, none in source or docs;sakir-2026-core-decompositionmerged clean with no conflicts - Rebuilt and reran the full pgTap suite on both branches after the merge: coreNumbers 92 tests and planar family 153 tests all passing
- Merged
- Git exercise #615:
- Exercise assigned by the mentors to practice removing obsolete files and restoring pristine files from upstream, kept on a branch separate from feature work
- Removed
src/components/bridges_driver.cppandinclude/drivers/components/makeConnected_driver.hwithgit rm, one commit per file - Restored
src/components/bridges.cfrompgrouting/developusinggit checkout <remote>/<branch> -- <file> - All three files are leftovers from the components refactor, so once the integration branch had develop merged in, the branch converged to a 0-diff PR
- Still in progress (planned for Week 10):
- Self loop handling for
pgr_coreNumbers; a vertex with only a self loop currently returns core 2 because boost counts it as degree 2, which is wrong for k-core - Regenerate
locale/pot/pgrouting_doc_strings.potwith the new coreNumbers doc strings
- Self loop handling for
- pgr_coreNumbers #602:
week 8
Dates: (July 13 ~ July 19) wasn't able to work on 15july and 18th july because of exams happening in my university
Proposed: Stabilize pgr_coreNumbers() implementation with pgTap validation, benchmarks, and CI compatibility fixes.
-
Revised plan:
- Rework the
pgr_planarFacesreturn type after mentor review onseqand thesidefield - Expand
pgr_coreNumbersdocumentation with a complete graph example - Add pgTap coverage for higher cores, multigraph input and result ordering
- Rework the
-
Work Done:
- pgr_planarFaces #600:
- Removed
seqfromplanarFaces_rt.hand fixed the consequences across all four layers - Changed
sidefromchartointso the function returns 1 and 2 instead of'l'and'r' - Updated
FaceVisitorto assign side as an int visit count, and fixedseqnumbering in the C SRF layer - Updated
edge_cases.pgto expect the int values, and regenerated the documentation queries - Documented
sideas INTEGER with values 1 and 2 in the rst
- Removed
- pgr_coreNumbers #601:
- Fixed the edge labels in the coreNumbers diagram and clarified the core column description
- Added a K4 complete graph example showing core 3, in both
pgr_coreNumbers.rstand the docqueries - Added pgTap tests covering higher cores, multigraph input and result ordering
- Still in progress (planned for Week 9):
- Act on the Discourse answer about multigraph semantics
- Sync both integration branches with upstream develop
- pgr_planarFaces #600:
week 7
Dates: (July 6 ~ July 12) wasn't able to work from 7th till 10th july because of monsoon crisis in assam, thus there was powercut for 3days
Proposed: Integrate PostgreSQL wrappers and SQL result pipeline for pgr_coreNumbers().
-
Revised plan:
- Create the planar family documentation page and wire it into the experimental index
- Set up release note infrastructure for both functions
- Expand pgTap coverage toward the official promotion bar
-
Work Done:
- pgr_planarFaces #595:
- Created
planar-family.rstwithofficial-startandexperimental-startsections listingpgr_isPlanarandpgr_planarFaces - Wired it into
experimental.rstusing include directives, replacing the direct doc links - Extended
edge_cases.pgfrom 6 to 8 plans with two new edge case tests - Updated
NEWS.md,page_history.jsandrelease_notes.rstwith include directives for automated release note generation
- Created
- pgr_coreNumbers #596:
- Fixed the
Availabilityblock formatting inpgr_coreNumbers.rstusing the same.. rubric::pattern - Updated
NEWS.md,page_history.jsandrelease_notes.rstwith include directives - Extended
edge_cases.pgfrom 9 to 13 plans, adding subgraph boundary coverage forid < 3(3-node chain) andid < 8(8-edge subgraph) - Extended
no_crash_test.pgfrom 5 to 8 plans, addingnull_ret/null_ret_arrprepared statements and athrow_on_empty_edges_sqltest for the empty SQL error path - Added
COSTandROWSplanner hints to the_pgr_coreNumbersSQL wrapper - Fixed the sort comparator in
coreNumbers.cppto takeII_t_rtby const reference instead of by value - All CI checks passing
- Fixed the
- Still in progress (planned for Week 8):
- Rework the
pgr_planarFacesreturn type after mentor review onseqandside - Complete graph example for
pgr_coreNumbersdocumentation
- Rework the
- pgr_planarFaces #595:
week 6
Dates: (June 29 ~ July 5)
Proposed: Expand user-facing documentation and documentation queries for both functions to the depth of the existing pgRouting function pages.
-
Revised plan:
- Bring both rst pages up to the depth of the Dijkstra pages: prose, diagrams and numbered examples
- Extend the docqueries for both functions and regenerate the expected results
- Untangle the cross-module dependencies that were breaking CI between the planar and metrics branches
-
Work Done:
- pgr_planarFaces #591 and pgr_coreNumbers #590:
- Expanded both documentation pages to Dijkstra-style depth: prose, graphviz diagrams and numbered examples with explanations
- Extended the docqueries for both functions and updated the expected
.resultfiles - Fixed CI failures by removing the cross-module docquery and rst dependencies between the planar and metrics mentor branches, which were making each branch fail on the other's files
- pgr_planarFaces #591 and pgr_coreNumbers #590:
week 5
Dates: (June 22 ~ June 28)
Proposed: Complete pgr_coreNumbers documentation and testing; polish pgr_planarFaces documentation.
-
Revised plan:
- Create Week 5 branches and PRs following the weekly workflow
- Finish remaining
pgr_coreNumberspgtap tests (inner_query.pg,edge_cases.pg) - Complete
pgr_coreNumbers.rst(academic prose, Batagelj & Zaversnik citation) - Refine
pgr_planarFaces.rstexplanation and description wording
-
Work Done:
- pgr_planarFaces #578:
- Refined the Explanation section: clarified success on planar input, noted the unbounded exterior face, and described counterclockwise traversal for
side = 'l'/'r' - Corrected row-count wording in the Description section (
2|E|rows when the graph has|E|edges) - No new algorithm or test changes; existing docqueries and pgtap tests from Week 3-4 remain passing
- Refined the Explanation section: clarified success on planar input, noted the unbounded exterior face, and described counterclockwise traversal for
- pgr_coreNumbers #579:
- Expanded
pgr_coreNumbers.rst: added k-core definition, algorithm context, Batagelj & Zaversnik citation, and Boost Graph Inside marker - Fixed Availability section formatting to match pgRouting RST conventions
- Added
inner_query.pgpgtap test using the standardstyle_dijkstrapattern (54 inner-query style checks) - Added
edge_cases.pgpgtap test covering subgraphs (id < 2,id < 4,id < 5,id < 10) and empty-graph input - Updated See Also links (
pgr_betweennessCentrality,metrics-family) - All CI checks passing
- Expanded
- Still in progress (planned for Week 6):
- Add pipeline example linking
pgr_coreNumberswithpgr_planarFacesin documentation - Additional Examples section for
pgr_coreNumbers(subgraph and edge-case docqueries) - Cross-link
pgr_isPlanarinpgr_planarFacesSee Also section
- Add pipeline example linking
- pgr_planarFaces #578:
week 4
Dates: (June 15 ~ June 21)
Proposed: Stabilize pgr_planarFaces() integration and complete validation/testing workflow.
-
Revised plan:
- Create Week 4 branches and PRs following the weekly workflow
- Polish
pgr_planarFacesdocumentation and docqueries - Implement
pgr_coreNumbersalgorithm (Batagelj–Zaversnik) and switch toII_t_rt - Add partial documentation, docqueries, and initial pgtap tests for
pgr_coreNumbers
-
Work Done:
- pgr_planarFaces #577:
- Enhanced
pgr_planarFaces.rstwith clearer face description, guidance to runpgr_isPlanarfirst, and an Explanation section - Added Additional Examples: planarity check before face extraction, and triangle graph example (2 faces, 6 rows)
- Extended docquery files (
planarFaces.pgandplanarFaces.result) withq2(isPlanar check) andq3(triangle example); docquery tests pass
- Enhanced
- pgr_coreNumbers #576:
- Switched return type from custom
CoreNumbers_rtto sharedII_t_rt(d1-> node,d2-> core;seqgenerated in C SRF layer) - Removed
include/c_types/coreNumbers_rt.hand updated process, driver, and algorithm layers - Implemented k-core decomposition manually using Batagelj–Zaversnik algorithm (Boost used only for graph construction)
- Addressed mentor review: renamed
deg->degree, extractedbin_sort_vertices()helper, usedstd::max_element()for max-degree lookup - Added partial RST documentation (
pgr_coreNumbers.rst) and registered indoc/metrics/CMakeLists.txtandmetrics-family.rst - Created docquery files (
coreNumbers.pgandcoreNumbers.result) with correct BEGIN/ROLLBACK wrapper format - Added initial pgtap tests:
types_check.pgandno_crash_test.pg(both passing) - All CI checks passing
- Switched return type from custom
- Still in progress (planned for Week 5):
- Complete
pgr_coreNumbers.rst(academic prose, Batagelj & Zaversnik citation, pipeline example withpgr_planarFaces) - Remaining pgtap tests (
inner_query.pg,edge_cases.pg)
- Complete
- pgr_planarFaces #577:
week 3
Dates: (June 8 ~ June 14)
Proposed: Begin PostgreSQL integration for pgr_planarFaces() with minimal wrapper and result pipeline support.
-
Revised plan:
- Restructure
pgr_planarFacesto 3-layer process/driver architecture - Add documentation and docqueries for
pgr_planarFaces - Fix
pgr_coreNumbersSQL and copyright issues
- Restructure
-
Work Done:
- pgr_planarFaces #568:
- Restructured algorithm to 3-layer process/driver architecture matching
dijkstra,astar,spanningTree,coloring, andorderingmodules - Created algorithm-specific
planarFaces_process.cppandplanarFaces_driver.cppfor SPI connection, timing, error reporting, edge fetching, and graph construction - Updated
planarFaces.cto callpgr_process_planarFaces()instead of directly calling the driver - Created RST documentation (
pgr_planarFaces.rst) and added to experimental toctree - Created docquery files (
planarFaces.pgandplanarFaces.result) with correct BEGIN/ROLLBACK wrapper format - Fixed cpplint errors (include ordering, missing
<utility>header) - Refactored from shared
planar_process/planar_driverto algorithm-specific files to avoid return type conflicts (PlanarFace_rtvsII_t_rt) with other planar algorithms - All CI checks passing- build, pgtap tests, docqueries, and cpplint
- Restructured algorithm to 3-layer process/driver architecture matching
- pgr_coreNumbers #567:
- Fixed
_coreNumbers.sqlLANGUAGE property fromIMMUTABLEtoVOLATILEto matchbetweennessCentralitypattern - Corrected copyright years in
coreNumbers.hppandcoreNumbers.cpp - All CI checks passing
- Fixed
- pgr_planarFaces #568:
week 2
Dates: (June 1 ~ June 7)
Proposed: Implement core planar face traversal logic and face recording workflow in isolated C++ prototypes.
-
Revised plan:
- Implement
pgr_planarFacesalgorithm and add pgtap tests - Move
pgr_coreNumbersfiles tometrics/module and fix naming conventions
- Implement
-
Work Done:
- Attended Monday meeting where mentor Vicky reviewed Week 1 PRs and gave feedback on file structure and naming conventions
-
pgr_planarFaces (PR #563):
- Implemented face traversal algorithm using Boost's
boyer_myrvold_planarity_testandplanar_face_traversalwith a customFaceVisitorthat recordsseq,face_id,edge_id,side - Rewrote driver and C SRF entry to follow the planar module pattern (matching
isPlanar/boyerMyrvold) - Removed old
planarFaces_process.cppandplanarFaces_driver.hpp— replaced with new driver pattern - Fixed file naming convention - removed incorrect
pgr_prefix from filenames to match planar directory - Added 4 pgtap test files (69 tests total):
edge_cases.pg(6),types_check.pg(4),no_crash_test.pg(5),inner_query.pg(54) - Verified algorithm output against real PostgreSQL database - all 69 tests pass locally and in CI
- Implemented face traversal algorithm using Boost's
-
pgr_coreNumbers (PR #564):
- Relocated all coreNumbers files from standalone
coreNumbers/directory intometrics/module (alongsidebetweennessCentralityandbandwidth) - Renamed files to follow metrics naming convention - removed
pgr_prefix, renamed_process.h→_driver.h,_driver.hpp→.hpp - Updated build configs:
src/metrics/CMakeLists.txt,sql/metrics/CMakeLists.txt,configuration.conf,code_checker.sh - Fixed driver header, SQL files, and C SRF entry to follow
betweennessCentralitypattern
- Relocated all coreNumbers files from standalone
week 1
Dates: (May 25 ~ May 31)
Proposed:
Study existing pgr_isPlanar() infrastructure and integrate Boyer–Myrvold embedding generation with reusable embedding storage for pgr_planarFaces().
-
Revised plam:
- Create skeleton file struture for
pgr_planarFaces - Create skeleton file structure for
pgr_coreNumbers - Follow the process-driver pattern shown by mentor
- Create skeleton file struture for
-
Work Done:
- Had a Monday meeting where my mentor Vicky showed how to create skeleton files using Dijkstra as example (PR #548, PR #549)
- Had exams so couldnt work till Thursday
- Made first attempt at
pgr_planarFacesskeleton (PR #551) but most CI checks were failing and the commit history got too messy so I closed it and started fresh - Rebuilt both skeletons from scratch:
- SQL layer: internal C stub + public wrapper
- C layer: PostgreSQL SRF entry point
- C++ layer: process layer + driver stub
- Build system: CMakeLists, configuration.conf, sig file
-
PR #556 for
pgr_planarFaces, all CI checks passing -
PR #555 for
pgr_coreNumbers, had one issue where the sig file entries were in the wrong position (recieved query check failure), fixed the sort order and all checks passed after that
Bonding period
Goal: arrive at Week 1 with , proposal reviewed by mentors, study implementation of algorithms, and a clear understanding of pgRouting architecture.
Proposed: Study pgRouting architecture and refine implementation strategy after deeper analysis of planar traversal and k-core decomposition workflows.
Plan for the week:
- Research outer-face traversal handling and visitor traversal order
- Investigate standalone implementation strategy for
pgr_coreNumbers() - Study pgRouting SQL → C wrapper → C++ driver → Boost integration pipeline
- Research Batagelj–Zaversnik k-core decomposition workflow
Report:
- Bonding period meeting
- Prepared Wiki (copied from proposal)
- Revised proposal timeline and implementation strategy
- Research about
planar_face_traversalvisitor workflow and outer-face handling - Investigated standalone
pgr_coreNumbers()implementation feasibility - Studied pgRouting execution pipeline and Boost graph integration workflow
- Researched Batagelj–Zaversnik degree-peeling decomposition process
Proposed: Study planar face traversal behavior using Graphviz examples and Boost documentation.
Plan for the week:
- Study
boyer_myrvold_planarity_testembedding generation - Experiment with Graphviz planar graph examples
- Research
planar_face_traversalvisitor workflow - Study pgRouting SQL → C wrapper → C++ driver → Boost pipeline
- Revise implementation approach after architecture study
Report:
- Studied Graphviz planar traversal examples
- Researched
planar_face_traversalworkflow and visitor behavior - Investigated outer-face traversal handling using Boost documentation and Graphviz experiments
- Studied pgRouting execution pipeline (SQL → C wrapper → C++ driver → Boost)
- Restructured proposal after deeper architecture study
- Planned standalone
pgr_coreNumbers()implementation approach - Researched core-number computation workflow and graph abstraction integration
- Explored Boost Graph Library references related to k-core decomposition
- Created discussion notes/questions regarding traversal behavior and implementation details
Plan for the week:
- Bonding period meeting with mentors
- Prepare GSoC wiki structure from proposal
- Revise proposal after deeper algorithm research
- Research outer-face handling during planar traversal
- Study third algorithm/stretch-goal feasibility as homework
Report:
- Bonding period meeting completed
- GSoC wiki prepared from proposal
- Proposal revision and implementation planning started
- Outer-face traversal behavior researched
- Third algorithm/stretch-goal research in progress
Link to all the Pull Requests made in GSoC-pgRouting repository
| Pull Request | Description | Date | Status |
|---|---|---|---|
| pgrouting#3137 | New function: pgr_coreNumbers | August 22, 2026 | Open |
| pgrouting#3138 | New function: pgr_planarFaces | August 23, 2026 | Open |
Related function request issues: pgrouting#3142 (pgr_coreNumbers), pgrouting#3143 (pgr_planarFaces).
| Pull Request | Description | Date | Status |
|---|---|---|---|
| #555 | Week 1: pgr_coreNumbers skeleton | May 29, 2026 | Merged |
| #556 | Week 1: pgr_planarFaces skeleton | May 30, 2026 | Merged |
| #563 | Week 2: pgr_planarFaces | June 7, 2026 | Merged |
| #564 | Week 2: pgr_coreNumbers | June 7, 2026 | Merged |
| #567 | Week 3: pgr_coreNumbers | June 13, 2026 | Merged |
| #568 | Week 3: pgr_planarFaces | June 13, 2026 | Merged |
| #576 | Week 4: pgr_coreNumbers | June 21, 2026 | Merged |
| #577 | Week 4: pgr_planarFaces | June 21, 2026 | Merged |
| #578 | Week 5: pgr_planarFaces | June 29, 2026 | Merged |
| #579 | Week 5: pgr_coreNumbers | June 29, 2026 | Merged |
| #591 | Week 6: pgr_planarFaces | July 6, 2026 | Merged |
| #590 | Week 6: pgr_coreNumbers | July 6, 2026 | Merged |
| #595 | Week 7: pgr_planarFaces | July 6, 2026 | Merged |
| #596 | Week 7: pgr_coreNumbers | July 10, 2026 | Merged |
| #600 | Week 8: pgr_planarFaces | July 15, 2026 | Merged |
| #601 | Week 8: pgr_coreNumbers | July 15, 2026 | Merged |
| #602 | Week 9: pgr_coreNumbers | July 22, 2026 | Merged |
| #611 | Week 9: merge develop into planarFaces | July 29, 2026 | Merged |
| #615 | Week 9: git exercise | August 3, 2026 | Merged |
| #614 | Week 10: pgr_planarFaces | August 2, 2026 | Merged |
| #616 | Week 10: pgr_coreNumbers | August 3, 2026 | Merged |
| #620 | Week 11: pgr_coreNumbers | August 10, 2026 | Merged |
| #621 | Week 11: pgr_planarFaces | August 10, 2026 | Merged |
| #625 | Week 12: Boost version PoC, pgr_planarFaces | August 15, 2026 | Open |
| #627 | Week 12: pgr_planarFaces | August 15, 2026 | Merged |
| #636 | Week 12: Boost version PoC, pgr_coreNumbers | August 17, 2026 | Open |
| #637 | Week 12: pgr_coreNumbers | August 17, 2026 | Merged |
TBD
Report Mail - [OSGeo Discourse]
Hello everyone,
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 learning experience and great time working with the pgRouting community and mentors.
Title: Implementing Planar Face Extraction and K-Core Decomposition Algorithms to pgRouting
Organisation: pgRouting under the umbrella of OSGeo
Abstract: This GSoC project dealt with the implementation of two new Graph algorithms in pgRouting. The algorithms are described below:
-
Planar Face Extraction: Given a planar undirected graph, it computes a planar embedding and performs a face traversal, identifying each face of the embedding and returning every edge-face incidence as a row indicating which face the edge borders and on which side. A face is a maximal connected region of the plane bounded by edges, which on a street network corresponds to the city blocks between the roads. Each edge separates exactly two faces once an embedding is fixed, so a graph with
|E|edges yields2|E|rows. The number of faces obeys Euler's formula,|V| - |E| + |F| = 2on a connected planar graph, generalising to|V| - |E| + |F| = 2Con a graph withCcomponents, with a time complexity of O(V + E), where V is the number of vertices and E is the number of edges. This implementation will enhance pgRouting's capabilities in topology extraction, benefiting polygon reconstruction and block identification problems.
It is implemented in Boost Graph Library (BGL) as boost::planar_face_traversal together with boost::boyer_myrvold_planarity_test.
-
K-Core Decomposition: The core number of a vertex is the largest value
ksuch that the vertex belongs to the k-core of the graph, where the k-core is the maximal subgraph in which every vertex has degree at leastkwithin that subgraph. The decomposition repeatedly peels away vertices whose degree falls belowk, raisingkat each stage until none remain, assigning one core number to every vertex with a time complexity of O(E) and space complexity of O(V), where V is the number of vertices and E is the number of edges. On a road network, core1marks dead-ends and cul-de-sacs, core2marks corridors and cycles, and core3and above mark densely interconnected regions with redundant routes. This implementation will enhance pgRouting's capabilities in network resilience and graph degeneracy analysis.
It is implemented from scratch using the Batagelj-Zaversnik degree-peeling algorithm, with Boost used only for graph construction.
State of the Project Before GSoC: pgRouting did not provide functions for planar face extraction or k-core decomposition. Only pgr_isPlanar and pgr_boyerMyrvold existed in the planar family, and neither returned the faces of an embedding. The metrics family had pgr_betweennessCentrality, pgr_degree and pgr_bandwidth, but no core decomposition.
State of the Project After GSoC: The deliverables are code, documentation, documentation tests, and the pgTAP tests of the functions pgr_planarFaces and pgr_coreNumbers, both integrated into pgRouting's shared process and driver architecture.
Potential Future Work:
- After the completion of the implementation of
pgr_planarFaces()andpgr_coreNumbers(), I will focus on resolving any potential bugs or usability issues that may come up during extended testing and community feedback, so that both can be promoted from experimental to official. - I would like to coordinate the planar family structure with the other planar functions being added in the same cycle, so that
pgr_isPlanar,pgr_boyerMyrvold,pgr_planarFaces,pgr_makeMaximalPlanarandpgr_makeBiconnectedPlanarshare a consistent process and driver arrangement. - I would like to explore a pipeline example combining
pgr_planarFaceswithpgr_coreNumbersfor urban block extraction and network hierarchy analysis, so I can experiment and develop at a more relaxed pace after the program ends.
Links:
-
Pull Requests:
- Final Pull Requests: (#3137) Experimental Function - coreNumbers (https://github.com/pgRouting/pgrouting/pull/3137) and (#3138) Experimental Function - planarFaces (https://github.com/pgRouting/pgrouting/pull/3138).
- Intermediate pull requests: https://github.com/pgRouting/GSoC-pgRouting/pulls?q=is%3Apr+author%3Asakirr05
- Project Documentation (Wiki Page): https://github.com/pgRouting/pgrouting/wiki/GSoC-2026-Planar-Face-Extraction-and-K%E2%80%90Core-Decomposition
I am so grateful to be a part of the amazing GSoC and OSGeo communities. I have learned a lot during this program and it has helped me improve my existing knowledge of contributing to open source and also got me better at programming. Last but not the least, thank you to my mentors and the entire community for the continuous support, guidance and helpful communication!
Thank you and Regards,
Md Sakir Ahmed
-
Batagelj, V. and Zaversnik, M. — An O(m) Algorithm for Cores Decomposition of Networks
-
Diagram tools — Diagrams were created using Python (NetworkX + Matplotlib) and Draw.io