New function pgr_makeMaximalPlanar to be added in pgrouting

Open
  • Is something wrong?
#3,141 0 comments 0 reactions 0 assignees View on GitHub

Maintainers usually reply within 3 days

Nobody has claimed this yet.

  • #3134 by @Mohit242-bit — closed without merging

Assessment

Difficulty
4/5
Estimated time
3-5 days
Newbie friendliness
40/100
Issue type
Feature
Clarity
Clearly specified
Activity status
Stale
Tech stack
cpp, postgresql
Domain
backend, databases

Research direction

The issue describes adding a new SQL function pgr_makeMaximalPlanar. Look at existing pgRouting functions in the source code to understand the pattern for wrapping Boost Graph Library algorithms. The linked pull request #3134 may show related work. Start by examining the directory structure for where graph algorithms are implemented and how they are exposed to PostgreSQL. The function must be added to the SQL signatures and the underlying C++ implementation.

Written by the indexing model from the issue text.

Description

GSoC planar

pgr_makeMaximalPlanar():

makeMaximalPlanar(): Maximal planar augmentation (triangulation) is an algorithm that takes a biconnected planar graph and adds edges until the graph becomes maximally planar. A graph is maximally planar if no more edges can be added without violating planarity, which results in a triangulated graph where every face is a triangle (satisfying Euler's formula E = 3V - 6). Triangulated planar graphs are required for advanced graph layout algorithms like Chrobak-Payne straight line drawing. This implementation uses the Boost Graph Library's make_maximal_planar algorithm with a time complexity of O(V + E), where V is the number of vertices and E is the number of edges. This will enhance pgRouting's capabilities in planar graph optimization and spatial rendering problems.

The algorithm:
  • Works on undirected graphs.
  • Requires the input graph to already be biconnected and planar.
  • Adds new edges between vertices strictly preserving the planarity of the embedding.
  • Outputs the set of edges added to the graph to triangulate it.
  • Running time: O(V + E) where V is the number of vertices and E is the number of edges.
Signature:
  • pgr_makeMaximalPlanar()
pgr_makeMaximalPlanar(Edges SQL)

Returns set of (seq, start_vid, end_vid)
OR EMPTY SET

Parameters

Parameter Type Description
Edges SQL TEXT Inner SQL query, as described below.
Inner Query

Edges SQL: An SQL query returning a set of rows with the following columns:

Column Type Default Description
id ANY-INTEGER Identifier of the edge.
source ANY-INTEGER Identifier of the first endpoint vertex of the edge.
target ANY-INTEGER Identifier of the second endpoint vertex of the edge.
cost ANY-NUMERICAL Weight of the edge (source, target). When negative, the edge does not exist.
reverse_cost ANY-NUMERICAL -1 Weight of the edge (target, source). When negative, the edge does not exist.

Where:

  • ANY-INTEGER = SMALLINT, INTEGER, BIGINT
  • ANY-NUMERICAL = SMALLINT, INTEGER, BIGINT, REAL, FLOAT
Result Columns

Returns SETOF (seq, start_vid, end_vid).

Column Type Description
seq BIGINT Sequential value starting from 1.
start_vid BIGINT Identifier of the first endpoint vertex of the added edge.
end_vid BIGINT Identifier of the second endpoint vertex of the added edge.
Dominant language
C++
Stars
1.4k
Forks
397
Avg merge
2d 16h
Merged PRs (30d)
8

Getting set up

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from pgRouting/pgrouting

All issues in pgRouting/pgrouting

Similar issues

More C++ issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.