Упрощение графика/решетки

Я работаю над структурой данных для алгоритма вырезания графа. Проблема состоит в том, чтобы делать разные сокращения на кратчайших дорожках. Я создал структуру данных, для которых я не уверен в свойствах.

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

Определите следующий 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.

С помощью этого свойства создайте новую решетку с отображением:

  • подрешетка к одному node
  • если найден верхний раздел, чем создание ребер (номер сети).

В простом алгоритме решетчато-решетчатого отображения:

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

Этот алгоритм можно многократно вызывать на новых решетках. Я беспокоюсь о:

  • Есть ли возможность получить решетку node?
  • Существует ли какая-либо мера количества итераций для достижения решетки? node? Мне кажется, что граница - это диаметр входного графика.

Я ценю ссылку на любую подобную структуру данных.

Тпх

Фон:

У меня возникла идея использовать проблему ограничения максимальной пропускной способности сети в работе, над которой я работал. Я думал о версии перехвата вершин, где заданное количество вершин можно удалить из сети, чтобы минимизировать максимальный поток. Сеть, над которой я работал, была очень регулярным планарным ориентированным графом (плоскость, разделенная на шестиугольники, каждая вершина связана с 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

Есть ли гарантия достижения решетки 1 node?

Если я правильно понимаю ваш псевдокод, нет: он несет линейный порядок n- node в линейный порядок n-node.

Я бы описал ваш код как принятие частичного порядка и находил последовательный параллельный порядок порядка, в который он имеет достаточно "верное" вложение.

Если вам просто интересно найти максимальные потоки/мин в плоских графах, там O (n log n) алгоритм для этого.