有向圖中所有節點列表

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。

剛剛獲得頂點當然是微不足道的，但對於任何更復雜的圖書館總是更好。