Добро пожаловать в форум, Guest >> Войти | Регистрация | Поиск | Правила | | В избранное | Подписаться | ||
Все форумы / Microsoft SQL Server |
![]() ![]() |
Топик располагается на нескольких страницах: [1] 2 3 вперед Ctrl→ все |
uaggster Member Откуда: Сообщений: 960 |
Коллеги, приветствую! Есть задача, к которой даже не знаю, с какой стороны подступиться, весь мозг сломал. Имеется таблица, содержащая набор произвольных графов. Графы в т.ч. - содержат петли. Необходимо "размотать" граф, и "вытащить" его за самый тяжелый узел. Create table graph (parent bigint not NULL, child bigint not NULL, [weight] int not NULL) insert into graph Values -- 1 граф (1, 1, 1), (1, 2, 1), (1, 3, 10), (2, 3, 2), (3, 1, 3), (3, 6, 1), (6, 6, 2) -- 2 граф (4, 4, 1), (4, 5, 1), (5, 4, 2), (5, 4, 1) На выходе нужно получить:
Граф представлен как совокупность нод: узел -> смежный узел -> вес узла. Преобразовать его нужно, "Навесив" все достижимые узлы на узел, имеющий максимальный вес в каком либо из состояний. Т.е., в первом графе максимальный вес имеет узел 1, см. (1, 3, 10), это вес 10. Поэтому он считается "главным", а остальные достижимые узлы, в т.ч. - он сам - его дочерними. Обратите внимание, что сам граф - имеет петли, а узел №6 - непосредственно из узла №1 - недостижим (но достижим через другие узлы). Второй граф имеет самый "массивный" узел (5, 4, 2), 5 имеет вес 2, остальные состояния - только вес 1, поэтому он и считается главным. Это не совсем взвешенный граф, но так получилось. Собственно, меня устроит любое решение, не обязательно "Одним запросом". В таблице - множество графов. Но если не получится преобразовать ее целиком, меня устроит решение, когда на вход подается нода, например parent = 1, а на выходе возвращается такая "матрица смежности" (это не матрица смежности, я понимаю, но тем не менее). ... я тогда курсором переберу все, объем небольшой, пара миллионов вхождений всего. Может ли облегчить задачу тот факт, что нод в любом из графов - заведомо не более 100? Если кандидатов на самую массивную ноду в графе - несколько, то нужно выбрать одну и только одну главную ноду произвольно. |
|||||||||||||||
28 июн 19, 09:40 [21916755] Ответить | Цитировать Сообщить модератору |
Ролг Хупин Member Откуда: Чебаркуль Сообщений: 3975 |
В тему SQL Graph Architecture https://docs.microsoft.com/en-us/sql/relational-databases/graphs/sql-graph-architecture?view=sql-server-2017 |
28 июн 19, 10:17 [21916780] Ответить | Цитировать Сообщить модератору |
uaggster Member Откуда: Сообщений: 960 |
Блин, у меня 2016SP2. Сейчас поставлю триал 2017. Хотя нужно вкуривать новую для себя концепцию. Чисто реляционного решения никто не знает? Фактически, как я понимаю, нужна функция, которая по номеру ноды вернет список всех достижимых из нее узлов, с весами. Всё осложняется произвольными петлями в графе. |
28 июн 19, 10:33 [21916811] Ответить | Цитировать Сообщить модератору |
Ролг Хупин Member Откуда: Чебаркуль Сообщений: 3975 |
Решение есть, я просто дал ссылку на тип данных,который уже сделан майкрософтом, может быть его использование поможет. Вы же версию сервера не указали. Кроме того, есть тип HierarchyID, для работы с иерархиями, это так, к слову. |
||
28 июн 19, 10:41 [21916819] Ответить | Цитировать Сообщить модератору |
uaggster Member Откуда: Сообщений: 960 |
Ролг Хупин, проблема в том, что там как раз не иерархия. Там большая часть - петли, но иногда осложненные перемычками. |
28 июн 19, 10:54 [21916835] Ответить | Цитировать Сообщить модератору |
aleks222 Member [заблокирован] Откуда: Сообщений: 1240 |
1. Добавь в табличку поле: ID_graph - идентификатор графа 2. Заполни. 3. Все станет тривиальным. |
||
28 июн 19, 12:58 [21916967] Ответить | Цитировать Сообщить модератору |
uaggster Member Откуда: Сообщений: 960 |
aleks222, А где его взять, идентификатор то? Для того, чтобы сгенерировать идентификатор, нужно определить все ноды, которые в него входят. Ну, т.е. определить сам граф, в куче других. Вот эти ноды - один граф, вот эти - другой. А как это сделать? |
28 июн 19, 13:14 [21916982] Ответить | Цитировать Сообщить модератору |
Konst_One Member Откуда: Сообщений: 11567 |
-- 2 граф (4, 4, 1), (4, 5, 1), (5, 4, 2), (5, 4, 1) что-то странный граф. если верхушка от 4, то почему там 5, 4 варианты попали? |
28 июн 19, 13:16 [21916986] Ответить | Цитировать Сообщить модератору |
uaggster Member Откуда: Сообщений: 960 |
Это не дерево. А граф общего вида. Нет у него верхушки. А ноды - перечислены, как перечислены. (5, 4, 2), (5, 4, 1) - да, перечислена дважды. Но вес "ситуации" - разный. (4, 4, 1) - да, нода указывает на саму себя. (4, 5, 1), (5, 4, 2), (5, 4, 1) - да, две ноды взаимно указывают друг на друга, причем нода 4 указывает на ноду 5 - один раз, а нода 5 на ноду 4 - дважды, имея при этом разные веса (можно трактовать как вес ребра). |
||
28 июн 19, 13:31 [21917011] Ответить | Цитировать Сообщить модератору |
Konst_One Member Откуда: Сообщений: 11567 |
graph (parent bigint not NULL, child bigint not NULL как так? у вас сполошное закольцовывание, это замкнутый граф. и другие графы ваши сложно определяемы, так как нет ограничений на "раскрутку", это задача без лимитов и ограничений не решаема. 4,4 4,5 5,4 5,5 |
28 июн 19, 13:36 [21917020] Ответить | Цитировать Сообщить модератору |
Владислав Колосов Member Откуда: Сообщений: 8340 |
uaggster, имо эта задача решается рекурсивными алгоритмами и не с помощью T-SQL. |
28 июн 19, 13:38 [21917022] Ответить | Цитировать Сообщить модератору |
uaggster Member Откуда: Сообщений: 960 |
Ну вот такие графы :-( Ограничение есть. В каждом конкретном графе - заведомо меньше 100 нод. Точнее даже не нод, а записей вида (4, 4, 1), описывающих связь. |
||
28 июн 19, 14:04 [21917055] Ответить | Цитировать Сообщить модератору |
iap Member Откуда: Москва Сообщений: 47052 |
Чтобы не зациклиться, надо организовать поле в рекурсивном CTE, в котором накапливать список пройденных узлов, чтобы не проходить узел дважды. |
28 июн 19, 15:10 [21917128] Ответить | Цитировать Сообщить модератору |
a_voronin Member Откуда: Москва Сообщений: 4807 |
uaggster, Сделайте обход вашего дерева-графа по принципу левый - корень - правый с помощью рекурсии и полученный линейный спиcок пробейте NTILE. Функция NTile(2) порежет ваш список примерно пополам без всяких долгих гемороев. https://docs.microsoft.com/ru-RU/sql/t-sql/functions/ntile-transact-sql?view=sql-server-2017 |
28 июн 19, 15:41 [21917151] Ответить | Цитировать Сообщить модератору |
court Member Откуда: Сообщений: 2250 |
Нужно найти несвязанные подграфы |
||
28 июн 19, 15:47 [21917158] Ответить | Цитировать Сообщить модератору |
uaggster Member Откуда: Сообщений: 960 |
Вот что мне нужно, как я понимаю: SHORTEST_PATH https://docs.microsoft.com/ru-ru/sql/relational-databases/graphs/sql-graph-shortest-path?view=sqlallproducts-allversions&viewFallbackFrom=sql-server-2017 Но оно, сцуко, доступно только с 2019. |
28 июн 19, 16:41 [21917201] Ответить | Цитировать Сообщить модератору |
court Member Откуда: Сообщений: 2250 |
![]()
и что это тебе даст ? вот тебе возможные пути в графе, - что дальше ? :) Как из этого, "по-простому" определить, что у тебя 2-а подграфа, и уже в них (в 2-х) искать максимальное ребро ... ? ;with cte as ( select start_node =parent ,node =child ,[path] =cast('/'+cast(parent as varchar(10))+'/'+cast(child as varchar(10))+'/' as varchar(max)) from graph where parent<>child union all select cte.start_node ,node =t.child ,[path] =cast(cte.[path]+cast(t.child as varchar(10))+'/' as varchar(max)) from graph t inner join cte on t.parent=cte.node where cte.[path] not like '%/'+cast(t.child as varchar(10))+'/%' ) select * from cte order by 1
|
||||||||||||||||||||||||||||||||||||||||||||||||||
28 июн 19, 17:16 [21917230] Ответить | Цитировать Сообщить модератору |
invm Member Откуда: Москва Сообщений: 9644 |
drop table if exists #t; declare @g table (parent bigint not NULL, child bigint not NULL, [weight] int not NULL); insert into @g Values -- 1 граф (1, 1, 1), (1, 2, 1), (1, 3, 10), (2, 3, 2), (3, 1, 3), (3, 6, 1), (6, 6, 2), -- 2 граф (4, 4, 1), (4, 5, 1), (5, 4, 2), (5, 4, 1); with g as ( select parent as root, parent, child, '/' + cast(parent as varchar(max)) as [path] from @g union all select g.root, c.parent, c.child, g.[path] + p.[path] from g join @g c on c.parent = g.child cross apply (select '/' + cast(c.parent as varchar(10))) p([path]) where g.[path] + '/' not like '%' + p.[path] + '/%' ) select root, parent, child, [path] + '/' as [path] into #t from g; with s as ( select a.root, string_agg(a.child, '/') within group (order by a.child) as graph_id from (select distinct root, child from #t) a group by a.root ), w as ( select s.*, row_number() over (partition by s.graph_id order by g.weight desc) as rn from s join @g g on g.parent = s.root ) select distinct w.root, t.child from w join #t t on t.root = w.root where w.rn = 1 order by w.root; |
28 июн 19, 19:10 [21917298] Ответить | Цитировать Сообщить модератору |
aleks222 Member [заблокирован] Откуда: Сообщений: 1240 |
Элементарно, Ватсон. declare @graph table (parent bigint not NULL, child bigint not NULL, [weight] int not NULL, gID bigint, primary key(parent, child, [weight]), unique(child, parent, [weight]) ); insert into @graph(parent, child, [weight]) Values -- 1 граф (1, 1, 1), (1, 2, 1), (1, 3, 10), (2, 3, 2), (3, 1, 3), (3, 6, 1), (6, 6, 2) -- 2 граф , (4, 4, 1), (4, 5, 1), (5, 4, 2), (5, 4, 1); with t as ( select *, n = row_number() over( order by 1/0 ) from @graph ) update t set gID = n from t; declare @rc int = 1; while @rc > 0 begin with t as ( select * from @graph ) update t set gID = t1.gID from t inner join t as t1 on t.child = t1.parent where t.gID > t1.gID ; set @rc = @@ROWCOUNT; with t as ( select * from @graph ) update t set gID = t1.gID from t inner join t as t1 on t1.child = t.parent where t.gID > t1.gID ; set @rc = @rc + @@ROWCOUNT; with t as ( select * from @graph ) update t set gID = t1.gID from t inner join t as t1 on t1.child = t.child where t.gID > t1.gID ; set @rc = @rc + @@ROWCOUNT; with t as ( select * from @graph ) update t set gID = t1.gID from t inner join t as t1 on t1.parent = t.parent where t.gID > t1.gID ; set @rc = @rc + @@ROWCOUNT; end; select * from @graph order by gID; select gID, max([weight]) from @graph group by gID |
||
28 июн 19, 19:59 [21917319] Ответить | Цитировать Сообщить модератору |
Сруль. Member Откуда: Сообщений: 121 |
Для начала в таблицу графа, я добавил номер графа. Разбираться, где заканчивается один граф и начинается второй, отдельная диссертация-не уму ни сердцу. --Подготовка данных Create table graph (parent bigint not NULL, child bigint not NULL, [weight] int not NULL,graph_id int) go insert into graph Values -- 1 граф (1, 1, 1,1), (1, 2, 1,1), (1, 3, 10,1), (2, 3, 2,1), (3, 1, 3,1), (3, 6, 1,1), (6, 6, 2,1) -- 2 граф insert into graph Values (4, 4, 1,2), (4, 5, 1,2), (5, 4, 2,2), (5, 4, 1,2) go select * from graph |
1 июл 19, 18:36 [21918447] Ответить | Цитировать Сообщить модератору |
Сруль. Member Откуда: Сообщений: 121 |
Второе действие, понадобяться вспомогательные таблицы, не временные, а вспомогательные. if OBJECT_ID('t_node_sequence') is not null drop table t_node_sequence go if OBJECT_ID('t_node_sequence') is null create table t_node_sequence (parent bigint not NULL, child bigint not NULL, graph_id int) go if OBJECT_ID('t_single_graph') is not null drop table t_single_graph go create table t_single_graph (parent bigint not NULL, child bigint not NULL, [weight] int not NULL,graph_id int) go |
1 июл 19, 18:39 [21918451] Ответить | Цитировать Сообщить модератору |
Сруль. Member Откуда: Сообщений: 121 |
Теперь две процедуры. Одна.create proc p_first_node(@graph_id int) as begin insert into t_node_sequence (parent,child,graph_id) select top 1 parent,child,graph_id from graph where [weight]=(select max([weight]) from graph where @graph_id=graph_id) and graph_id=@graph_id delete t from t_single_graph t,t_node_sequence t1 where t.parent=t1.parent and t.child=t1.child and t.graph_id=@graph_id return end |
1 июл 19, 18:42 [21918454] Ответить | Цитировать Сообщить модератору |
Сруль. Member Откуда: Сообщений: 121 |
Вторая.-------------------------------------------------------------------------------------------------- create proc p_next_node(@new_parent int,@graph_id int) as begin declare @parent int, @child int if not exists(select * from t_single_graph where @graph_id=graph_id and @new_parent=parent and parent<>child) return select top 1 @parent=parent, @child=child from t_single_graph where @new_parent=parent and @graph_id=graph_id and parent<>child insert into t_node_sequence (parent,child,graph_id) select @new_parent,@child,@graph_id delete t_single_graph where parent=@parent and @child=child set @new_parent=@child exec p_next_node @new_parent ,@graph_id return end |
1 июл 19, 18:43 [21918455] Ответить | Цитировать Сообщить модератору |
Сруль. Member Откуда: Сообщений: 121 |
Теперь скрипт для первого графа, хард-кодный параметр 1if OBJECT_ID('t_node_sequence') is not null drop table t_node_sequence go if OBJECT_ID('t_node_sequence') is null create table t_node_sequence (parent bigint not NULL, child bigint not NULL, graph_id int) go if OBJECT_ID('t_single_graph') is not null drop table t_single_graph go create table t_single_graph (parent bigint not NULL, child bigint not NULL, [weight] int not NULL,graph_id int) go --===================================================== insert into t_single_graph select * from graph where graph_id=1 --===================================================== declare @new_parent int exec p_first_node 1 select @new_parent=child from t_node_sequence --select @new_parent exec p_next_node @new_parent,1 insert into t_node_sequence --напоследок загоняем петли (parent,child,graph_id) select parent,child,graph_id from graph where graph_id=1 and parent=child select * from t_node_sequence order by parent,child |
1 июл 19, 18:45 [21918457] Ответить | Цитировать Сообщить модератору |
Сруль. Member Откуда: Сообщений: 121 |
Скрипт для второго графа, хард-кодный параметр 2if OBJECT_ID('t_node_sequence') is not null drop table t_node_sequence go if OBJECT_ID('t_node_sequence') is null create table t_node_sequence (parent bigint not NULL, child bigint not NULL, graph_id int) go if OBJECT_ID('t_single_graph') is not null drop table t_single_graph go create table t_single_graph (parent bigint not NULL, child bigint not NULL, [weight] int not NULL,graph_id int) go --===================================================== insert into t_single_graph select * from graph where graph_id=2 --===================================================== declare @new_parent int exec p_first_node 2 select @new_parent=child from t_node_sequence --select @new_parent exec p_next_node @new_parent,2 insert into t_node_sequence --напоследок загоняем петли (parent,child,graph_id) select parent,child,graph_id from graph where graph_id=2 and parent=child select * from t_node_sequence order by parent,child |
1 июл 19, 18:47 [21918458] Ответить | Цитировать Сообщить модератору |
Топик располагается на нескольких страницах: [1] 2 3 вперед Ctrl→ все |
Все форумы / Microsoft SQL Server | ![]() |