回答セットプログラミングを使用してグラフが強く接続されているかどうかを確認するにはどうすればよいですか？

Question

私はセットプログラミングには新しく、助けを借りることができます。私はthisを読んでいますが、まだ助けてもらえます。グラフが強く接続されているかどうかを判断するために、回答セットプログラミングを使用するにはどうすればよいですか？

マイブレーンストーミング：ノードとエッジで表される

• グラフ（すなわち、ノード（1..2）、エッジ（1,2）、エッジ（2,1））。

• ここで、グラフが強く接続されている場合は、「strong（）： - ......」ルールが必要です。

• グラフが強く結ばれるのは、いずれかのノードから始まり、それらが指し示す方向にエッジをたどって他のノードに到達できる場合です。

• だから私のプログラムは、各ノードXをとり、他のすべてのノードに到達しようとするために有向枝に沿って進む必要があります。他のすべてのノードに到達する場合はTrue、それ以外の場合はFalse。

強（）： - ？

は、あなたのグラフが向けられていない限り、あなたが対称エッジ取得する必要があります

Answer 1

まず ：

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

：次に

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

を、あなたはそれらの間のパスがある場合、2つのノードが接続されていることを伝える必要がありますノードのすべてのペアのために、それらが接続されている場合

さて、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でテスト）

---