Как представить ориентированный циклический граф в Прологе с прямым доступом к соседним вершинам
Мне нужно построить ориентированный граф (во время выполнения) с циклами в Прологе, и я не уверен, как его представить. Мое требование состоит в том, что мне нужно добраться от одной вершины до его соседки за постоянное время.
Можно ли представить его в виде дерева, например:
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->[]]но как избежать вызова функции 'member' в списке при поиске соседей, которые стоят линейного времени?Спасибо за вашу помощь
3 ответа
Если ваш граф имеет меньше вершин, чем максимальная арность, разрешенная вашим Прологом (например, SWI-Пролог имеет неограниченную арность), вы можете представить ребра как индексы аргументов:
может быть 
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 также получает (потенциально большие) преимущества автоматической индексации.
больше редактировать Я полностью забыл RDF и Semantic Web. Действительно мощный, мы идем к этому.
В дополнение к представлению, которое предлагает @chac, вы также можете рассмотреть возможность использования атрибутивных переменных (если ваша система Prolog поддерживает это), особенно если вам нужно прикрепить дополнительные атрибуты к вершинам или ребрам во время ваших вычислений. В этом представлении вы будете использовать уникальную переменную для каждой вершины, присоедините (с помощью put_attr/3) атрибут, например, "name", если необходимо, и добавите дополнительный атрибут, такой как "ребра", который, например, может быть списком вершин. или список терминов ребро (E, вершина), где E снова является переменной, к которой вы можете прикрепить дополнительные атрибуты, если вам нужно отслеживать информацию, которая влияет на ребра.
Есть library(ugraphs) во многих системах Prolog, таких как YAP, SWI, SICStus, Ciao. (Пожалуйста, не стесняйтесь добавлять дополнительные ссылки здесь!) Там, графики представлены в виде списка пар Vertex-Neighbours, С первого взгляда у вас может сложиться впечатление, что это не очень эффективное представление. В конце концов, доступ к одной вершине пропорционален длине списка. Однако прямой доступ к вершине редко представляет интерес. Большую часть времени график будет обрабатываться одним махом, что часто амортизирует стоимость доступа.