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

Вам нужна техника, известная как завязывание узла. Он использует ленивую оценку, чтобы выполнить работу. ЦПС не нужен.

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

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

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

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

Вы должны быть осторожны и избегать оценки ленивых значений до того, как закончите построение графика.

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

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

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

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

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

Например, пусть 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'

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