description.txt

                Разработка абстрактной модели графа зависимости, её визуализация и применение.


1. Предисловие Приветствие
2. Принципы работы
3. Правила подключения
4. События графа
5. Визуализация
6. Области применения


1. Предисловие

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

    Для ясности расскажу немного о истоках. О том, что же такое граф мы можем узнать из математической теории графов, это раздел дисркетной математики основным объектом изучения которой и являются графы. Граф - это совокупность вершин соединенных ребрами. Графы могут быть направленными, ненаправленными, смешанными и изоморфными. Что касается терминологии сразу хочу сказать что у теории графов она еще не устоялась, и в разных публикациях под одними и теми же терминами могут пониматься разные вещи. Вершины мы будем называть "нодами" (нода), ребра - "связями" (связь). В нашем случае мы рассмотрим ациклический направленный граф (DAG). Это такой граф в котором отсутствуют направленные циклы, то есть пути, начинающиеся и кончающиеся в одной и той же вершине.




                                                Принципы.

1) У каждой ноды есть входные и выходные порты, и есть "мозг" - функция "compute", которая запрашивает данные у входных портов, производит какие-то вычисления а затем записывает результат в выходные порты.

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

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

3) У каждого порта должно быть бинарное свойство dirty. И служебные списки кто на кого влияет. Для установления этих зависимостей должна вызываться функция pinAffects.

    Например если это выходной порт ноды "А", то на него будет влиять какой-то входной порт этой ноды. А в момент соединения с нодой "Б" аутпут "А" станет влиять на какой-то инпут ноды "Б", и т.д. реализуя связи между входными и выходными портами нод. На основе таких связей будет работать механизм dirty propogation для оптимального пересчета графа.

4) Выходные порты выдают информацию только если у них спросить (getData). (lazy evaluation)

5) Данные запрещается читать\писать на прямую внутри функции compute, для этого существуют специальные методы getData, setData. Хотя например в методе отображения графа plot мы обращаемся к данным на прямую, чтобы распечатать их значение в данный момент, не вызывая при этом getData и не задействуя механизм dirty_propagation.

6) Compute методы вызываются единожды для каждой ноды по глубине начиная с конца графа, учитывая dirty флаги. Информацию о том в каком порядке вызывать комьют для блока должен знать граф, и её можно получить скормив мутоду ноду. Нужно учесть ситуацию ненаправленных циклов.

7) Ноды одного уровня не зависят друг от друга и вычисляются параллельно или последовательно на выбор. Когда все ноды одного уровня просчитаны, начинают вычисляться ноды следующего уровня, и т.д. до конца.

8) Порты будут разделяться по типам данных с которыми работают. Нельзя соединить порты несовместимых типов данных.


                                                Правила.

- Подключены могут быть только порты разного типа (входной и выходной) с совместимыми типами данных.
- Входной порт может принимать только одну связь.
- Выходной порт может связываться со многими.
- Входной порт не может принимать значение с выходного порта собственной ноды. (Циклических нод нет)
- Когда пишем "особые"" ноды, у которых пины могут быть добавлены в рантайме или нужно хранить что-то уникальное, нужно описать как сохранять и загружать такие ноды. Например массивы или sequence нода, или коммент нода. (см. исходники)


                                            Описание событий.

1) Выходной порт ноды "А" соеденился с входным портом ноды "Б".

    В этот момент заполнятся списки влияния.
    Заполняются списки графа.
    Создается связь. (графически - линия соединяющая порты)
    Данные из выходного порта ноды "А" записались во входной порт ноды "Б".
    Расставляются dirty флаги.

2) Связь между портами разорвалась.

    Редактируются списки влияния.
    Удаляется связь.

3) Изменилось значения инпут порта ноды.

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

4) Порт запраштвает данные.
    
    Проверяется dirty флаг, если true то у графа запрошивается порядок пересчета нод, и они пересчитываются. Если false, берутся данные с последнего просчета.