Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Как пронумеровать коротко-замкнутый граф  [new]
stenford
Member

Откуда: урал
Сообщений: 2850
Имеется граф, замкнутый сам на себя (node2 содержит node4, a node4 содержит node2):

declare @t table(nodeID int, nodeName varchar(50), parentID int)

insert into @t values(1, 'node1', null)
insert into @t values(2, 'node2', 1)
insert into @t values(3, 'node3', 1)
insert into @t values(4, 'node4', 2)
insert into @t values(2, 'node2', 4);

WITH Emp_CTE AS (
SELECT nodeID, nodeName, parentID
FROM @t
WHERE parentID IS NULL
UNION ALL
SELECT e.nodeID, e.nodeName, e.parentID
FROM @t e
INNER JOIN Emp_CTE ecte ON ecte.nodeID = e.parentID
)
SELECT *
FROM Emp_CTE


Kак пронумеровать теперь эти записи по уровням, что-б получилось типа такого:

Node:  Level
node1    0
node2    1
node3    1
node4    2



т.е. прогнорировать замкнутость и вывести максимальный номер уровня?
19 июн 13, 07:53    [14451538]     Ответить | Цитировать Сообщить модератору
 Re: Как пронумеровать коротко-замкнутый граф  [new]
LexusR
Member

Откуда: Novosibirsk
Сообщений: 1887
declare @t table(nodeID int, nodeName varchar(50), parentID int)

insert into @t values(1, 'node1', null)
insert into @t values(2, 'node2', 1)
insert into @t values(3, 'node3', 1)
insert into @t values(4, 'node4', 2)
insert into @t values(2, 'node2', 4);

WITH Emp_CTE AS (
SELECT nodeID, nodeName, parentid,0 as [level]
FROM @t
WHERE parentID IS NULL
UNION ALL
SELECT e.nodeID, e.nodeName, e.parentID,ecte.[level]+1 as [level]
FROM @t e
INNER JOIN Emp_CTE ecte ON ecte.nodeID = e.parentID and isnull(ecte.parentID,0) <> e.nodeID
)
SELECT *
FROM Emp_CTE
19 июн 13, 08:25    [14451589]     Ответить | Цитировать Сообщить модератору
 Re: Как пронумеровать коротко-замкнутый граф  [new]
stenford
Member

Откуда: урал
Сообщений: 2850
LexusR
declare @t table(nodeID int, nodeName varchar(50), parentID int)

insert into @t values(1, 'node1', null)
insert into @t values(2, 'node2', 1)
insert into @t values(3, 'node3', 1)
insert into @t values(4, 'node4', 2)
insert into @t values(2, 'node2', 4);

WITH Emp_CTE AS (
SELECT nodeID, nodeName, parentid,0 as [level]
FROM @t
WHERE parentID IS NULL
UNION ALL
SELECT e.nodeID, e.nodeName, e.parentID,ecte.[level]+1 as [level]
FROM @t e
INNER JOIN Emp_CTE ecte ON ecte.nodeID = e.parentID and isnull(ecte.parentID,0) <> e.nodeID
)
SELECT *
FROM Emp_CTE


:)

меня интересовал общий случай, ноды могут быть замкнуты через произвольное количество детей. Усложним задачу:

declare @t table(nodeID int, nodeName varchar(50), parentID int)

insert into @t values(1, 'node1', null)
insert into @t values(2, 'node2', 1)
insert into @t values(3, 'node3', 1)
insert into @t values(4, 'node4', 2)
insert into @t values(5, 'node5', 4)
insert into @t values(2, 'node2', 5);

WITH Emp_CTE AS (
SELECT nodeID, nodeName, parentid,0 as [level]
FROM @t
WHERE parentID IS NULL
UNION ALL
SELECT e.nodeID, e.nodeName, e.parentID,ecte.[level]+1 as [level]
FROM @t e
INNER JOIN Emp_CTE ecte ON ecte.nodeID = e.parentID and isnull(ecte.parentID,0) <> e.nodeID
)
SELECT *
FROM Emp_CTE
19 июн 13, 08:36    [14451614]     Ответить | Цитировать Сообщить модератору
 Re: Как пронумеровать коротко-замкнутый граф  [new]
Ennor Tiegael
Member

Откуда:
Сообщений: 3422
stenford,

Конструировать в CTE путь из пройденных узлов и проверять на каждом шаге, проходили здесь уже или нет.
19 июн 13, 08:41    [14451639]     Ответить | Цитировать Сообщить модератору
 Re: Как пронумеровать коротко-замкнутый граф  [new]
LexusR
Member

Откуда: Novosibirsk
Сообщений: 1887
declare @t table(nodeID int, nodeName varchar(50), parentID int)

insert into @t values(1, 'node1', null)
insert into @t values(2, 'node2', 1)
insert into @t values(3, 'node3', 1)
insert into @t values(4, 'node4', 2)
insert into @t values(5, 'node5', 4)
insert into @t values(2, 'node2', 5);

WITH Emp_CTE AS (
SELECT nodeID, nodeName, parentid,0 as [level],'$'+cast(nodeID as varchar(8000)) as [path]
FROM @t
WHERE parentID IS NULL
UNION ALL
SELECT e.nodeID, e.nodeName, e.parentID,ecte.[level]+1 as [level],ecte.path+'$'+cast(e.nodeID as varchar(10))
FROM @t e
INNER JOIN Emp_CTE ecte ON ecte.nodeID = e.parentID and ecte.path not like '%'+'$'+cast(e.nodeID as varchar(10))+'%'
)
SELECT *
FROM Emp_CTE
19 июн 13, 09:03    [14451720]     Ответить | Цитировать Сообщить модератору
 Re: Как пронумеровать коротко-замкнутый граф  [new]
LexusR
Member

Откуда: Novosibirsk
Сообщений: 1887
по наводке Ennor Tiegael
19 июн 13, 09:05    [14451731]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить