Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3   вперед  Ctrl      все
 Отсортировать (в кавычках) взвешенный граф. Возможно ли это на TSQL?  [new]
uaggster
Member

Откуда:
Сообщений: 619
Коллеги, приветствую!
Есть задача, к которой даже не знаю, с какой стороны подступиться, весь мозг сломал.
Имеется таблица, содержащая набор произвольных графов.
Графы в т.ч. - содержат петли.
Необходимо "размотать" граф, и "вытащить" его за самый тяжелый узел.

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)

На выходе нужно получить:
parent child
1 1
1 2
1 3
1 6
5 5
5 4

Граф представлен как совокупность нод: узел -> смежный узел -> вес узла.
Преобразовать его нужно, "Навесив" все достижимые узлы на узел, имеющий максимальный вес в каком либо из состояний.
Т.е., в первом графе максимальный вес имеет узел 1, см. (1, 3, 10), это вес 10.
Поэтому он считается "главным", а остальные достижимые узлы, в т.ч. - он сам - его дочерними.
Обратите внимание, что сам граф - имеет петли, а узел №6 - непосредственно из узла №1 - недостижим (но достижим через другие узлы).
Второй граф имеет самый "массивный" узел (5, 4, 2), 5 имеет вес 2, остальные состояния - только вес 1, поэтому он и считается главным.

Это не совсем взвешенный граф, но так получилось.
Собственно, меня устроит любое решение, не обязательно "Одним запросом".

В таблице - множество графов.
Но если не получится преобразовать ее целиком, меня устроит решение, когда на вход подается нода, например parent = 1, а на выходе возвращается такая "матрица смежности" (это не матрица смежности, я понимаю, но тем не менее).
... я тогда курсором переберу все, объем небольшой, пара миллионов вхождений всего.

Может ли облегчить задачу тот факт, что нод в любом из графов - заведомо не более 100?
Если кандидатов на самую массивную ноду в графе - несколько, то нужно выбрать одну и только одну главную ноду произвольно.
28 июн 19, 09:40    [21916755]     Ответить | Цитировать Сообщить модератору
 Re: Отсортировать (в кавычках) взвешенный граф. Возможно ли это на TSQL?  [new]
Ролг Хупин
Member

Откуда: Чебаркуль
Сообщений: 2726
В тему

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]     Ответить | Цитировать Сообщить модератору
 Re: Отсортировать (в кавычках) взвешенный граф. Возможно ли это на TSQL?  [new]
uaggster
Member

Откуда:
Сообщений: 619
Блин, у меня 2016SP2.
Сейчас поставлю триал 2017. Хотя нужно вкуривать новую для себя концепцию.
Чисто реляционного решения никто не знает?

Фактически, как я понимаю, нужна функция, которая по номеру ноды вернет список всех достижимых из нее узлов, с весами.
Всё осложняется произвольными петлями в графе.
28 июн 19, 10:33    [21916811]     Ответить | Цитировать Сообщить модератору
 Re: Отсортировать (в кавычках) взвешенный граф. Возможно ли это на TSQL?  [new]
Ролг Хупин
Member

Откуда: Чебаркуль
Сообщений: 2726
uaggster
Блин, у меня 2016SP2.
Сейчас поставлю триал 2017. Хотя нужно вкуривать новую для себя концепцию.
Чисто реляционного решения никто не знает?

Фактически, как я понимаю, нужна функция, которая по номеру ноды вернет список всех достижимых из нее узлов, с весами.
Всё осложняется произвольными петлями в графе.


Решение есть, я просто дал ссылку на тип данных,который уже сделан майкрософтом, может быть его использование поможет.
Вы же версию сервера не указали.
Кроме того, есть тип HierarchyID, для работы с иерархиями, это так, к слову.
28 июн 19, 10:41    [21916819]     Ответить | Цитировать Сообщить модератору
 Re: Отсортировать (в кавычках) взвешенный граф. Возможно ли это на TSQL?  [new]
uaggster
Member

Откуда:
Сообщений: 619
Ролг Хупин, проблема в том, что там как раз не иерархия.
Там большая часть - петли, но иногда осложненные перемычками.
28 июн 19, 10:54    [21916835]     Ответить | Цитировать Сообщить модератору
 Re: Отсортировать (в кавычках) взвешенный граф. Возможно ли это на TSQL?  [new]
aleks222
Member

Откуда:
Сообщений: 694
uaggster
Блин, у меня 2016SP2.
Сейчас поставлю триал 2017. Хотя нужно вкуривать новую для себя концепцию.
Чисто реляционного решения никто не знает?

