如何判断图表是否使用答案集编程强连接？

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）