Стиль прохождения продолжения (CPS) при построении графа

Question

Я работаю над библиотекой для поверхностей подразделений.Чтобы представить топологию сетки, я использую некую структуру данных планки с расщепленными вершинами (см. Диаграмму слева).

Во время построенияСетка, которую также можно рассматривать как график, она создает узлы, которые должны указывать на другие, которые еще не существуют (см. диаграмму справа - пунктирная стрелка представляет будущие ссылки).Классическое решение состоит в том, чтобы создать узел с пустым указателем, а затем обновить его при создании другого.Поскольку я работаю над Haskell :) и не хочу переходить к темной стороне кода (нечистота), мне интересно, возможно ли построить сетку (граф) без обновления данных.Я полагаю, что CPS (Стиль продолжения прохождения) мог бы справиться с этой задачей, но я не могу найти способ.

Это просто сон?*

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

data Mesh = Edge Vertex Mesh Mesh Vertex | Ground

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

Я ошибаюсь?Если нет, как это сделать?

Answer 1

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

Предположим, вы можете идентифицировать каждый узел по некоторому уникальному идентификатору (строка, целое число или что-то еще).Предположим также, что когда вы создаете узел, вы уже знаете идентификаторы всех узлов, на которые он указывает, независимо от того, созданы они или нет.Затем вы можете использовать эту технику.

Вы вводите nodes :: Data.Map NodeID Node через функции создания вашего графа (используйте монаду состояний для дополнительного удобства).Когда вы создаете узел, вы добавляете его на карту.Когда вы создаете ребро, которое должно указывать на узел с именем x, вы используете fromMaybe $ lookup nodes x. Неважно, создан ли узел с именем x или будет создан в будущем .Пока он является созданным в какой-то момент, вы настроены.Он будет получен с карты только тогда, когда вам это нужно.

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

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

Следует соблюдать осторожность и избегать оценки отложенных значений до завершения построения графика.

Answer 2

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

Реальная реализация графа завершена, осталось только заставить двоичную сериализацию работать и работать (используя PLANAR_CODE для начинающих, может быть, Graph6 и Sparse6) и некоторые другие дополнительные вещи.

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

Код можно получить из darcs get <a href="http://code.haskell.org/~ivanm/planar-graph/" rel="nofollow">http://code.haskell.org/~ivanm/planar-graph/</a>; пример использования (для этого я и разрабатываю эту библиотеку): http://code.haskell.org/~ivanm/dangd/.

---

Взято из документации Хэддока в качестве примера его использования:

Например, пусть g относится к следующему графику (где n1 и т. Д. Являются метками и именами переменных):

     ====                    ====
    ( n1 )                  ( n2 )
     ====                    ====





                             ====
                            ( n3 )
                             ====

Мы можем добавить ребро между n1 и n2 (используя Anywhere в качестве EdgePos , поскольку в настоящее время ни на одном узле нет ребер):

 ((e1,e2),g') = addEdge n1 Anywhere n2 Anywhere "e1" "e2" g

Это приведет к следующему графику:

                  e2
     ====  <---------------  ====
    ( n1 )                  ( n2 )
     ====  --------------->  ====
                  e1




                             ====
                            ( n3 )
                             ====

Если мы хотим добавить ребра между n2 и n3, у нас есть три варианты расположения на n2:

• Использовать Anywhere: поскольку есть только один другой край, он не делает Разница с точки зрения внедрения, где идет второй край.

• Положите новый край BeforeEdge e2 (по часовой стрелке вокруг n2).

• Положите новый край AfterEdge e2 (по часовой стрелке вокруг n2).

Поскольку n2 в настоящее время имеет только одно ребро, все три значения EdgePos приведет к тому же графику, поэтому мы можем произвольно выбрать один:

 ((e3,e4),g'') = addEdge n2 (BeforeEdge e2) n3 Anywhere "e3" "e4" g'

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

                  e2
     ====  <---------------  ====
    ( n1 )                  ( n2 )
     ====  --------------->  ====
                  e1         |  ^
                             |  |
                          e3 |  | e4
                             |  |
                             v  |
                             ====
                            ( n3 )
                             ====

Тот же график (до фактических Edge значений; поэтому он не будет удовлетворять ==) было бы получено с:

 ((e4,e3), g'') = addEdge n3 Anywhere n2 (BeforeEdge e2) "e4" "e3" g'

Answer 3

Кажется, вам не нужно хранить ссылку на ребро NextA и NextB внутри ребра.Поскольку это то, что можно вычислить путем обхода текущего Edge, почему бы не написать функцию, которая берет Edge и возвращает его ребро NextA / NextB, которое соответствует диаграмме, основанной на направлении по часовой стрелке частей A и B края.