Фактически, как я понимаю, нужна функция, которая по номеру ноды вернет список всех достижимых из нее узлов, с весами.
Всё осложняется произвольными петлями в графе.


1. Добавь в табличку поле: ID_graph - идентификатор графа
2. Заполни.
3. Все станет тривиальным.
28 июн 19, 12:58    [21916967]     Ответить | Цитировать Сообщить модератору
 Re: Отсортировать (в кавычках) взвешенный граф. Возможно ли это на TSQL?  [new]
uaggster
Member

Откуда:
Сообщений: 619
aleks222, А где его взять, идентификатор то?
Для того, чтобы сгенерировать идентификатор, нужно определить все ноды, которые в него входят.
Ну, т.е. определить сам граф, в куче других.
Вот эти ноды - один граф, вот эти - другой.
А как это сделать?
28 июн 19, 13:14    [21916982]     Ответить | Цитировать Сообщить модератору
 Re: Отсортировать (в кавычках) взвешенный граф. Возможно ли это на TSQL?  [new]
Konst_One
Member

Откуда:
Сообщений: 11313
-- 2 граф
(4, 4, 1), (4, 5, 1), (5, 4, 2), (5, 4, 1)


что-то странный граф. если верхушка от 4, то почему там 5, 4 варианты попали?
28 июн 19, 13:16    [21916986]     Ответить | Цитировать Сообщить модератору
 Re: Отсортировать (в кавычках) взвешенный граф. Возможно ли это на TSQL?  [new]
uaggster
Member

Откуда:
Сообщений: 619
Konst_One
-- 2 граф
(4, 4, 1), (4, 5, 1), (5, 4, 2), (5, 4, 1)


что-то странный граф. если верхушка от 4, то почему там 5, 4 варианты попали?

Это не дерево. А граф общего вида. Нет у него верхушки.
А ноды - перечислены, как перечислены.
(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]     Ответить | Цитировать Сообщить модератору
 Re: Отсортировать (в кавычках) взвешенный граф. Возможно ли это на TSQL?  [new]
Konst_One
Member

Откуда:
Сообщений: 11313
graph (parent bigint not NULL, child bigint not NULL

как так? у вас сполошное закольцовывание, это замкнутый граф. и другие графы ваши сложно определяемы, так как нет ограничений на "раскрутку", это задача без лимитов и ограничений не решаема.

4,4
4,5
5,4
5,5
28 июн 19, 13:36    [21917020]     Ответить | Цитировать Сообщить модератору
 Re: Отсортировать (в кавычках) взвешенный граф. Возможно ли это на TSQL?  [new]
Владислав Колосов
Member

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

имо эта задача решается рекурсивными алгоритмами и не с помощью T-SQL.
28 июн 19, 13:38    [21917022]     Ответить | Цитировать Сообщить модератору
 Re: Отсортировать (в кавычках) взвешенный граф. Возможно ли это на TSQL?  [new]
uaggster
Member

Откуда:
Сообщений: 619
Konst_One
graph (parent bigint not NULL, child bigint not NULL

как так? у вас сполошное закольцовывание, это замкнутый граф. и другие графы ваши сложно определяемы, так как нет ограничений на "раскрутку", это задача без лимитов и ограничений не решаема.

4,4
4,5
5,4
5,5

Ну вот такие графы :-(

Ограничение есть. В каждом конкретном графе - заведомо меньше 100 нод.
Точнее даже не нод, а записей вида (4, 4, 1), описывающих связь.
28 июн 19, 14:04    [21917055]     Ответить | Цитировать Сообщить модератору
 Re: Отсортировать (в кавычках) взвешенный граф. Возможно ли это на TSQL?  [new]
iap
Member

Откуда: Москва
Сообщений: 46776
Чтобы не зациклиться, надо организовать поле в рекурсивном CTE, в котором накапливать список пройденных узлов,
чтобы не проходить узел дважды.
28 июн 19, 15:10    [21917128]     Ответить | Цитировать Сообщить модератору
 Re: Отсортировать (в кавычках) взвешенный граф. Возможно ли это на TSQL?  [new]
a_voronin
Member

Откуда: Москва
Сообщений: 3926
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]     Ответить | Цитировать Сообщить модератору
 Re: Отсортировать (в кавычках) взвешенный граф. Возможно ли это на TSQL?  [new]
court
Member

Откуда:
Сообщений: 1736
a_voronin
Функция NTile(2) порежет ваш список примерно пополам без всяких долгих гемороев.
ему не нужно "пополам"
Нужно найти несвязанные подграфы
28 июн 19, 15:47    [21917158]     Ответить | Цитировать Сообщить модератору
 Re: Отсортировать (в кавычках) взвешенный граф. Возможно ли это на TSQL?  [new]
uaggster
Member

Откуда:
Сообщений: 619
Вот что мне нужно, как я понимаю: 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]     Ответить | Цитировать Сообщить модератору
 Re: Отсортировать (в кавычках) взвешенный граф. Возможно ли это на TSQL?  [new]
court
Member

Откуда:
Сообщений: 1736
uaggster
Вот что мне нужно, как я понимаю: SHORTEST_PATH
https://docs.microsoft.com/ru-ru/sql/relational-databases/graphs/sql-graph-shortest-path?view=sqlallproducts-allversions&viewFallbackFrom=sql-server-2017
Но оно, сцуко, доступно только с 2019.
Картинка с другого сайта.
автор
Функция SHORTEST_PATH позволяет найти:
Кратчайший путь между двумя заданные узлы/сущности
Единый источник кратчайшего пути.
Кратчайшего пути из нескольких узлов источника для нескольких целевых узлов.

и что это тебе даст ?
вот тебе возможные пути в графе, - что дальше ? :)
Как из этого, "по-простому" определить, что у тебя 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


