найти список всех узлов в ориентированном графе

Question

дано множество утверждений в прологе, сконструированное для края, обозначающий направленные соединения между узлами:

edge(n1, n2). 
edge(n2, n3). 
edge(n1, n4). 

следующий запрос дает бесконечное конкатенацию [n1, n2, n1, n2 ... ] ...

allnodes([]). 
allnodes([X | [ Y | Xs]]) :- 
    edge(X, Y), 
    allnodes(Xs). 

, когда его спросили, как allnodes(Result)

Что я ищу список [n1, n2, n3, n4] в некотором порядке.

Answer 1

Давайте попробуем разобраться в положениях, которые вы написали. В первом разделе allnodes([]). в основном говорится: «нет узлов». Это, очевидно, не так, если только никаких границ не существует.

Второе предложение может интерпретироваться по строкам «все узлы состоят из X и Y, если есть ребро от X до Y, плюс все узлы». См. Рекурсию здесь? Список содержит себя как хвост! Вот почему вы получаете одни и те же узлы снова и снова.

Что вы на самом деле хотите, это набор всех узлов, которые встречаются как начальный или конечный узел для ребра.

Для того, чтобы облегчить для себя, давайте сначала перевести Prolog, что это значит для чего-то, чтобы быть узлом:

node(N) :- edge(N, _). 
node(N) :- edge(_, N). 

просто. Что-то есть узел, если там начинается какой-то край, или какой-то край заканчивается там.

Теперь все, что нам нужно сделать, это найти все, что удовлетворяет вышеуказанному предикату.

allnodes(Nodes) :- setof(N, node(N), Nodes). 

Обратите внимание, что я использую setof/3, а не findall/3 для удаления дубликатов, как указано выше, определение node/2 будет успешным один раз для каждого вхождения узла в кромке, например, он будет успешным дважды для n1 и n2.

Это дает результат, который вы ищете:

?- allnodes(N). 
N = [n1, n2, n3, n4] 

Answer 2

Рассмотрите возможность использования существующей библиотеки, например library(ugraphs). Это очень хорошо документировано, но чтобы вы начали, вот как вы можете сделать график из списка ребер, а затем показать все вершины:

?- bagof(A-B, edge(A, B), Edges), 
    vertices_edges_to_ugraph([], Edges, G), 
    vertices(G, Vertices). 
Edges = [n1-n2, n1-n4, n2-n3], 
G = [n1-[n2, n4], n2-[n3], n3-[], n4-[]], 
Vertices = [n1, n2, n3, n4]. 

Это также использует bagof/3 для построения списка From-To пара , Остальные два предиката из библиотеки. Этот пример относится к SWI-Prolog, но сама библиотека должна работать с любой полупристойной реализацией Prolog и the code is on Github.

Просто получение вершин, конечно, тривиально, но для чего-то более сложного библиотека всегда лучше.