Skip to content

Home

Jump to bottom
Mohit Pramod Singh Rawat edited this page May 17, 2026 · 3 revisions

Table of Contents

Proposal

Brief Description

This project completes pgRouting's planar graph pipeline by implementing two missing Boost Graph Library algorithms: pgr_makeBiconnectedPlanar and pgr_makeMaximalPlanar.

Together with the existing pgr_makeConnected, these form a complete pipeline:

pgr_makeConnected → pgr_makeBiconnectedPlanar → pgr_makeMaximalPlanar

This pipeline unlocks downstream Boost layout algorithms (chrobak_payne_straight_line_drawing, planar_canonical_ordering) that are currently inaccessible to pgRouting users.

State of the Project Before GSoC

pgRouting already provides pgr_makeConnected, pgr_isPlanar / pgr_boyerMyrvold, and pgr_bipartite. Two concrete gaps remain: no function to eliminate articulation points while preserving planarity, and no triangulation of biconnected planar graphs — leaving chrobak_payne_drawing and straight_line_drawing completely inaccessible.

Deliverables

Proposed:

  • Implementation of pgr_makeBiconnectedPlanar()
  • Implementation of pgr_makeMaximalPlanar()
  • Code with clear comments following pgRouting style guides
  • User documentation (RST format) for each new function
  • pgTap test cases for all functions
  • Weekly wiki progress reports
  • Detailed reports for midterm and final evaluations

Delivered: Link to PR or to Tag based on the final status

Detailed Proposal

Link to proposal PDF

Participants

Title GitHub Handle Name
1st Mentor @cvvergara Vicky Vergara
2nd Mentor @robe2 Regina Obe
Student Developer @Mohit242-bit Mohit Rawat

Timeline & weekly report

Note: in reverse order: the most recent is first

Second Coding Period

week 12

Week 12

Dates: (August 10 - August 16)

Proposed: Final polish - clean up all code, squash commits, format documentation, write final blog post / GSoC wiki summary, prepare final report.

Plan for the week:

  • Clean up all code and squash commits
  • Finalize all RST documentation
  • Write final GSoC wiki summary
  • Prepare and submit final evaluation report

Report:

  • Code cleanup and commit squashing complete
  • All documentation finalized
  • Final wiki summary written
  • Final report submitted

Link to report mail

week 11

Week 11

Dates: (August 3 - August 9)

Proposed: Additional integration testing and performance benchmarking on OSM datasets (>1M edges). Address any remaining mentor feedback from Phase 2.

Plan for the week:

  • Run full pipeline integration tests on large OSM datasets
  • Performance benchmarking on large real-world networks
  • Address any remaining mentor feedback
  • Begin drafting final report

Report:

  • Integration tests on large OSM datasets complete
  • Performance benchmarking done
  • Mentor feedback addressed
  • Final report draft started

Link to report mail

week 10

Week 10

Dates: (July 27 - August 2)

Proposed: Pipeline Integration & Deliverable - fix any cross-function ID mapping issues. Deliverable: working pgr_makeMaximalPlanar with full tests and docs. Address mentor feedback from Phase 2 midterm review.

Plan for the week:

  • Fix any cross-function ID mapping issues
  • Confirm pgr_makeMaximalPlanar is at merged quality
  • Full pipeline integration test: makeConnected -> makeBiconnectedPlanar -> makeMaximalPlanar
  • Address mentor feedback from Phase 2 review

Report:

  • Cross-function ID mapping issues fixed
  • pgr_makeMaximalPlanar at merged quality
  • Full pipeline end-to-end integration test passing
  • Mentor feedback addressed

Link to report mail

week 9

Week 9

Dates: (July 20 - July 26)

Proposed: Phase 2: Documentation & Idempotency - complete RST docs and docqueries for pgr_makeMaximalPlanar. Verify idempotency (re-run returns empty, pgr_isPlanar still true). Full pipeline integration test.

Plan for the week:

  • Complete RST documentation for pgr_makeMaximalPlanar
  • Write and verify docquery examples
  • Verify idempotency: re-running on augmented graph returns 0 rows
  • Verify pgr_isPlanar returns true after adding returned edges

Report:

  • RST documentation for pgr_makeMaximalPlanar complete
  • Docquery examples written and verified
  • Idempotency verified (re-run returns 0 rows)
  • Planarity preserved after augmentation confirmed

Link to report mail

week 8

Week 8

Dates: (July 13 - July 19)

Proposed: Phase 2: Testing - write comprehensive pgTap tests for pgr_makeMaximalPlanar. Verify E = 3V-6 on all test graphs. Verify no parallel edges or self-loops introduced.

Plan for the week:

  • Write pgTap edge_cases.pg: K3 (already maximal), C4 square (adds 2 diagonals), wheel graph W5, K5 (non-planar -> error)
  • Write inner_query.pg, no_crash_test.pg, types_check.pg
  • Verify E = 3V-6 post-augmentation on all test graphs
  • Verify no parallel edges or self-loops introduced

