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

Question

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

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

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

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

Answer 1

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

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

Answer 2

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

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

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

Это выглядит примерно так, для 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

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

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

1. Постоянный поиск по времени узла в графе и соседнего узла или возврат нуля, если он не существует.
2. Простое и гибкое определение ребер.Направленный край существует неявно, когда вы добавляете соседа к записи узла на карте, и его значение (или структура для получения дополнительной информации) предоставляется явно, или ноль.
3. Вам не нужно искатьсуществующий узел, чтобы сделать что-нибудь с ним.Он неизменен, так что вы можете определить его один раз, прежде чем добавить его в график, и тогда вам не придется искать его, чтобы получить последнюю версию, когда все изменится.Если соединение в графе изменяется, вы изменяете структуру графа, а не сами узлы / ребра.
4. Это объединяет лучшие характеристики матричного представления (топология графа находится в самой карте графа, не закодированной вузлы и ребра, поиск в постоянном времени и неизменяемые узлы и ребра) и список смежности (каждый узел «имеет» список соседних узлов, экономия пространства, так как у вас нет никаких «пробелов», как у каноническогоразреженная матрица).
5. У вас может быть несколько ребер между узлами, и если вы случайно определите ребро, которое уже точно существует, структура карты позаботится о том, чтобы вы не дублировали ее.
6. Идентификация узла и края сохраняется путем clojure.Мне не нужно придумывать какую-либо схему индексации или общий ориентир.Ключи и значения карт - это вещи, которые они представляют, а не поиск в другом месте или ссылка.Ваша структура узла может быть все nils, и пока она уникальна, она может быть представлена ​​на графике.

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

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

Answer 3

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

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

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