Я работаю над структурой данных для алгоритма вырезания графа. Проблема состоит в том, чтобы делать разные сокращения на кратчайших дорожках. Я создал структуру данных, для которых я не уверен в свойствах.
Ввод представляет собой ориентированный график кратчайших путей, который представляет собой ограниченную решетку, частично упорядоченное множество с минимальным и максимальным элементами.
Определите следующий node N (n) of node n как набор узлов b, для которых a < b, и нет c с < c < б. Аналогично определите предыдущий node P (n). Расширение определений на множествах, объединение N (S) N (n) для n в S, аналогичное для P (S).
Легко сделать разные сокращения в списке множества узлов L, N (L), N (N (L)),... где для каждой соседней пары множеств A, N (A) = B выполнено что нет разделов:
A = A_1 union A_2
B = B_1 union B_2
with B_i = N(A_i), A_i = P(B_i) for i=1,2.
С помощью этого свойства создайте новую решетку с отображением:
В простом алгоритме решетчато-решетчатого отображения:
A = {minimum node}
new_node = [A]
1:
while A, N(A) don't have partitions
append N(A) to new_node
A = N(A)
for each partition $B_i$
last_new_node = new_node
create new_node = [B_i]
create edge last_new_node to new_node
go to 1
At the end fix maximum node in new lattice if needed
Этот алгоритм можно многократно вызывать на новых решетках. Я беспокоюсь о:
Я ценю ссылку на любую подобную структуру данных.
Тпх
Фон:
У меня возникла идея использовать проблему ограничения максимальной пропускной способности сети в работе, над которой я работал. Я думал о версии перехвата вершин, где заданное количество вершин можно удалить из сети, чтобы минимизировать максимальный поток. Сеть, над которой я работал, была очень регулярным планарным ориентированным графом (плоскость, разделенная на шестиугольники, каждая вершина связана с 6 вершинами). Я хотел разрезать (запретить) только кратчайшие пути от source до sink. Чтобы сделать это, я использовал упрощение ориентированного графа, edge (a,b) находится в упрощенном графике, если он находится на кратчайшем пути от a до sink. Если вес кромки положителен, то упрощенный ориентированный граф является решеткой. Это то, что я назвал "ориентированным графом кратчайших путей".
Я хотел иметь разрезы вершин, которые хороши (параллель, распространение,...), что проще в (очень структурированной) решетке.
Родные срезы - это "волны", например. один хороший разрез C также производит N(C), что приятно. Из-за этого я попытался упростить решетку с описанными выше операциями. Я попытался описать 2 подмножества вершин, которые интересны для разрезов и используются в сопоставлении:
- волновой параллельный набор узлов. Если C - одна волна, то N(C) - другая.
- полоса - серия волн без пересечения с другими полосами. C, N(C), N(N(C)).
B1--C1--D1 ...
/ \ / \ /
A X X
\ / \ / \
B2--C2--D2
Waves: {A}, {B1,B2}, {C1,C2}, {D1,D2}
Stripe is made of these 4 waves.
Отображение карт с первой решетки на node новой решетки. Узлы в новой решетке связаны, если они разделяют волну. Направление ребра связано с полосой, которая разделяет последнюю волну на полосу, разделяющую первую волну.
Поскольку отображение создает новую решетку с одинаковыми свойствами, процедуру можно повторить до тех пор, пока не будет решетка с только одним node. Это можно показать, потому что диаметр решетки меньше, по крайней мере для 1, с каждой итерацией. Это связано с тем, что минимальные node M и N(M) находятся в одной полосе и уменьшают диаметр решетки.
Теперь выполнение или поиск разрезов - это рекурсивная задача, начинайте с решетки до последнего с помощью только одного node и делайте разрез на одну целую волну или на соседние волны по лестнице. Для узлов в разрезанной подрешетке, отображаемой в ней, и разрезаем эту подрешетку. То же самое делается до достижения начальной решетки.
Эта структура какая-то на сжатии решетки. Я думаю, что он может быть использован для поиска динамических разрезов.
В моем случае я не использую его с некоторыми другими ограничениями проекта. Я решил начальную проблему очень просто с несколькими строками кода, но я не понимал, что это можно сделать так: -)
Есть ли гарантия достижения решетки 1 node?
Если я правильно понимаю ваш псевдокод, нет: он несет линейный порядок n- node в линейный порядок n-node.
Я бы описал ваш код как принятие частичного порядка и находил последовательный параллельный порядок порядка, в который он имеет достаточно "верное" вложение.
Если вам просто интересно найти максимальные потоки/мин в плоских графах, там O (n log n) алгоритм для этого.