Report:

  • pgTap edge_cases.pg complete
  • pgTap inner_query.pg complete
  • pgTap no_crash_test.pg complete
  • pgTap types_check.pg complete
  • E = 3V-6 verified on all test graphs

Link to report mail

week 7

Week 7

Dates: (July 6 - July 12)

Proposed: Phase 2: Core Logic & Edge Cases - handle all error conditions for pgr_makeMaximalPlanar. Handle already-maximal-planar case (empty return). Verify E = 3V-6.

Plan for the week:

  • Handle error conditions: not-biconnected input, not-planar input, fewer than 3 vertices
  • Handle already-maximal-planar case (all faces triangles -> empty return)
  • Verify E = 3V-6 holds on all test graphs

Report:

  • Error conditions handled: not-biconnected, not-planar, < 3 vertices
  • Already-maximal-planar returns empty set correctly
  • E = 3V-6 verified on all test graphs

Link to report mail

First Coding Period

week 6

Week 6

Dates: (June 29 - July 5)

Proposed: Phase 2: pgr_makeMaximalPlanar begins - implement triangulation_visitor with timestamp trick for O(1) neighbor marking. Connect to planar_face_traversal. Get basic triangulation working on C4 -> K4 (adds 2 diagonals).

Plan for the week:

  • Implement triangulation_visitor with timestamp trick for O(1) neighbor marking
  • Connect to planar_face_traversal
  • Get basic triangulation working on C4 -> K4 (adds 2 diagonals, E = 6)
  • Midterm evaluation: pgr_makeBiconnectedPlanar at merged quality; pgr_makeMaximalPlanar basic triangulation passing

Report:

  • triangulation_visitor implemented with timestamp trick
  • Connected to planar_face_traversal
  • C4 -> K4 triangulation working (adds 2 diagonals)
  • Midterm deliverables submitted

Link to report mail

week 5

Week 5

Dates: (June 22 - June 28)

Proposed: Phase 1 -> Phase 2 Transition - address mentor feedback from Week 4. Create Phase 2 file scaffolding (src/planar/makeMaximalPlanar.*). Study triangulation_visitor source and end_face() phases 1-6 in detail.

Plan for the week:

  • Address all mentor feedback from Week 4
  • Create Phase 2 file scaffolding: makeMaximalPlanar.hpp, driver files, SQL files
  • Study triangulation_visitor and end_face() logic in detail
  • Update CMakeLists.txt for Phase 2 files

Report:

  • All Phase 1 mentor feedback addressed
  • Phase 2 file scaffolding created
  • triangulation_visitor and end_face() studied
  • CMakeLists.txt updated for Phase 2

Link to report mail

week 4

Week 4

Dates: (June 15 - June 21)

Proposed: Phase 1: Documentation & Delivery - complete RST documentation, write docquery examples, verify idempotency. Deliverable: working pgr_makeBiconnectedPlanar with full tests and docs.

Plan for the week:

  • Complete RST documentation for pgr_makeBiconnectedPlanar
  • Write and verify docquery examples
  • Verify idempotency: re-run returns 0 rows; pgr_isPlanar returns true after augmentation
  • Submit Phase 1 deliverable for mentor review

Report:

  • RST documentation complete
  • Docquery examples written and verified
  • Idempotency verified
  • Phase 1 deliverable submitted for mentor review

Link to report mail

week 3

Week 3

Dates: (June 8 - June 14)

Proposed: Phase 1: Edge Cases & Output Mapping - handle already-biconnected (empty return), not-connected error, not-planar error. Write comprehensive pgTap tests: path graphs P3/P4/P5, cycle graphs, tree graphs, disconnected input.

Plan for the week:

  • Handle edge cases: already-biconnected (empty), not-connected (error), not-planar (error)
  • Write pgTap edge_cases.pg: path graphs P3/P4/P5, cycle graphs C4/C5, tree graphs, K5 (non-planar -> error)
  • Write inner_query.pg, no_crash_test.pg, types_check.pg
  • Map Boost vertex descriptors -> pgRouting IDs correctly

Report:

  • Edge cases handled: already-biconnected, not-connected, not-planar
  • pgTap edge_cases.pg complete
  • pgTap inner_query.pg complete
  • pgTap no_crash_test.pg complete
  • pgTap types_check.pg complete

Link to report mail

week 2

Week 2

Dates: (June 1 - June 7)

Proposed: Phase 1: Core Algorithm - connect EdgeIndexMap and embedding to boost::make_biconnected_planar. Implement pgr_collect_edges_visitor. Map Boost vertex descriptors back to pgRouting IDs. Get a working end-to-end function on the 7-vertex walkthrough graph.

Plan for the week:

  • Connect EdgeIndexMap and planar embedding to boost::make_biconnected_planar
  • Implement pgr_collect_edges_visitor (records (u,v) pairs without mutating graph)
  • Map Boost vertex descriptors back to pgRouting IDs
  • Get end-to-end working on 7-vertex walkthrough graph (adds edges (1,5) and (3,7))

