Custom Sort in Acyclic Digraph
Problem definition
This article is derived from this MSDN forum post. This article addresses the task of how to present a Tree in a custom order. In fact, the article title could be pre-order tree traversal.
Vocabulary
Digraph (Directed Graph)
A digraph is a graph, or a set of nodes connected by the edges, where the edges have a direction associated with them.
Acyclic Graph
An acyclic graph is a graph without any cycle.
Acyclic Digraph
An acyclic digraph (directed acyclic graph), also known as a DAG, is a directed graph with no directed cycles.
Topological Ordering
Every DAG has a topological ordering, an ordering of the vertices such that the starting endpoint of every edge occurs earlier in the ordering than the ending endpoint of the edge.
Solution
The code below resolves the stated problem of how to present a non-topological ordering of a DAG (i.e., custom sorting an acyclic digraph). Executing the following script will create and populate a resultant test table demonstrating the stated solution.
IF OBJECT_ID('tempdb..#test', 'U') IS NOT NULL
DROP TABLE #test;
GO
CREATE TABLE #test
(
Childid INT ,
parentid INT
);
GO
INSERT INTO #test
( Childid, parentid )
VALUES
( 100, 0 ),
( 102, 100 ),
( 103, 100 ),
( 104, 102 ),
( 105, 102 ),
( 106, 104 ),
( 107, 103 ),
( 109, 105 );
GO
The image below shows the sample data used in this solution.
The desired order is shown below. As you can see, It's very important to select with right order (for example 104 just after 102).
The solution is to produce paths that differ from topological ordering. In the following code, changing the ORDER BY list in the ROW_NUMBER function changes the sort order, producing paths that differ from the topological ordering.
DECLARE @rootId AS INT = 100;
WITH Subs
AS ( SELECT Childid ,
1 AS lvl ,
CAST(1 AS VARBINARY(MAX)) AS PathSort
FROM #test
WHERE Childid = @rootId
UNION ALL
SELECT C.Childid ,
P.lvl + 1 ,
P.PathSort + CAST(ROW_NUMBER() OVER ( PARTITION BY C.parentid ORDER BY C.Childid ) AS BINARY(5))
FROM Subs AS P
JOIN #test AS C ON C.parentid = P.Childid
)
SELECT Childid ,
ROW_NUMBER() OVER ( ORDER BY PathSort ) AS CustomSort,
REPLICATE(' | ', lvl) + CAST(Childid AS NVARCHAR(100)) ChildInTree
FROM Subs
ORDER BY CustomSort;
The resulting output is shown in the following figure.
