I am resolving dependency between some objects in a table. I have to do something with objects in order their dependency. For example, the first object doesn't depend on any object. The second and third ones depends on first one and so on. I have to use topological sorting. Could someone show the sample of implementation so sorting in t-sql. I have a table:
create table dependency
(
DependencyId PK
,ObjectId
,ObjectName
,DependsOnObjectId
)
I want to get
ObjectId ObjectName SortOrder
It seams, it works:
declare @step_no int
declare @dependency table
(
DependencyId int
,ObjectId int
,ObjectName varchar(100)
,DependsOnObjectId int
,[rank] int NULL
,degree int NULL
);
insert into @dependency values (5, 5, 'Obj 5', 2, NULL, NULL)
insert into @dependency values (6, 6, 'Obj 6', 7, NULL, NULL)
insert into @dependency values (2, 2, 'Obj 2', 1, NULL, NULL)
insert into @dependency values (3, 3, 'Obj 3', 1, NULL, NULL)
insert into @dependency values (1, 1, 'Obj 1', 1, NULL, NULL)
insert into @dependency values (4, 4, 'Obj 4', 2, NULL, NULL)
insert into @dependency values (7, 7, 'Obj 7', 2, NULL, NULL)
update @dependency set rank = 0
-- computing the degree of the nodes
update d set d.degree =
(
select count(*) from @dependency t
where t.DependsOnObjectId = d.ObjectId
and t.ObjectId <> t.DependsOnObjectId
)
from @dependency d
set @step_no = 1
while 1 = 1
begin
update @dependency set rank = @step_no where degree = 0
if (@@rowcount = 0) break
update @dependency set degree = NULL where rank = @step_no
update d set degree = (
select count(*) from @dependency t
where t.DependsOnObjectId = d.ObjectId and t.ObjectId != t.DependsOnObjectId
and t.ObjectId in (select tt.ObjectId from @dependency tt where tt.rank = 0))
from @dependency d
where d.degree is not null
set @step_no = @step_no + 1
end
select * from @dependency order by rank