Я работаю над структурой данных для алгоритма вырезания графика.Задача состоит в том, чтобы делать различные разрезы на кратчайших путях.Я сделал структуру данных, для которой я не уверен в свойствах.
Ввод - это ориентированный граф кратчайших путей, который является ограниченной решеткой, частично упорядоченным множеством с минимальным и максимальным элементом.
Определить следующий узел N (n) узла n как набор узлов b, для которых a предыдущий узел 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
Этот алгоритм можно повторно вызывать на новых решетках.Я беспокоюсь о:
- Есть ли гарантия для достижения одноузловой решетки?
- Есть ли мера количества итераций для достижения одноузловой решетки?Мне кажется, что граница - это диаметр входного графика.
Я ценю ссылку на любую подобную структуру данных.
Tnx
Справочная информация:
У меня была идеяиспользуйте Максимальный поток сетевой проблемы в материалах, над которыми я работал.Я думал о версии запрета вершин, где заданное количество вершин может быть удалено из сети, чтобы минимизировать максимальный поток.Сеть, над которой я работал, была очень регулярным плоским ориентированным графом (плоскость разделена на шестиугольники, каждая вершина соединена с 6 вершинами).Я хотел сократить (перехватить) только кратчайшие пути от source до sink.Для этого я использовал упрощение ориентированного графа, ребро (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.
Отображение полосы с начальной решетки на узел новой решетки.Узлы в новой решетке связаны, если они разделяют волну.Направление края от полосы, которая разделяет последнюю волну, к полосе, которая разделяет первую волну.
Поскольку отображение создает новую решетку с такими же свойствами, процедуру можно повторять до тех пор, пока не будет решетки только с одним узлом.Это можно показать, потому что диаметр решетки меньше, по крайней мере, на 1 с каждой итерацией.Это потому, что минимальные узлы M и N(M) находятся в одной полосе, и это уменьшает диаметр решетки.
Теперь выполнение или поиск разрезов является рекурсивной задачей, начните с решетки один перед последним с толькоодин узел, и сделайте разрез на одну целую волну или на соседние волны лестничным способом.Для узлов в разрезе возьмите подрешетку, которая отображается в ней, и сделайте разрез на этой подрешетке.То же самое делается до достижения начальной решетки.
Эта структура является своего рода при сжатии решетки.Я думаю, что это может быть использовано для поиска динамических разрезов решетки.
В моем случае я не использую его, так как некоторые другие ограничения проекта.Я решил начальную задачу очень просто с помощью всего лишь нескольких строк кода, но я не знал, что это можно сделать раньше: -)