Convert a table of edge descriptions to a list of arrays containing trees

Question

I've got two tables in Snowflake, which define a bunch of graphs. They look like this:

Node Table:

node    family     
A       1
B       1
C       1
D       1
E       1
F       1
G       1
H       1
I       2
J       2

etc...

Edge Table:

to   from
A        B
B        C
B        D
D        E
F        G
G        H

etc...

A family describes a collection of one or more related graphs; some of these may be a single graph, others may be several small graphs etc. The graphs are unidirectional and may have several branches/forks. There is currently no label for each of these graphs (that is, it needs to be inferred from the connections).

I'd like to create a table with a list of graphs in it, such as:

family   id    structure
1        1     [A -> B -> C, B -> D -> E]
1        2     [F -> G -> H] 
2 ... etc...

Where each row represents a set of connected nodes and the structure of that set and id is a new label for the graph object.

I've made some progress using recursive CTEs but hit a wall. Any help highly appreciated!

user_43992 · Answer

Firstly we need to build the recursions.

WITH nodes(node, family) AS (
    SELECT * 
    FROM VALUES
        ('A',1),
        ('B',1),
        ('C',1),
        ('D',1),
        ('E',1),
        ('F',1),
        ('G',1),
        ('H',1),
        ('I',2),
        ('J',2)
), edges(_from, _to) AS (
    SELECT * 
    FROM VALUES
        ('A','B'),
        ('B','C'),
        ('B','D'),
        ('D','E'),
        ('F','G'),
        ('G','H')
), recursive_wrapper AS (
    WITH recur AS (
        -- Anchor Clause
        select
            family, 
            node, 
            node as tail, 
            array_construct(node) path, 
            1 as depth
        from nodes
        
        union all

        -- Recursive Clause
        select r.family,
            r.node,
            e._to as tail,
            ARRAY_APPEND(r.path, e._to) as path,
            r.depth + 1 as depth 
        from recur AS r
        join edges AS e
            on r.tail = e._from
    )
    SELECT * 
    FROM recur
)
SELECT * 
FROM recursive_wrapper
WHERE node = 'A'

gives:

FAMILY	NODE	TAIL	PATH	DEPTH
1	A	A	[ "A" ]	1
1	A	B	[ "A", "B" ]	2
1	A	C	[ "A", "B", "C" ]	3
1	A	D	[ "A", "B", "D" ]	3
1	A	E	[ "A", "B", "D", "E" ]	4

Then we need to prune the sublimated rows (in above we want to remove depth 1,2,4 as they are sub parts of another row), we can do this by swapping from an array to a string for path

), recursive_wrapper AS (
    WITH recur AS (
        -- Anchor Clause
        select
            family, 
            node, 
            node as tail, 
            node::text path, /* this cast it to max size, verse the largest size of the input */
            1 as depth
        from nodes
        
        union all

        -- Recursive Clause
        select r.family,
            r.node,
            e._to as tail,
            r.path || '_' || e._to as path,
            r.depth + 1 as depth 
        from recur AS r
        join edges AS e
            on r.tail = e._from
    )
    SELECT * 
    FROM recur
)
SELECT a.*
    ,b.path as b_path
    ,b.depth as b_depth
    ,startswith(b.path, a.path) as starts
    ,sum(iff(starts,1,0)) over(partition by a.family, a.node, a.path) as dominated_count
FROM recursive_wrapper as a
LEFT JOIN recursive_wrapper as b 
    ON a.family = b.family AND a.node = b.node AND a.depth < b.depth
WHERE a.node = 'A'
ORDER BY 1,2,4;

gives:

FAMILY	NODE	TAIL	PATH	DEPTH	B_PATH	B_DEPTH	STARTS	DOMINATED_COUNT
1	A	A	A	1	A_B	2	TRUE	4
1	A	A	A	1	A_B_C	3	TRUE	4
1	A	A	A	1	A_B_D	3	TRUE	4
1	A	A	A	1	A_B_D_E	4	TRUE	4
1	A	B	A_B	2	A_B_C	3	TRUE	3
1	A	B	A_B	2	A_B_D	3	TRUE	3
1	A	B	A_B	2	A_B_D_E	4	TRUE	3
1	A	C	A_B_C	3	A_B_D_E	4	FALSE	0
1	A	D	A_B_D	3	A_B_D_E	4	TRUE	1
1	A	E	A_B_D_E	4				0

so we want to just keep those with a count of zero, which we can do in a QUALIFY

SELECT a.*
    --,b.path as b_path
    --,b.depth as b_depth
    --,startswith(b.path, a.path) as starts
    --,sum(iff(starts,1,0)) over(partition by a.family, a.node, a.path) as dominated_count

FROM recursive_wrapper as a
LEFT JOIN recursive_wrapper as b 
    ON a.family = b.family AND a.node = b.node AND a.depth < b.depth
WHERE a.node = 'A'
QUALIFY sum(iff(startswith(b.path, a.path),1,0)) over(partition by a.family, a.node, a.path) = 0
ORDER BY 1,2,4;

gives:

FAMILY	NODE	TAIL	PATH	DEPTH
1	A	C	A_B_C	3
1	A	E	A_B_D_E	4

This will explode with loops, which we can protect against by put the array back, and checking for the value already being in the array

WITH nodes(node, family) AS (
    SELECT * 
    FROM VALUES
        ('A',1),
        ('B',1),
        ('C',1),
        ('D',1),
        ('E',1),
        ('F',1),
        ('G',1),
        ('H',1),
        ('I',2),
        ('J',2)
), edges(_from, _to) AS (
    SELECT * 
    FROM VALUES
        ('A','B'),
        ('B','C'),
        ('B','D'),
        ('D','E'),
        ('F','G'),
        ('G','H')
), recursive_wrapper AS (
    WITH recur AS (
        -- Anchor Clause
        select
            family, 
            node, 
            node as tail, 
            node::text path, /* this cast it to max size, verse the largest size of the input */
            array_construct(node) a_path, 
            1 as depth
        from nodes
        
        union all

        -- Recursive Clause
        select r.family,
            r.node,
            e._to as tail,
            r.path || '_' || e._to as path,
            ARRAY_APPEND(r.a_path, e._to) as a_path,
            r.depth + 1 as depth 
        from recur AS r
        join edges AS e
            on r.tail = e._from AND ARRAY_CONTAINS( e._to::variant , r.a_path ) = FALSE
    )
    SELECT * 
    FROM recur
)
SELECT a.*
FROM recursive_wrapper as a
LEFT JOIN recursive_wrapper as b 
    ON a.family = b.family AND a.node = b.node AND a.depth < b.depth
QUALIFY sum(iff(startswith(b.path, a.path),1,0)) over(partition by a.family, a.node, a.path) = 0
ORDER BY 1,2,4;

user_16582 · Answer

- Extract the two tables into your favorite programming language.
- Create a set of families
- Iterate F over family set
    - Iterate over rows in node table
         - If node belongs to F
              - Add node to vector
    - Construct empty adjacency matrix ( square 2D vector of size node vector size
    - Iterate N1 over node vector
          - Iterate N2 != N1 over node vector
                - IF N1-N2 in edge table
                       - Add to adjacency matrix
    - Iterate N1 over node vector
          - IF N1 has zero in-edges
               - Output tree rooted at N1

Convert a table of edge descriptions to a list of arrays containing trees

2 Answers