Report:

  • EdgeIndexMap connected to boost::make_biconnected_planar
  • pgr_collect_edges_visitor implemented
  • Vertex descriptor -> pgRouting ID mapping working
  • End-to-end working on 7-vertex walkthrough graph

Link to report mail

week 1

Week 1

Dates: (May 25 - May 31)

Proposed: Phase 1: pgr_makeBiconnectedPlanar begins - build and test EdgeIndexMap construction in isolation using BGL_FORALL_EDGES. Run boyer_myrvold_planarity_test with embedding storage enabled; verify embedding vector populates correctly on test graphs.

Plan for the week:

  • Build and test EdgeIndexMap construction using BGL_FORALL_EDGES in isolation
  • Run boyer_myrvold_planarity_test with embedding storage enabled on test graphs
  • Verify embedding vector populates correctly on path, cycle, and tree graphs
  • Create all 12 new files for Phase 1 file structure; update CMakeLists.txt

Report:

  • EdgeIndexMap construction built and tested in isolation
  • boyer_myrvold_planarity_test with embedding storage verified on test graphs
  • All Phase 1 file structure created
  • CMakeLists.txt updated

Link to report mail

Community Bonding Period

Bonding period

Goal: arrive at Week 1 with pseudocode approved by mentors, test graphs designed, and a clear understanding of pgRouting architecture.

Week -1 (May 19 ~ May 24)

Proposed: Pre-Coding Preparation - run standalone tests of boost::make_biconnected_planar on path/tree graphs and boost::make_maximal_planar on simple planar graphs (C4 -> K4). Share pseudocode of C++ wrapper classes with mentors for review. Design specific test graphs for docqueries.

Plan for the week:

  • Run standalone tests of boost::make_biconnected_planar on path/tree graphs
  • Run standalone tests of boost::make_maximal_planar on simple planar graphs (C4 -> K4)
  • Write pseudocode for both C++ wrapper classes and share with mentors for review
  • Design specific test graphs for docqueries and submit to mentors for approval
  • Clarify with mentors: edge_index map construction, preferred error reporting, and embedding parameter approach

Report:

  • Standalone tests of boost::make_biconnected_planar run
  • Standalone tests of boost::make_maximal_planar run
  • Pseudocode for both wrappers shared with mentors
  • Test graphs designed and submitted for approval
  • Mentor clarifications received

Link to report mail

Week -2 (May 11 ~ May 18)

Proposed: Deep Codebase Reading - read make_biconnected_planar.hpp and make_maximal_planar.hpp in full Boost source. Write a private walkthrough document for each file and share with mentors for feedback.

Plan for the week:

  • Study boyer_myrvold_planarity_test embedding generation
  • Experiment with Graphviz planar graph examples
  • Research planar_face_traversal visitor workflow
  • Study pgRouting SQL -> C wrapper -> C++ driver -> Boost pipeline
  • Revise implementation approach after architecture study

Report:

  • Studied Graphviz planar examples
  • planar_face_traversal workflow studied
  • pgRouting execution pipeline studied
  • Researched implementation approach from scratch

Link to report mail

Week -3 (May 1 ~ May 10)

Proposed: Environment and Community - introduce myself on pgrouting-dev and soc@osgeo mailing lists. Verify pgRouting builds from source with all planar tests passing. Set up wiki progress page.

Plan for the week:

  • Introduce myself on pgrouting-dev and soc@osgeo mailing lists
  • Verify pgRouting builds from source with all planar tests passing
  • Set up wiki progress page at the pgRouting GSoC wiki

Report:

  • Bonding period meeting
  • Prepared Wiki (copied from proposal)
  • Worked on edges problem (maximal planar and biconnected planar should return edges or not in the output)

Link to report mail

Log of Pull Requests

Link to all the Pull Requests made in GSoC-pgRouting repository

Pull Request Description Date Status
TBD pgr_makeBiconnectedPlanar - Phase 1 implementation TBD TBD
TBD pgr_makeMaximalPlanar - Phase 2 implementation TBD TBD

Slides

TBD

Final Report

TBD

  1. Links:

(i) Code Documentation:

TBD

(ii) Tags:

TBD

(iii) Pull Requests:

TBD

(iv) Wiki Pages:

TBD

  1. Images:

TBD

  1. Media:

TBD

References

  1. boost::make_biconnected_planar - Boost Graph Library

  2. boost::make_maximal_planar - Boost Graph Library

  3. Boyer-Myrvold Planarity Testing/Embedding - Boost Graph Library

  4. biconnected_components (Tarjan) - Boost Graph Library

  5. planar_face_traversal - Boost Graph Library

  6. planar_canonical_ordering - Boost Graph Library

  7. chrobak_payne_straight_line_drawing - Boost Graph Library

  8. pgRouting Sample Data

Clone this wiki locally