LINUX.ORG.RU

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

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

anonymous ()
Ответ на: Re: Common lisp: графовые структуры данных от anonymous

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

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

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

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

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

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

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

anonymous ()

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

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

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

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

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

mind ()
Ответ на: Re: Common lisp: графовые структуры данных от mind

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

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

anonymous ()
Ответ на: Re: Common lisp: графовые структуры данных от mind

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

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

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

anonymous ()

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

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

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.