Multigraph input semantics for pgr_coreNumbers (parallel edges and self-loops)

pgRouting pgrouting-dev
1

Hi! @cvvergara @robe,

I have a design question about pgr_coreNumbers.

The standard definition of the k-core is stated for simple graphs:

  • the k-core is the maximal subgraph in which every vertex has degree ≥ k
  • the core number of a vertex is the largest k for which it belongs to the k-core
  • on n vertices the maximum possible core number is n - 1 (the complete graph Kₙ)

In my current implementation the initial degree comes straight from src/metrics/coreNumbers.cpp:

degree[*vi] = boost::out_degree(*vi, graph.graph);

Since pgrouting::UndirectedGraph is a multigraph, out_degree counts every parallel edge separately and counts a self-loop twice. So the peeling operates on multigraph degrees, not simple-graph degrees.

While adding degenerate-input pgTAP tests for week 8 I measured what this produces:

  • one edge 1-2 → 1:1 2:1
  • two parallel edges 1-2 → 1:2 2:2
  • three parallel edges 1-2 → 1:3 2:3
  • a single self-loop 1-1 → 1:2
  • self-loop 1-1 plus edge 1-2 → 1:2 2:1

However, two of these are not reachable under the simple-graph definition:

  • three parallel edges between two vertices report core 3, but on two vertices the maximum possible core number is 1
  • a lone self-loop reports core 2, but that vertex has no neighbours at all and would be core 0

Also, in the existing pgRouting codebase this behaviour already has a precedent. pgr_degree - a released, non-experimental function in the same family reports exactly the same degrees on the same inputs:

  • two parallel edges 1-2 → pgr_degree gives 1:2 2:2, pgr_coreNumbers gives 1:2 2:2
  • three parallel edges 1-2 → pgr_degree gives 1:3 2:3, pgr_coreNumbers gives 1:3 2:3
  • a single self-loop 1-1 → pgr_degree gives 1:2, pgr_coreNumbers gives 1:2

So pgr_coreNumbers is already consistent with pgr_degree; it is not introducing a new convention.

This leaves me unsure which approach to follow:

Option A (Matches pgr_degree): keep multigraph degrees as they are, and document the consequence explicitly in pgr_coreNumbers.rst- that core numbers scale with edge multiplicity, so users importing road networks with duplicate geometry may see inflated cores. This keeps the metrics family internally consistent.

Option B (Match the textbook definition): collapse parallel edges and drop self-loops before peeling, so pgr_coreNumbers always reports simple-graph core numbers. This matches the published definition and the values users would compute by hand, but makes pgr_coreNumbers and pgr_degree disagree on the same input.

My pgTAP tests currently pin the existing (Option A) behaviour, so they document what the function does today - I can flip them if Option B is preferred.

Which approach would you prefer?
thank you
sakirr

2

Hi @sakirr05

My first step is trying to understand the graph you need as input, so here is a graph with 2 edges

SELECT 100 AS id, 1 AS source, 2 AS target, 8.5 AS cost 
UNION 
SELECT 101, 1, 2, 7.5; 
 id  | source | target | cost 
-----+--------+--------+------
 100 |      1 |      2 |  8.5
 101 |      1 |      2 |  7.5
(2 rows)

In pgRouting, depending on the function it can represent many graphs

Is “representing” the following graph

graph G { 1 -- 2 [label="8.5"] 1 -- 2 [label="7.5"] }

Is “representing” the following graph

digraph G { 1 -> 2 [label="8.5"] 1 -> 2 [label="7.5"] }

Is “representing” the following graph

digraph G { 1 -> 2 [label="7.5"] }

Is “representing” the following graph

graph G { 1 -- 2 [label="7.5"] }

We certainly have the ability to read edges discarding parallel edges with higher cost, as you can see here

The code snippet where its was used

pgrouting::UndirectedGraph undigraph;
undigraph.insert_min_edges_no_parallel(edges);
pgrouting::functions::Pgr_primpgrouting::UndirectedGraph prim;

which made me notice that I missed using it on develop. :frowning:

If you need it use it.

3

Hi @cvvergara,

thanks, that clears it up. and the insert_min_edges_no_parallel pointer helps a lot.

so for pgr_coreNumbers the graph is always built undirected, so your first drawing is basically what happens right now, it keeps both parallel edges:

graph G { 1 -- 2 [label="8.5"] 1 -- 2 [label="7.5"] }

degree of both nodes ends up as 2 since each edge is counted separately, that’s why 3 parallel edges gave core 3 in my earlier test.

i looked at graph_add_min_edge_no_parallel and if i switch coreNumbers_driver.cpp to use insert_min_edges_no_parallel instead, this same input collapses to your 4th drawing, only the cheaper edge survives:

graph G { 1 -- 2 [label="7.5"] }

degree becomes 1 for both, which lines up with the normal definition and fixes the parallel edge case.

but self loops are still an issue even after that change. the function only dedups when source and target are different, so a self loop still gets added and still counts toward degree. e.g. this input, one self loop on node 1 plus a normal edge to node 2:

graph G { 1 [label="1\n(core 2)"] 2 [label="2\n(core 1)"] 1 -- 1 [label="self-loop, +2 to degree"] 1 -- 2 [label="7.5"] }

node 1 ends up core 2 and node 2 ends up core 1, because the loop alone gives node 1 degree 2 before the peeling even looks at its real neighbor. insert_min_edges_no_parallel wouldn’t change this since source and target are the same vertex, so this stays untouched by the switch.

so i think i’ll go ahead and switch to insert_min_edges_no_parallel for the parallel edge part, that seems like the right call since prim already does it. self loops i’ll leave open for now unless you think it needs handling too.
thanks
sakir