В настоящее время я реализую динамический граф DAG в C ++ — он будет отображаться пользователю через пользовательский интерфейс, и вставка / удаление узлов / ребер будут обычными операциями.
Размер графиков может варьироваться от очень маленького до большого — я стремлюсь поддерживать миллионы узлов.
Таким образом, я ищу оптимальную структуру данных, которая не будет занимать слишком много места в памяти, но также и для способа быстрой вставки / удаления с быстрой многопоточной итерацией по топологически отсортированным узлам (таким образом, несколько узлов может выполняться параллельно).
Я не проводил никакого профилирования, чтобы посмотреть, удастся ли наивному подходу пересчитывать топологический вид полного графа каждый раз, когда выполняется модификация, сократить его, но ради обучения я подумал, что лучше найти «умнее». » путь.
Я понятия не имею, как подойти к многопоточной итерации графа, но для начала я наткнулся на некоторые статьи, связанные с этапом итеративной / динамической топологической сортировки, и проблема в том, что они слишком умны для меня, чтобы понять. Это выходит на теоретическую / математическую сторону и не содержит конкретных примеров реализации, которые могли бы помочь мне понять, что происходит.
Вот пример такой бумаги: Маркировочный подход к обнаружению добавочного цикла.
Поскольку не хватает документов, таких как «Итеративная / динамическая топологическая сортировка для чайников», есть ли у кого-нибудь подсказки по этому вопросу?
Алгоритм динамического toposort (не проверено).
Начните с топологически отсортированной последовательности вершин.
Сам алгоритм не обнаруживает циклы, но вы можете ограничить поиск циклов подмножеством вершин, которые были перемещены.
Действительно есть работа по динамическому топосорту.
Pearce & Келли http://homepages.ecs.vuw.ac.nz/~djp/dts.html есть алгоритм, который, как они утверждают, прост и практически эффективен. Они также предоставляют реализацию C ++. В качестве введения они обсуждают еще более простые варианты.
Вот некоторые из более поздних работ по этой проблеме, в хронологическом порядке. Более поздние методы имеют тенденцию быть более сложными, чем более ранние. Даже если нет, более поздние статьи могут предполагать, что вы уже прочитали предыдущие. Вы, очевидно, начали с последней статьи в этом списке, которая могла прыгнуть в глубокий конец.