start_nodenodepath
12/1/2/
13/1/3/
16/1/3/6/
13/1/2/3/
16/1/2/3/6/
21/2/3/1/
26/2/3/6/
23/2/3/
31/3/1/
36/3/6/
32/3/1/2/
45/4/5/
54/5/4/
54/5/4/
28 июн 19, 17:16    [21917230]     Ответить | Цитировать Сообщить модератору
 Re: Отсортировать (в кавычках) взвешенный граф. Возможно ли это на TSQL?  [new]
invm
Member

Откуда: Москва
Сообщений: 8661
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]     Ответить | Цитировать Сообщить модератору
 Re: Отсортировать (в кавычках) взвешенный граф. Возможно ли это на TSQL?  [new]
aleks222
Member

Откуда:
Сообщений: 694
uaggster
aleks222, А где его взять, идентификатор то?
Для того, чтобы сгенерировать идентификатор, нужно определить все ноды, которые в него входят.
Ну, т.е. определить сам граф, в куче других.
Вот эти ноды - один граф, вот эти - другой.
А как это сделать?


Элементарно, Ватсон.
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]     Ответить | Цитировать Сообщить модератору
 Re: Отсортировать (в кавычках) взвешенный граф. Возможно ли это на TSQL?  [new]
Сруль.
Member

Откуда:
Сообщений: 107
Для начала в таблицу графа, я добавил номер графа.
Разбираться, где заканчивается один граф и начинается второй,
отдельная диссертация-не уму ни сердцу.


--Подготовка данных
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]     Ответить | Цитировать Сообщить модератору
 Re: Отсортировать (в кавычках) взвешенный граф. Возможно ли это на TSQL?  [new]
Сруль.
Member

Откуда:
Сообщений: 107
Второе действие, понадобяться вспомогательные таблицы, не временные,
а вспомогательные.
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]     Ответить | Цитировать Сообщить модератору
 Re: Отсортировать (в кавычках) взвешенный граф. Возможно ли это на TSQL?  [new]
Сруль.
Member

Откуда:
Сообщений: 107
Теперь две процедуры. Одна.
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]     Ответить | Цитировать Сообщить модератору
 Re: Отсортировать (в кавычках) взвешенный граф. Возможно ли это на TSQL?  [new]
Сруль.
Member

Откуда:
Сообщений: 107
Вторая.
--------------------------------------------------------------------------------------------------
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]     Ответить | Цитировать Сообщить модератору
 Re: Отсортировать (в кавычках) взвешенный граф. Возможно ли это на TSQL?  [new]
Сруль.
Member

Откуда:
Сообщений: 107
Теперь скрипт для первого графа, хард-кодный параметр 1

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
--=====================================================
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]     Ответить | Цитировать Сообщить модератору
 Re: Отсортировать (в кавычках) взвешенный граф. Возможно ли это на TSQL?  [new]
Сруль.
Member

Откуда:
Сообщений: 107
Скрипт для второго графа, хард-кодный параметр 2

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
--=====================================================
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 Ответить