分層無向圖表示

Question

我要代表這樣的圖形：

Graph = graph([Object1,Object2,Object3,Object4], 
       [arc(Object1,Object2,connected), 
       arc(Object2,Object4,connected), 
       arc(Object3,Object4,connected), 
       arc(Object1,Object3,connected), 
       arc(Object2,Object3,parallel), 
       arc(Object1,Object4,parallel), 
       arc(Object2,Object3,similar_size), 
       arc(Object1,Object4,similar_size)]) 

我對代碼沒有限制，但是我會堅持這種表示，它適用於所有我已經編碼的其他結構。

我的意思是無向圖，其中頂點是一些對象，邊代表它們之間的無向關係。爲了給你在這個特定的例子中更多的背景，我試圖表示一個矩形，所以對象是它的四個邊（段）。這些片段使用頂點等以相同的方式表示。重點是構建圖表的層次結構，它表示同一級別上的對象之間的約束。

問題存在於邊緣的表示中。表示弧（a，b）最明顯的方法是將（a，b）和（b，a）放入程序中。但是，這會使我的程序氾濫成倍的數據氾濫。例如，如果我有頂點a，b，c，d。我可以構建段（a，b），（a，c），（a，d），（b，c），（b，d），（c，d）。但我也得到（b，a），（c，a）等等。在這一點上它不是問題。但後來我建立了一個矩形。它可以構建段（a，b），（b，c），（c，d），（a，d）。我想得到答案 - 有一個矩形。然而，你可以計算出這個矩形的組合數。這也需要太多的時間來計算，顯然我不想在矩形級完成。

我想過排序元素。我可以在一個段中排序頂點。但是，如果我想要在矩形中對段進行排序，則約束不再有效。圖表變成了指示。例如考慮前兩個關係，假設我們有弧（a，b）和（a，c）。如果沒有對弧進行排序，則程序按照我的要求進行回答：arc（b，a，connected），arc（a，c，connected）匹配：Object1 = b，Object2 = a，Object4 = c。如果我對元素進行排序，它不再有效，因爲我不能有弧（b，a，連接）和弧（a，b，連接）試用。只有第二個。我會堅持排序，但我不知道如何解決這個最後的問題。

希望我說得很清楚。我寧願儘量接近我已有的表示和想法。但全新的也是非常受歡迎的。我不期待任何確切的答案，而是讓我朝着正確的方向傾斜，或者提出具體的東西來讀，因爲我對Prolog來說很新，也許這個問題並不罕見。

我想從昨天開始解決這個問題，不能拿出任何簡單的答案。我查看了一些離散數學和通用無向圖表示，如鄰接表。如果有任何不清楚的地方，請告訴我 - 我會盡力提供更多細節。

Answer 1

有趣的問題，雖然有點廣泛，因爲它沒有說明你實際想要做的弧，矩形等;只有某些用途時，表示可能是有效的（時間/空間/優雅）。無論如何，這裏有一些想法：

排序
明顯的問題是你提到的問題;

arc(X,Y):- 
    arc_data(X,Y) 
    ; arc_data(Y,X). 

注意，你應該不做這樣的事情：

arc(a,b). 
arc(b,c). 
arc(X,Y):- 
    arc(Y,X) 

，因爲這將導致一個無限循環，如果你可以通過引入成功，如果有序對存在一個條款，解決它該弧線不存在。 如果第一個參數是大於第二個，你可以但只有檢查：

arc(a,b). 
arc(b,c). 
arc(X,Y):- 
    compare(>,X,Y), 
    arc(Y,X) 

這種做法不會解決可能出現由於有兩種方式表示的弧的多種解決方案。 最簡單的解決將是隻檢查一個解決方案，其中只有一個解決方案是使用once/1預計：

3 ?- arc(X,Y). 
X = a, 
Y = b ; 
X = b, 
Y = a. 

4 ?- once(arc(X,Y)). 
X = a, 
Y = b. 

當然你不能做到這一點的時候可能有多種解決方案。

另一種方法是強制執行進一步的抽象：此刻，當你有兩個點（a，b），您可以創建弧（arc(a,b)或arc(b,a)）檢查，如果這些點連接後。相反，你應該通過謂詞創建弧（也可以檢查點是否連接）。好處是，你不再涉足直接弧的表示，因此可以強制執行排序（是的，它基本上是面向對象）：

cv_arc(X,Y,Arc):- 
     (arc(X,Y), 
     Arc = arc(X,Y)) 
    ; (arc(Y,X), 
     Arc = arc(Y,X)). 

（假設爲數據庫arc(a,b)）：

6 ?- cv_arc(a,b,A). 
    A = arc(a, b). 

    7 ?- cv_arc(b,a,A). 
    A = arc(a, b). 

    8 ?- cv_arc(b,c,A). 
    false. 

當然，你需要遵循類似的原則爲其餘的對象;我假設你正在做這樣的事情找一個矩形：由於電弧

rectangle(A,B,C,D):- 
    arc(A,B), 
    arc(B,C), 
    arc(C,D), 
    arc(D,A). 

除了重複的（這是解決），這將承認ABCD，DABC等不同的矩形：

28 ?- rectangle(A,B,C,D). 
A = a, 
B = b, 
C = c, 
D = d ; 
A = b, 
B = c, 
C = d, 
D = a ; 
A = c, 
B = d, 
C = a, 
D = b ; 
A = d, 
B = a, 
C = b, 
D = c. 

我們將再次做同樣的：

rectangle(rectangle(A,B,C,D)):- 
    cv_arc(A,B,AB), 
    cv_arc(B,C,BC), 
    compare(<,AB,BC), 
    cv_arc(C,D,CD), 
    compare(<,BC,CD), 
    cv_arc(D,A,DA), 
    compare(<,CD,DA). 

和運行與arc(a,b). arc(b,c). arc(c,d). arc(a,d).：

27 ?- rectangle(R). 
R = rectangle(a, b, c, d) ; 
false. 

請注意，如果弧的順序錯誤，我們沒有重新排列矩形;我們只是失敗了。這樣我們就避免了重複的解決方案（如果我們命令它們並將它作爲有效的矩形接受，我們將有相同的矩形四次），但是找到矩形的時間增加了。我們通過停止搜索第一個無序的弧而不是創建整個矩形來減少開銷。另外，如果訂購電弧，開銷也會減少（因爲第一次匹配會被排序）。另一方面，如果我們考慮以這種方式搜索所有矩形的複雜性，那麼開銷並不那麼重要。此外，它只適用於我們只需要第一個矩形;如果我們想要獲得更多解決方案或確保沒有其他解決方案，prolog會搜索整棵樹，無論它是否報告解決方案。