論理プログラミングで悩んでいます。私はこの問題を抱えています。あなたの何人かが私を助けてくれることを願っています。不連続グラフは、事実によって次のように表されます。
h(0,1).
h(1,2).
h(3,4).
h(3,5).
したがって、2 つの別個のグラフ コンポーネントがあります。リストで表される出力のすべての個別のコンポーネントが必要です。したがって、グラフに 3 つの個別のコンポーネントがある場合は、3 つのリストがあります。上記の例では、期待される出力は[[0,1,2],[3,4,5]]です。
強連結成分はこのモジュールによって計算されます - Markus Triska のサイトから入手しました。
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Strongly connected components of a graph.
Written by Markus Triska (triska@gmx.at), 2011, 2015
Public domain code.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
:- module(scc, [nodes_arcs_sccs/3]).
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Usage:
nodes_arcs_sccs(+Ns, +As, -SCCs)
where:
Ns is a list of nodes. Each node must be a ground term.
As is a list of arc(From,To) terms where From and To are nodes.
SCCs is a list of lists of nodes that are in the same strongly
connected component.
Running time is O(|V| + log(|V|)*|E|).
Example:
%?- nodes_arcs_sccs([a,b,c,d], [arc(a,b),arc(b,a),arc(b,c)], SCCs).
%@ SCCs = [[a,b],[c],[d]].
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
:- use_module(library(assoc)).
nodes_arcs_sccs(Ns, As, Ss) :-
must_be(list(ground), Ns),
must_be(list(ground), As),
catch((maplist(node_var_pair, Ns, Vs, Ps),
list_to_assoc(Ps, Assoc),
maplist(attach_arc(Assoc), As),
scc(Vs, successors),
maplist(v_with_lowlink, Vs, Ls0),
keysort(Ls0, Ls1),
group_pairs_by_key(Ls1, Ss0),
pairs_values(Ss0, Ss),
% reset all attributes
throw(scc(Ss))),
scc(Ss),
true).
% Associate a fresh variable with each node, so that attributes can be
% attached to variables that correspond to nodes.
node_var_pair(N, V, N-V) :- put_attr(V, node, N).
v_with_lowlink(V, L-N) :-
get_attr(V, lowlink, L),
get_attr(V, node, N).
successors(V, Vs) :-
( get_attr(V, successors, Vs) -> true
; Vs = []
).
attach_arc(Assoc, arc(X,Y)) :-
get_assoc(X, Assoc, VX),
get_assoc(Y, Assoc, VY),
successors(VX, Vs),
put_attr(VX, successors, [VY|Vs]).
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Tarjan's strongly connected components algorithm.
DCGs are used to implicitly pass around the global index, stack
and the predicate relating a vertex to its successors.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
scc(Vs, Succ) :- phrase(scc(Vs), [s(0,[],Succ)], _).
scc([]) --> [].
scc([V|Vs]) -->
( vindex_defined(V) -> scc(Vs)
; scc_(V), scc(Vs)
).
scc_(V) -->
vindex_is_index(V),
vlowlink_is_index(V),
index_plus_one,
s_push(V),
successors(V, Tos),
each_edge(Tos, V),
( { get_attr(V, index, VI),
get_attr(V, lowlink, VI) } -> pop_stack_to(V, VI)
; []
).
vindex_defined(V) --> { get_attr(V, index, _) }.
vindex_is_index(V) -->
state(s(Index,_,_)),
{ put_attr(V, index, Index) }.
vlowlink_is_index(V) -->
state(s(Index,_,_)),
{ put_attr(V, lowlink, Index) }.
index_plus_one -->
state(s(I,Stack,Succ), s(I1,Stack,Succ)),
{ I1 is I+1 }.
s_push(V) -->
state(s(I,Stack,Succ), s(I,[V|Stack],Succ)),
{ put_attr(V, in_stack, true) }.
vlowlink_min_lowlink(V, VP) -->
{ get_attr(V, lowlink, VL),
get_attr(VP, lowlink, VPL),
VL1 is min(VL, VPL),
put_attr(V, lowlink, VL1) }.
successors(V, Tos) --> state(s(_,_,Succ)), { call(Succ, V, Tos) }.
pop_stack_to(V, N) -->
state(s(I,[First|Stack],Succ), s(I,Stack,Succ)),
{ del_attr(First, in_stack) },
( { First == V } -> []
; { put_attr(First, lowlink, N) },
pop_stack_to(V, N)
).
each_edge([], _) --> [].
each_edge([VP|VPs], V) -->
( vindex_defined(VP) ->
( v_in_stack(VP) ->
vlowlink_min_lowlink(V, VP)
; []
)
; scc_(VP),
vlowlink_min_lowlink(V, VP)
),
each_edge(VPs, V).
v_in_stack(V) --> { get_attr(V, in_stack, true) }.
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
DCG rules to access the state, using semicontext notation.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
state(S), [S] --> [S].
state(S0, S), [S] --> [S0].
次に、それをフォーマットとインターフェースする必要があります。最初に事実を主張します。
?- [user].
h(0,1).
h(1,2).
h(3,4).
h(3,5).
|: (^D here)
ここでクエリ - グラフを作成するには、無向エッジを両方の「方向」で取得する必要があることに注意してください。
?- setof(N, X^(h(N,X);h(X,N)), Ns), findall(arc(X,Y), (h(X,Y);h(Y,X)), As), nodes_arcs_sccs(Ns,As,SCCs).
Ns = [0, 1, 2, 3, 4, 5],
As = [arc(0, 1), arc(1, 2), arc(3, 4), arc(3, 5), arc(1, 0), arc(2, 1), arc(4, 3), arc(5, 3)],
SCCs = [[0, 1, 2], [3, 4, 5]].
サービス述語を定義する価値があるかもしれませんconnected(X,Y) :- h(X,Y) ; h(Y,X)....
編集
もちろん、モジュール (scc) で見つかった高度に最適化された実装がやり過ぎと見なされる場合は、特に最新の Prolog - SWI で許可されている高レベルの機能を考慮して、修正点を計算して、コードを数行に減らすことができます。 - ライブラリ (yall) でプロローグします。この場合:
gr(Gc) :- h(X,Y), gr([X,Y], Gc).
gr(Gp, Gc) :-
maplist([N,Ms]>>setof(M,(h(N,M);h(M,N)),Ms), Gp, Cs),
append(Cs, UnSorted),
sort(UnSorted, Sorted),
( Sorted \= Gp -> gr(Sorted, Gc) ; Gc = Sorted ).
のように呼ばれる
?- setof(G,gr(G),L).
L = [[0, 1, 2], [3, 4, 5]].
を使用して、次のようにiwhen/2定義できます。binrel_connected/2
:- use_module(library(ugraphs)).
:- use_module(library(lists)).
binrel_connected(R_2, CCs) :-
findall(X-Y, call(R_2,X,Y), Es),
iwhen(ground(Es), ( vertices_edges_to_ugraph([],Es,G0),
reduce(G0,G),
keys_and_values(G,CCs,_) )).
SICStus Prolog 4.5.0 でsymm/2の対称閉鎖のサンプル クエリ:
| ?- binrel_connected(symm(h), CCs).
CCs = [[0,1,2],[3,4,5]] ? ;
no