Как создать циклические (и неизменные) структуры данных в Clojure без дополнительной косвенности?

Мне нужно представлять ориентированные графы в Clojure. Я хотел бы представить каждый node в графе как объект (возможно, запись), который включает в себя поле под названием :edges, которое представляет собой набор узлов, которые непосредственно доступны из текущего node. Надеюсь, это само собой разумеется, но я бы хотел, чтобы эти графики были неизменными.

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

Однако этот подход не работает для циклических графов. Единственным обходным решением, которое я могу придумать, является наличие отдельной коллекции (возможно, карты или вектора) всех ребер для целого графика. Поле :edges в каждом node будет иметь ключ (или индекс) в сборке графов ребер. Добавление этого дополнительного уровня косвенности работает, потому что я могу создавать ключи (или индексы) до того, что они (будут) ссылаться на существующие, но это похоже на kludge. Мало того, что мне нужно делать дополнительный поиск, когда я хочу посетить соседний node, но мне также нужно передать глобальную коллекцию граней, которая кажется очень неуклюжей.

Я слышал, что у некоторых Lisps есть способ создания циклических списков, не прибегая к функциям мутации. Есть ли способ создать неизменяемые циклические структуры данных в Clojure?

Ответ 1

Я играл с этим последние несколько дней.

Я сначала попытался сделать каждый node удержанием набора refs к ребрам, и каждое ребро удерживает набор ссылок refs на узлы. Я установил их равными друг другу в типе операции (dosync... (ref-set...)). Мне это не понравилось, потому что для изменения одного node требуется большое количество обновлений, а распечатка графика была немного сложной. Мне пришлось переопределить мультиметод print-method, чтобы repl не переполнял переполнение. Также в любое время, когда я хотел добавить ребро к существующему node, мне сначала нужно было извлечь фактический node из графика, а затем делать всевозможные обновления краев и все такое, чтобы убедиться, что все держатся за самая последняя версия другой вещи. Кроме того, поскольку все было в рефлексии, определение того, связано ли что-то с чем-то другим, была операция линейного времени, которая казалась неэлегантной. Я не очень далеко до определения того, что выполнение каких-либо полезных алгоритмов с помощью этого метода было бы затруднительным.

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

Похоже на это, вроде, для 1->2, 1->3, 2->5, 5->2

(def graph {node-1 {node-2 edge12, node-3 edge13},
            node-2 {node-5 edge25},
            node-3 nil ;;no edge leaves from node 3
            node-5 {node-2 edge52}) ;; nodes 2 and 5 have an undirected edge

Для доступа к соседям node -1 вы идете (keys (graph node-1)) или вызываете функцию, определенную в другом месте (neighbors graph node-1), или можете сказать ((graph node-1) node-2), чтобы получить ребро от 1->2.

Несколько преимуществ:

Постоянный поиск по времени node в графе и соседнего node, или возврат nil, если он не существует.
Простое и гибкое определение края. Ориентированное ребро существует неявно, когда вы добавляете сосед к записи node на карте, а его значение (или структура для получения дополнительной информации) предоставляется явно или равно нулю.
Вам не нужно искать существующий node, чтобы что-то делать с ним. Он неизменен, поэтому вы можете определить его один раз, прежде чем добавлять его в график, а затем вам не нужно преследовать его при получении последней версии, когда ситуация изменится. Если соединение в графике изменяется, вы меняете структуру графика, а не сами узлы/ребра.
Это объединяет лучшие функции матричного представления (топология графа находится в самом графическом кармане, не закодированном в узлах и ребрах, постоянном поиске по времени и не мутирующих узлах и ребрах) и список смежности (каждый node "имеет" список своих соседних узлов, эффективное пространство, поскольку у вас нет никаких "пробелов", таких как каноническая разреженная матрица).
Вы можете иметь кратные ребра между узлами, и если вы случайно определяете ребро, которое уже существует точно, структура карты заботится о том, чтобы вы не дублировали его.
Node, а идентификатор края сохраняется clojure. Мне не нужно придумывать какую-либо схему индексирования или общую точку отсчета. Ключи и значения карт - это то, что они представляют, а не поиск в другом месте или ref. Ваша структура node может быть всеми nils, и до тех пор, пока она уникальна, ее можно представить на графике.

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

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

Ответ 2

Вы можете обернуть каждый node в ref, чтобы дать ему стабильный дескриптор, чтобы указать (и разрешить вам изменять ссылку, которая может начинаться с нуля). Тогда можно построить циклические графики таким образом. Конечно, у этого есть "дополнительное" направление.

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

Ответ 3

Я столкнулся с этой задачей раньше и пришел к выводу, что в настоящее время невозможно использовать по-настоящему неизменяемые структуры данных в Clojure.

Однако вы можете выбрать один или несколько из следующих вариантов:

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