Функциональные графики

Question

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

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

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

Поэтому я вместо этого попытался сохранить родительские узлы внутри каждого узла, то есть узлы знают, кто их родители.

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

Итак, чтобы обновить одно значение узла, я должен обновить каждый узел на графике.

Другая идея, которая у меня была, заключалась в том, чтобы хранить родительские узлы в каждом узле, просто сохраняя «пути» к родительским узлам в каждом узле. Таким образом, мне не нужно обновлять дочерние элементы родителя, поскольку «путь» к родительскому объекту не изменился (хотя сам узел имеет).

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

Answer 1

Итак, чтобы обновить значение узла, я должен обновить каждый узел на всем графике.

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

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

Я работаю над графическим проектом db в течение некоторого времени, который еще не выпущен. Однако я опубликовал некоторый код. Я думаю, this mutable graph implementation может пригодиться вам как источник идей.