Hacktoberfest 2026: los issues que los mantenedores marcaron para octubre, abiertos y aptos para principiantes. Explorar issues de Hacktoberfest

New function pgr_makeMaximalPlanar to be added in pgrouting

Abierto
  • ¿Algo no está bien?
#3,141 0 comentarios 0 reacciones 0 asignados Ver en GitHub

Los mantenedores suelen responder en 2 días

Nadie ha tomado este issue todavía.

  • #3134 de @Mohit242-bit — cerrado sin fusionar

Evaluación

Dificultad
4/5
Tiempo estimado
3-5 días
Aptitud para principiantes
40/100
Tipo de issue
Nueva funcionalidad
Claridad
Bien especificado
Estado de actividad
Estancado
Stack tecnológico
cpp, postgresql
Área
backend, databases

Línea de trabajo

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.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

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.
Lenguaje dominante
C++
Estrellas
1.4k
Forks
397
Merge medio
2 d 2 h
PR fusionados (30 d)
4

Preparar el entorno

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de pgRouting/pgrouting

Todos los issues de pgRouting/pgrouting

Issues similares

Más issues de C++

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.