sqlsql-servergraph-algorithmgraph-traversaltopological-sort

SQL query for topological sort


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);

enter image description here

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 ?


Solution

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