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 ?
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.