dag sort

gistfile1.txt

with recursive
dag (depended_on,dependent) as
  (
      values
      ('b2'::text,'d1'::text),
      ('d1','d2'),
      ('d2','d3'),
      ('d3','d4'),
      ('b1','a1'),
      ('b2','a1'),
      ('a1','c1'),
      ('d4','a1')
      -- expected order is:
      -- c1 a1 d4 d3 d2 d1 b2 with b1 anywhere after a1
  )
  --- continue here ...
  
  -- solution from RhodiumToad
with recursive r(item,path) as (select dependent, array[]::text[] from dag d1 where not exists (select 1 from dag d2 where d2.depended_on=d1.dependent) union all select depended_on, path || dependent from dag join r on (r.item=dag.dependent)) select * from (select distinct on (item) item,path from r order by item, cardinality(path) desc) s order by cardinality(path);