Directional acyclic graph: find all paths from a specific node

Question

How to find all paths from a specific node (node ​​36 in the example)?

Let's say we have two tables:

  CATEGORIES CATEG_PARENTS
 id idc |  idparent
 - ----------------
 1 2 1
 2 2 20
 5 5 2
 8 8 5
 20 20 1
 22 22 8
 30 22 20
 31 30 20
 36 31 22
                 31 30
                 36 31

These are two possible representations:

alt text http://nebm.ist.utl.pt/~glopes/img/graphso.png alt text http://nebm.ist.utl.pt/~glopes/img/graphso2.png

This is the result I want:

  ids
 -------------------
 "{1,20,22,31}"
 "{1,20,2,5,8,22,31}"
 "{1,20,30,31}"
 "{1,2,5,8,22,31}"

One path per line, written as an integer array.

(I am going to write the answer that I came up with, but I agree that it is easier if there is one)

Answer 1

WITH RECURSIVE parent_line(path, id) AS ( SELECT ARRAY[(row_number() OVER (PARTITION BY CP.idc))::integer], C.id FROM categorias C JOIN categ_parents CP ON C.id = CP.idparent WHERE CP.idc = 36 UNION ALL SELECT PL.path || (row_number() OVER (PARTITION BY PL.id))::integer, C.id FROM categorias C JOIN categ_parents CP ON C.id = CP.idparent JOIN parent_line PL on CP.idc = PL.id ), real_parent_line(path, chainid, id) AS ( SELECT PL.path, (row_number() OVER (PARTITION BY PL.id)), PL.id FROM parent_line PL WHERE PL.id IN ( SELECT id FROM categorias C LEFT JOIN categ_parents CP ON (C.id = CP.idc) WHERE CP.idc IS NULL ) UNION ALL SELECT PL.path, chainid, PL.id FROM parent_line PL, real_parent_line RPL WHERE array_upper(PL.path,1) + 1 = array_upper(RPL.path,1) AND PL.path = RPL.path[1:(array_upper(RPL.path,1)-1)] ) SELECT array_accum(id) AS ids FROM real_parent_line RPL GROUP BY chainid; 

The first WITH clause gives the following:

  path |  id
 ------------------------
 "{1}" 31
 "{1,1}" 22
 "{1,2}" 30
 "{1,1,1}" 20
 "{1,1,2}" 8
 "{1,2,1}" 20
 "{1,1,2,1}" 5
 "{1,1,1,1}" 1
 "{1,2,1,2}" 1
 "{1,1,2,1,1}" 2
 "{1,1,2,1,1,1}" 1
 "{1,1,2,1,1,2}" 20
 "{1,1,2,1,1,2,1}" 1

Thanks to # postgresql @freenode for some help.