Я пытаюсь найти быстрый способ проверить относительное упорядочение двух узлов ориентированного ациклического графа.Узел может предшествовать, идти после или быть параллельным другому узлу.Вот пример:
B, A->C, A->D, B->F, C->E, D->H, E->G, E->H, F->I, G->I, H->I, H->J, I->K, J->K">
Узел H идет после A, C, D и E, но параллельно B, F и G,и предшествует I, J и K.
Я бы хотел найти способ проведения такого типа сравнения узлов с минимальным обходом графа путем создания индекса (или нескольких индексов), пока я создаюграф.В идеале, каждый раз, когда я добавляю узел или ребро, мне нужно только устанавливать его индексы, а не обновлять другие значения вокруг него.Я не уверен, возможно ли это, но такое ощущение, что это может быть?
Мои первоначальные подходы не были такими удачными.Вот иллюстрация 4-х этапов моего первоначального мыслительного процесса создания другого графика:
B | (A=1;B=128). 2: A->C, C->B | (A=1;B;128;C=64). 3: A->C, A->D, C->B, D->B | (A=1;B=128;C=64;D=64). 4: A->C, A->D, C->E, D->B, E->B | (A=1;B=128;C=64;D=64,2;E=96).">
- Я назначаю высокое значение(128) в качестве индекса для конечной точки, B.
- Разбив ребро пополам, я назначаю половинное значение 64 для C. Сравнение между двумя точками остается в силе.
- Я снова соединяю А и В параллельно.Это также половина, 64, и сравнения все еще действительны: D равно (параллельно) C. C. 1024 *
- Я разделил ссылку CB, давая новому узлу E значение 96. Теперь все становится странным.Сравнение больше не работает, так как E (96) больше, чем D (64), но должно быть параллельным.Я пытаюсь вернуться к шагу 3 и добавить второе значение 2 к D, чтобы указать ветку, на которой он находится.Теперь, если я сравниваю D с E, я сначала проверяю, равно ли значение ветви (со значением ветви по умолчанию 1).
После этого метод ломается.Какое значение ветви я даю B?Что произойдет, если я добавлю ребро от D до E?Возможно, мне нужно продолжать добавлять множество значений ветвления, но кажется, что этот подход может привести к тому, что каждый индекс будет расти до размера самого графика.Я хотел бы сохранить эффективность памяти, если это возможно, хотя я мог бы сделать некоторые временные / пространственные компромиссы и сделать некоторый локализованный обход графа, если он того стоит.
Кто-нибудь знает решение этой проблемы или некоторыеусловия поиска, которые я мог бы использовать, чтобы изучить дальше?Спасибо!
РЕДАКТИРОВАТЬ: похоже, топологический порядок это то, что я ищу.Хотя он не скажет мне, параллельны ли два узла, на данный момент этого может быть достаточно.Мой новый вопрос: как я могу эффективно обновить данные топологического упорядочения при добавлении новых узлов и ребер?