Как я могу гарантировать, что DAG останется ациклическим после вставки узла?

Question

У меня есть DAG, хранящая отношения между определенными объектами в моем приложении. Когда эта структура обновляется путем добавления новой вершины ниже существующей (т.е. неявно создавая новое ребро в новую вершину), а затем (в любое более позднее время) нового ребра оттуда в другие вершины, Я хочу убедиться, что график остается DAG, т.е. е. что мой код не создает циклы.

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

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

Answer 1

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

Как говорит @Markus, однако, если вы не создаете ссылки как на , так и с нового узла на существующие узлы, вы не сможете создать цикл введя новый узел в граф.

Answer 2

Когда эта структура обновляется путем добавления новой вершины, а затем нового ребра оттуда к другим вершинам

Если все новые ребра из новой вершины, вы никогда не будете создавать циклы.

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

Answer 3

В этой статье имеется онлайн-алгоритм для поддержания топологического порядка (стр. 4).

Answer 4

Что вы можете сделать, это упорядочить узлы в топологическом порядке (ищите «топологическая сортировка»). Когда вы добавляете дугу из узла более низкого порядка в узел более высокого порядка, вы знаете, что цикл не был создан. В обратном случае вам нужно постепенно обновлять свой топологический порядок и в то же время определять цикл выполнения.