如何判斷圖表是否使用答案集編程強連接？

Question

我是新來回答設置編程，可以使用一些幫助。我一直在閱讀this，但仍然可以使用一些幫助。如何使用答案集編程來判斷一個圖是否強連接？

我的頭腦風暴：由節點和邊緣表示

• 格拉夫（即;節點（1..2），邊緣（1,2），和邊緣（2,1））。

• 現在我需要規則「strong（）： - ......」，如果圖形是強連接的，則爲true。

• 如果您可以從任何節點開始，並沿着它們指向的方向跟隨邊緣到達任何其他節點，則該圖形是強連接的。

• 所以我的程序需要把每個節點X和沿有向邊沿去嘗試和到達其他每個節點。如果它到達每個其他節點，則爲真，否則爲False。

Strong（）： - ？

Answer 1

首先，除非你的圖是定向的，你必須得到對稱的邊緣：

edge(X,Y):- edge(Y,X). 

然後，你需要告訴兩個節點連接，如果它們之間的路徑：

connected(X,Y):- edge(X,Y). 
connected(X,Z):- edge(X,Y) ; connected(Y,Z). 

現在

，strong認爲如果對所有節點對，它們連接：

strong:- connected(X,Y): edge(X,_), edge(_,Y). 

的替代版本可以是：

not_strong:- not connected(X,Y) ; edge(X,_) ; edge(_,Y). 
strong:- not not_strong. 

---

（測試用clingo 4.5.4）