|
Разбить направленный граф на несколько деревьев
#39861733
Ссылка:
Ссылка на сообщение:
Ссылка с названием темы:
Ссылка на профиль пользователя:
|
|
|
|
Кстати мое решение данной задачи выглядит вот так
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
insert into tmp_link
with tPart (id , fQty) as (select 1, 1 from dual
union all
select 2, 1 from dual
union all
select 3, 1 from dual
union all
select 4, 3 from dual
union all
select 5, 1 from dual
union all
select 6, 2 from dual
union all
select 7, 1 from dual
union all
select 8, 2 from dual
union all
select 9, 1 from dual
union all
select 10, 1 from dual
),
tLink (idParent, idChild, fQty) as (select 1 , 4 , 1 from dual
union all
select 2 , 4 , 1 from dual
union all
select 3 , 4 , 1 from dual
union all
select 4 , 5 , 1 from dual
union all
select 4 , 6 , 2 from dual
union all
select 6 , 9 , 1 from dual
union all
select 6 , 10 , 1 from dual),
t (id, fqty, fqtyAll, sPath, bProcessed, idParent, idRoot, nlvl, fqtylink) as
(select idChild, fQty, fQty, '-'||tlink.idParent, 0, idParent, idParent, 1, fQty from tLink where idParent not in (select idChild from tLink)
union all
select tLink.idChild, least(t.fQty, tLink.fqty) , t.fQty, t.sPath||'-'||tLink.idParent, 0, tLink.idParent, t.idRoot, t.nlvl+1, tLink.fQty from tLink, t where t.id = tLink.idParent
)
select t.*, row_number() over(order by t.idRoot, t.nlvl, t.id) from t;
/
declare
nvRn number(15) := 0;
svPath varchar2(4000);
svSubPath varchar2(4000);
svPrevSubPath varchar2(4000);
i number;
fvQty number;
fvQtyAll number;
idv number;
idvParent number;
begin
loop
--выбираем первую по порядку не обработанную запись
select min(nrn)
into nvRn
from tmp_link
where id not in (select idParent from tmp_link where idParent is not null)
and bProcessed = 0
and nrn > nvRn;
exit when nvRn is null;
--dbms_application_info.set_action(nvRn);
select sPath, fQty, id, idParent, fQtyAll
into svPath, fvQty, idv, idvParent, fvQtyAll
from tmp_link where nrn = nvRn;
update tmp_link set bProcessed = 1 where nrn = nvRn;
--обновляем количество в не обработанных записях
--для каждого узла проверяем наличие ветвлений
i := 1;
svSubPath := svPath;
svPrevSubPath := '!!!';
loop
--if instr(svSubPath,'p') > 0 then --альтернативы есть только на укрупненных позициях
--обновляем свои альтернативы
update tmp_link t3
set fqtyAll = least(fqtyAll,fvQtyAll - fvQty), fqty = least(fqty, fvqtyAll - fvQty)
where t3.sPath like svSubPath||'%'
and t3.sPath not like svPrevSubPath||'%' --запрет на спуск тем же путем которым мы поднимаемся
and bProcessed = 0;
--обновляем чужие альтернативы
update tmp_link t3
set fqty = least(fqty, t3.fqtylink - fvQty)
where t3.idParent = idvParent
and t3.sPath != svSubPath
and t3.id = idv
and bProcessed = 0;
--удаляем лишнее
delete from tmp_link t3
where
(t3.idParent = idvParent or t3.sPath like svSubPath||'%')
and (t3.fqty = 0 or t3.fqtyAll = 0)
and bProcessed = 0;
--end if;
--сдвигаемся выше по дереву
exit when idvParent is null;
svPrevSubPath := svSubPath;
svSubPath := substr(svSubPath,1,instr(svSubPath,'-',-1)-1);
begin
select sPath, fQty, id, idParent, fQtyAll
into svPath, fvQty, idv, idvParent, fvQtyAll
from tmp_link where sPath = svSubPath and id = idvParent;
exception
when no_data_found then
exit;
end;
update tmp_link set bProcessed = 1 where sPath = svSubPath and id = idv;
end loop;
end loop;
end;
/
select idRoot, idParent, id, fqty from tmp_link;
Но во первых это не красиво :), а во вторых не очень быстро.
На тестовом примере с количеством связей порядка 43 тыс., мой код работает 15-20 минут (с учетом наличия правильных индексов на промежуточной таблице).
Конечно его можно оптимизировать обработав то что все эти сложности нужны только если есть ветвления, убрать delete из цикла и т.п., но когда писал на форму я очень надеялся что кто нибудь предложит какой-нибудь альтернативный подход. |
|
|
