Как я гарантирую, что DAG остается нециклическим после вставки узла?
У вас есть две основные проблемы здесь.
Во-первых, когда вы объявляете ваш массив как char *cmd[index];, размер массива не привязан к текущему значению index при изменении index. Он устанавливает размер на текущее значение , равное index, равное 0. Создание массива размера 0 вызывает неопределенное поведение . Вам нужно установить фиксированный размер для массива, который будет достаточно большим для ваших нужд.
char *cmd[MAX_LIMIT];
Другая проблема - ваш выбор разделителей. Функция fgets считывает строку текста , включая новую строку в конце ввода . Поэтому любой параметр, который будет считан последним, будет иметь \n в конце. Чтобы это исправить, добавьте \n в список разделителей.
char delim[] =" \n";
3 ответа
Вы могли также сохранить обратные каналы и просто проверить, что узел конечной остановки добавляемого края не появляется ни в одном из родительских узлов узла источника. Это было бы быстрее, чем выполнение полного обнаружения цикла. По существу это было бы алгоритмом поиска кратчайшего пути для обратных каналов, которые для DAG должны быть линейным режимом.
Как @Markus говорит, тем не менее, если Вы не создаете ссылки и к и от нового узла до существующих узлов, Вы не должны мочь создать цикл путем представления нового узла графику.
Когда эта структура обновляется путем добавления новой вершины и затем нового края оттуда к другим вершинам
Если все новые края будут от новой вершины, то Вы никогда не будете создавать циклы.
Если Вы также собираетесь быть добавляющими краями к новой вершине от более старых узлов, Ваши опции зависят от ожидаемой формы графика. Они все сводятся к вариациям на частичное упорядочивание, но существуют взломы, которые дают лучшую производительность для деревьев, лесов, ромбовидных сеток, и т.д. Что Вы знаете об ожидаемой полной форме графика?
То, что можно сделать, должно сохранить узлы заказанными в топологическом упорядочивании (поиск "топологического вида"). Когда Вы добавляете дугу от низшего порядка до узла высшего порядка, Вы знаете, что никакой цикл не был создан. В обратном случае Вы должны инкрементно обновить свое топологическое упорядочивание и в то же время обнаружение выполняемого цикла.