SQL query for topological sort

Question

I have a directed acyclic graph:

DROP TABLE IF EXISTS #Edges
CREATE TABLE #Edges(from_node int, to_node int);
INSERT INTO #Edges VALUES (1,2),(1,3),(1,4),(5,1);

I want to list all nodes, always listing a to node before its from node. For example: 2, 3, 4, 1, 5.

It is also called a topological ordering. How can it be done in SQL ?

Answer 1

You can use a recursive CTE to calculate the depth. Then order by the depth:

with cte as (
      select e.from_node, e.to_node, 1 as lev
      from edges e
      where not exists (select 1 from edges e2 where e2.to_node = e.from_node)
      union all
      select e.from_node, e.to_node, lev + 1
      from cte join
           edges e
           on e.from_node = cte.to_node
     )
select *
from cte
order by lev desc;

EDIT:

I notice that you do not have "1" in your edges list. To handle this:

with cte as (
      select 1 as from_node, e.from_node as to_node, 1 as lev
      from edges e
      where not exists (select 1 from edges e2 where e2.to_node = e.from_node)
      union all
      select e.from_node, e.to_node, lev + 1
      from cte join
           edges e
           on e.from_node = cte.to_node
      -- where lev < 5
     )
select *
from cte
order by lev desc;

Here is a db<>fiddle.