Итеративная / динамическая топологическая сортировка для чайников

В настоящее время я реализую динамический граф DAG в C ++ — он будет отображаться пользователю через пользовательский интерфейс, и вставка / удаление узлов / ребер будут обычными операциями.

Размер графиков может варьироваться от очень маленького до большого — я стремлюсь поддерживать миллионы узлов.

Таким образом, я ищу оптимальную структуру данных, которая не будет занимать слишком много места в памяти, но также и для способа быстрой вставки / удаления с быстрой многопоточной итерацией по топологически отсортированным узлам (таким образом, несколько узлов может выполняться параллельно).

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

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

Вот пример такой бумаги: Маркировочный подход к обнаружению добавочного цикла.

Поскольку не хватает документов, таких как «Итеративная / динамическая топологическая сортировка для чайников», есть ли у кого-нибудь подсказки по этому вопросу?

3

Решение

Алгоритм динамического toposort (не проверено).

Начните с топологически отсортированной последовательности вершин.

  1. Если вершина без ребер добавлена, вставьте ее в любое место последовательности.
  2. Если ребро или вершина удалены, ничего не делайте.
  3. Если добавлен передний край (от нижнего к верхнему), ничего не делать.
  4. Если добавлен новый обратный край A → B, переместите B сразу после A. Отметьте исходящие края B как новые. Повторите пункты 3 и 4 по мере необходимости. (Если можно переместить несколько вершин, начните с самой низкой сортировки; если у перемещаемой вершины есть несколько новых входящих ребер, выберите одну из вершин с самой высокой сортировкой). Если в этом процессе вы встречаете одну и ту же вершину дважды, сообщите о цикле.

Сам алгоритм не обнаруживает циклы, но вы можете ограничить поиск циклов подмножеством вершин, которые были перемещены.

1

Другие решения

Действительно есть работа по динамическому топосорту.

Pearce & Келли http://homepages.ecs.vuw.ac.nz/~djp/dts.html есть алгоритм, который, как они утверждают, прост и практически эффективен. Они также предоставляют реализацию C ++. В качестве введения они обсуждают еще более простые варианты.

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

1

По вопросам рекламы [email protected]