adunstan · November 11, 2015 21:14 · Nov 11, 2015 · Nov 11, 2015 · Nov 11, 2015 · Nov 11, 2015
diff --git a/gistfile1.txt b/gistfile1.txt
@@ -14,3 +14,6 @@ dag (depended_on,dependent) as
       -- 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);
diff --git a/gistfile1.txt b/gistfile1.txt
@@ -1,5 +1,5 @@
 with recursive
-vals (depended_on,dependent) as
+dag (depended_on,dependent) as
   (
       values
       ('b2'::text,'d1'::text),

diff --git a/gistfile1.txt b/gistfile1.txt
@@ -13,4 +13,4 @@ vals (depended_on,dependent) as
       -- expected order is:
       -- c1 a1 d4 d3 d2 d1 b2 with b1 anywhere after a1
   )
-  --- contrinue here ...
+  --- continue here ...
diff --git a/gistfile1.txt b/gistfile1.txt
@@ -0,0 +1,16 @@
+with recursive
+vals (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
+  )
+  --- contrinue here ...