PostgreSQL recursive query in order to get ranked edges

Question

I have a table with a huge amount of edges that are somehow related to each other (from_segment and to_segment). Every edge is devided into several different smaller sectors (from_meter and to_meter). Every smaller sector has a a specified direction.

See the following table:

DROP TABLE IF EXISTS network;
CREATE TABLE network (
  id integer PRIMARY KEY,
  from_segment text,
  to_segment text, 
  from_meter int,
  to_meter int,
  direction text
);

INSERT INTO network (id, from_segment, to_segment, from_meter, to_meter, direction) VALUES
  (1,'A', 'B', 0, 5,'X'),
  (2,'A', 'B', 0, 5,'Y'),
  (3,'A', 'B', 5,10,'X'),
  (4,'A', 'B', 5,10,'Y'),
  (5,'A', 'B',10,15,'X'),
  (6,'A', 'B',10,15,'Y'),
  (7,'A', 'B',15,20,'X'),
  (8,'A', 'B',15,20,'Y'),

  (9,'B', 'C', 0, 5,'X'),
  (10,'B', 'C', 0, 5,'Y'),
  (11,'B', 'C', 5,10,'X'),
  (12,'B', 'C', 5,10,'Y'),
  (13,'B', 'C',10,15,'X'),
  (14,'B', 'C',10,15,'Y'),
  (15,'B', 'C',15,20,'X'),
  (16,'B', 'C',15,20,'Y'),

  (17,'C', 'D', 0, 5,'X'),
  (18,'C', 'D', 0, 5,'Y'),
  (19,'C', 'D', 5,10,'X'),
  (20,'C', 'D', 5,10,'Y'),
  (21,'C', 'D',10,15,'X'),
  (22,'C', 'D',10,15,'Y'),

  (23,'E', 'F', 0, 5,'X'),
  (24,'E', 'F', 0, 5,'Y'),
  (25,'E', 'F', 5,10,'X'),
  (26,'E', 'F', 5,10,'Y'),

  (27,'K', 'L', 0, 5,'X'),
  (28,'K', 'L', 0, 5,'Y'),
  (29,'K', 'L', 5,10,'X'),
  (30,'K', 'L', 5,10,'Y'),
  (31,'K', 'L',10,15,'X'),
  (32,'K', 'L',10,15,'Y'),

  (33,'L', 'M', 0, 5,'X'),
  (34,'L', 'M', 0, 5,'Y');

What I would like to do is to bring the edges (also for every smaller sector and direction) into a specific rank/order:

from_segment| to_segment | result_1 | result_2
     A            B           1         1 
     B            C           1         2
     C            D           1         3
     E            F           2         1
     K            L           3         1
     L            M           3         2

I tried to finish the query with several different approaches, e.g. recursive function as well as the partition over approach but I failed every time. I guess the solution is somewhere in between but I have no idea how to solve the problem.

Thank you for your help!

user_10676716 · Answer

You want to walk distinct (from_segment, to_segmgent) tuples, while numbering the paths, and the nodes along each path.

This recursive query should do what you want:

with recursive
    data as (
        select distinct from_segment, to_segment from network
    ),
    rcte as (
        select 
            from_segment, 
            to_segment, 
            row_number() over(order by from_segment) result_1,
            1 result_2
        from data d
        where not exists (
            select 1 from data d1 where d1.to_segment = d.from_segment
        )
        union all
        select  
            d.from_segment,
            d.to_segment,
            r.result_1,
            r.result_2 + 1
        from rcte r
        inner join data d on d.from_segment = r.to_segment
    )
select * from rcte order by result_1, result_2

The first cte lists the distinct tuples; then the recursive cte starts from the beginning of each path, ranks them with row_number(), and then walks each path, incrementing a counter along the way.

Demo on DB Fiddle:

from_segment | to_segment | result_1 | result_2
:----------- | :--------- | -------: | -------:
A            | B          |        1 |        1
B            | C          |        1 |        2
C            | D          |        1 |        3
E            | F          |        2 |        1
K            | L          |        3 |        1
L            | M          |        3 |        2

PostgreSQL recursive query in order to get ranked edges

1 Answers