Как представить ориентированный циклический граф в Прологе с прямым доступом к соседним вершинам

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

Можно ли представить его в виде дерева, например:

t(left_son,V,right_son)

но как решить циклы?

Я могу составить список ребер:

graph([a,b,c,d],[e(a,b),e(b,c),e(c,a),e(c,d)])

Или просто

[a->[b],b->[c],c->[a,d],d->[]]

 но как избежать вызова функции «член»; в списке при поиске соседей, которые стоят линейного времени?

Спасибо за вашу помощь

Ответы на вопрос(3)

Решение Вопроса

Если ваш граф имеет меньше вершин, чем максимальная арность, разрешенная вашим Прологом (например, SWI-Пролог имеет неограниченную арность), вы можете представить ребра как индексы аргументов:

может бытьthis

G = graph(a-[2],b-[3],c-[1,4],d-[2]).

затем используйтеArg(Edge, G, Vert-Edges) для доступа к соседям.

Конечно, любой Пролог позволит вам описать график, используя факты. Это также предпочтительный способ для очень больших графиков.

:- dynamic edge/2.

edge(a,b).
edge(b,c).
edge(c,a).
edge(c,d).
edge(d,b).

edit Реляционное представление Edge / 2 также получает (потенциально большие) преимущества автоматической индексации.

more edit Я полностью забылRDF а такжеСемантическая паутина, Действительно мощный, мы идем к этому.

 11 апр. 2012 г., 05:19
Пара наблюдений. Сначала OP говорит о построении графа «во время выполнения», поэтому либо будут использоваться динамические предикаты, либо будет создан и передан некоторый сложный термин Пролог. Во-вторых, «постоянное время» доступ, по-видимому, важен только тогда, когда задействованы большие графы. Поэтому, возможно, стратегия должна заключаться в реализации в Прологе с использованием второй формы представления, предложенной chac, а затем переключиться на реализацию в C / C ++ (или другом языке, поддерживающем арифметику указателей), если и когда скорость становится проблемой. Ясность и правильность перед оптимизацией!

В дополнение к представлению, которое предлагает @chac, вы также можете рассмотреть возможность использования атрибутивных переменных (если ваша система Prolog поддерживает это), особенно если вам нужно прикрепить дополнительные атрибуты к вершинам или ребрам во время ваших вычислений. В этом представлении вы будете использовать уникальную переменную для каждой вершины, прикрепите (с помощью put_attr / 3) атрибут, подобный & quot; name & quot; если необходимо, добавьте к нему дополнительный атрибут, например & quot; edge & quot; например, это может быть список вершин или список терминов ребро (E, вершина), где E снова переменная, к которой вы можете прикрепить дополнительные атрибуты, если вам нужно отслеживать информацию, которая влияет на ребра.

 17 апр. 2012 г., 09:09
Пример, который обсуждался вcomp.lang.prolog находит сильно связные компоненты ориентированного графа. Решение, которое было размещено здесь:scc.pl, Дополнительные примеры, такие как максимальные совпадения и алгоритмы максимального потока, см. В библиотеке (clpfd) в SWI-Prolog. Все эти алгоритмы (также пример SCC) требуют дополнительной информации для вершин, например, находится ли она в стеке, была ли она посещена и т. Д., А атрибутные переменные позволяют легко присоединять и изменять такие атрибуты.
 16 апр. 2012 г., 17:05
это кажется действительно интересным. Как насчет небольшого примера?

Естьlibrary(ugraphs) во многих системах Prolog, таких какПЕА, SWI, SICStus, Чао, (Пожалуйста, не стесняйтесь добавлять дополнительные ссылки здесь!) Там, графики представлены в виде списка парVertex-Neighbours, С первого взгляда у вас может сложиться впечатление, что это не очень эффективное представление. В конце концов, доступ к одной вершине пропорционален длине списка. Однако прямой доступ к вершине редко представляет интерес. Большую часть времени график будет обрабатываться одним махом, что часто амортизирует стоимость доступа.

Ваш ответ на вопрос