PostgreSQL 11.2 Group objects by common attribute in single table

Question

I work on a network dataset (with PostGIS extension, but since my current method using pgrouting is the only one I found to do what I want and it is extremely painful to run, I want to try and deal with it by attributes) such as the picture below :

Each section (letters) is a single object, and the color is the relevant attribute of the objects.

The table representing this is defined as such :

CREATE TABLE lines (gid text, color text, startpoint integer, endpoint integer);
INSERT INTO lines (gid, color, startpoint, endpoint) 
VALUES 
    ('A','green', 1, 2), 
    ('B','green', 2, 3), 
    ('C','green', 3, 4), 
    ('D','green', 4, 5), 
    ('E','red', 2, 6), 
    ('F','red', 6, 7), 
    ('G','red', 7, 8), 
    ('H','blue', 3, 9), 
    ('I','blue', 4, 10), 
    ('J','blue', 10, 11);

The result I want to get is an aggregate object made of all the objects of the same color which touches each other. So here it would be 4 objects : {A,B,C,D}, {E,F,G}, {H} and {I,J}. I assume the way to go is to use the startpoint and endpoint values since they are determining the touching aspect of the objects.

For now I went like the code below, using a JOIN so the object H is returned (if I were to use a WHERE clause identical to the ON condition the H wouldn't be returned since it would never match the startpoint/endpoint correlation) :

SELECT a.gid, b.gid, a.color 
FROM lines a 
LEFT JOIN lines b ON a.gid > b.gid AND (a.startpoint = b.endpoint OR a.endpoint = b.startpoint) AND a.color = b.color

With this result :

And from here I don't know how to do. I use an aggregating function in PostGIS to merge the lines, so I suppose I need to have results in this form (so then I can run a query with GROUP BY) :

Would anyone know of a way to do what I want to do?

user_10676716 · Answer

Assuming that your data has no cirles, as shown in your sample data, an option is to use a recursive query.

The idea is to first identify all starting points for each color. For this, you can use not exsits:

select l.*
from lines l
where not exists (
    select 1 from lines l1 where l1.endpoint = l.startpoint and l1.color = l.color
)

From there on, you can recursively traverse the structure, by looking for lines of the same color that start where the previous one ended, while keeping track of the lines path in an array.

The final step is to filter the resultset to identify non-overlapping paths. For this, we can use not exists with the containment operator.

Note that this technique allows for branches, if any.

Code:

with recursive cte as (
    select l.*, array[gid] path
    from lines l
    where not exists (
        select 1 from lines l1 where l1.endpoint = l.startpoint and l1.color = l.color
    )
    union all 
    select l.*, c.path || l.gid
    from cte c
    inner join lines l on l.startpoint = c.endpoint and l.color = c.color
)
select color, path
from cte c
where not exists (select 1 from cte c1 where c1.path @> c.path and not c.path @> c1.path)
order by color, path

Demo on DB Fiddle:

color | path     
:---- | :--------
blue  | {H}      
blue  | {I,J}    
green | {A,B,C,D}
red   | {E,F,G}

PostgreSQL 11.2 Group objects by common attribute in single table

1 Answers