Ответ 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 узла.