Hacktoberfest 2026: le issue che i maintainer hanno segnato per ottobre, aperte e adatte ai principianti. Sfoglia le issue Hacktoberfest

[PENDING] GSOC 2025: New function minDegreeOrdering to be added in pgRouting Functionality/experimental GSoC ordering

Aperta
  • Qualcosa non va?
#2,962 1 commento 0 reazioni 1 assegnatario Vedi su GitHub

I maintainer di solito rispondono entro 2 giorni

@wifiBlack ci sta già lavorando.

Dal 28/8/2025.

  • #2963 di @wifiBlack — aperta

Valutazione

Questa issue non è ancora stata valutata.

Descrizione

Functionality/experimental GSoC ordering

pgr_minDegreeOrdering():

minDegreeOrdering(): In numerical linear algebra, the MinDegree ordering is a heuristic used to reduce the amount of fill-in during sparse matrix factorization, such as Cholesky decomposition for symmetric matrices. When eliminating variables in a sparse system, new nonzero entries—called fill-ins—can appear in positions that were originally zero, increasing storage and computation costs. The minimum degree approach attempts to reorder the vertices (or equivalently, the rows and columns of the matrix) so that, at each elimination step, the vertex with the smallest degree is removed first, thereby reducing potential fill-in.

Main characteristics of the function:
  • The implementation targets undirected graphs.
  • The algorithm is a heuristic; finding the true optimal ordering is NP-complete.
  • The time complexity is: (O(|V| log |V| + |E|))
    • where (|V|) is the number of vertices,
    • (|E|) is the number of edges.
Signature:
  • minDegreeOrdering()
pgr_minDegreeOrdering(Edges SQL)

Returns set of (seq, node)
OR EMPTY SET
Parameters:
Parameter Type Description
Edges SQL TEXT Inner SQL query, as described below.
Inner Query:

Edges SQL: It should be an SQL query which should return 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 end point vertex of the edge
target ANY-INTEGER Identifier of the second end point vertex of the edge
cost ANY-NUMERICAL Weight of the edge (source, target). When negative: edge (source, target) does not exist on the graph.
reverse_cost ANY-NUMERICAL -1 Weight of the edge (target, source). When negative: edge (target, source) does not exist on the graph.

Where:
ANY-INTEGER = SMALLINT, INTEGER, BIGINT
ANY-NUMERICAL = SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Result Columns:

Returns SET OF (seq, node)

Column Type Description
seq BIGINT Sequence of the order starting from 1.
node BIGINT New ordering in reverse order.
Lingua principale
C++
Stelle
1.4k
Fork
397
Merge medio
2g 2h
PR unite (30g)
4

Preparare l'ambiente

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di pgRouting/pgrouting

Tutte le issue di pgRouting/pgrouting

Issue simili

Altre issue su C++

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.