Resources For IT Professionals

# Custom Sort in Acyclic Digraph

## 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 ,`
`                        ````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.

Wiki - Revision Comment List(Revision Comment)
Sort by: Published Date | Most Recent | Most Useful
• TNJMAN edited Revision 28. Comment: added wiki reference/citation for the definition of a "tree"

• TNJMAN edited Revision 27. Comment: minor fix.

• TNJMAN edited Revision 26. Comment: added acyclic digraph wiki ref/citation

• TNJMAN edited Revision 24. Comment: minor syntax correction ("...desired order is shown below.")

• TNJMAN edited Revision 23. Comment: Utilize pre-defined acronym vs. full name (i.e., "DAG")

• TNJMAN edited Revision 22. Comment: Parenthetical

• TNJMAN edited Revision 21. Comment: more bling

• TNJMAN edited Revision 20. Comment: some cleanup

• TNJMAN edited Revision 19. Comment: clarified the Solution section.

• TNJMAN edited Revision 18. Comment: more cleanup

Page 1 of 2 (18 items) 12
Wikis - Comment List
Sort by: Published Date | Most Recent | Most Useful
Posting comments is temporarily disabled until 10:00am PST on Saturday, December 14th. Thank you for your patience.
• That was really good piece of code and it helped me a lot in solving my issue.

• Thanks Kalman,

• See similar tree traverse logic in AdventureWorks orgchart:

www.sqlusa.com/.../organizationtree

• Thanks!

• Good job, overall.  Curious, what happened to "101" and "108" in your data points? You have all the other values. It doesn't really matter, since it's a valid example/solution, as-is, but it just made me curious. Thanks.

• TNJMAN edited Revision 28. Comment: added wiki reference/citation for the definition of a "tree"

• TNJMAN edited Revision 27. Comment: minor fix.

• TNJMAN edited Revision 26. Comment: added acyclic digraph wiki ref/citation

• TNJMAN edited Revision 25. Comment: more minor fixes

• TNJMAN edited Revision 24. Comment: minor syntax correction ("...desired order is shown below.")

• TNJMAN edited Revision 23. Comment: Utilize pre-defined acronym vs. full name (i.e., "DAG")

• TNJMAN edited Revision 22. Comment: Parenthetical

• TNJMAN edited Revision 21. Comment: more bling

• TNJMAN edited Revision 20. Comment: some cleanup

• TNJMAN edited Revision 19. Comment: clarified the Solution section.

Page 1 of 2 (30 items) 12