Wikis - Page Details

First published by Saeid Hasani
When: 29 Aug 2013 4:43 PM
Last revision by TNJMAN
When: 8 Sep 2013 10:33 AM
Revisions: 30
Comments: 30

Options

Can You Improve This Article?

Positively! Click Sign In to add the tip, solution, correction or comment that will help other users.

Report inappropriate content using these instructions.

Custom Sort in Acyclic Digraph

Problem definition
Vocabulary
Solution
See Also

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.

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 ,

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.

Products

Resources

Solutions

Updates

Trials

Related Sites

Training

Certifications

Other resources

Support options

More support

Not an IT pro?

Custom Sort in Acyclic Digraph

Custom Sort in Acyclic Digraph

Table of Contents

Problem definition

Vocabulary

Digraph (Directed Graph)

Acyclic Graph

Acyclic Digraph

Topological Ordering

Solution

See Also