Common lisp: графовые структуры данных

Юзай setf. Узлы - или cons-ы, или вектора.

Не совсем понял. У меня проблема в следующем

1) имеем ориентированную графовую структуру данных

2) есть узел. Обозначим его a.

3) есть два других узла b и с, которые "ссылаются" на узел a. Для определенности имя ссылки обозначим как a-link.

В конечном счете необходимо нечто вроде (get-linked-element b 'a-link) => a (get-linked-element c 'a-link) => a

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

Неправ ты, неправ.

Я же сказал - setf.

(setq a (cons 1 2))
(setq b (cons 3 4))
(setf (cdr b) a)
(setf (cdr a) b)

и получилось колечко...

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

Теперь конструктивно:

1. битовая матрица. Да, как в С :)

2. пакет cl-graph (http://common-lisp.net/project/cl-graph/)

Смотря какие графы. Если у тебя граф - это AST после пары проходов компиляции - то списки, и только списки, пусть он и зацикленный по самые гланды. Никаких битовых матриц!

> Если у тебя граф - это AST

Если граф -- дерево, то это другой вопрос. Я так понял, что человека интересуют не частные случаи.

> Если граф -- дерево

Зачем дерево? Оно может уже зацикленным быть. AST только называется T, а на самом деле в общем виде это орграф.

>(setq a (cons 1 2))
>(setq b (cons 3 4))
>(setf (cdr b) a)
>(setf (cdr a) b) 

По идее вместо cons должно стоять либо list либо (cons x (cons y nil))
Место (cdr x) должно стоять (rest (last x))

А по херу, главное идею показать. 1 и 4 потерять не жалко.

Осознал как обрабатывать графовые структуры данных. Возникла другая проблема - при работе в repl cmucl-а или slime при печати структур данных с "кольцевыми" связями происходит зацикливание. Как с таким бороться ?

Никак. Всегда "смотреть" только "голову" :)