通过Prolog随时建立牢固连接的组件 [英] Anytime strongly connected components via Prolog
问题描述
Markus Triska报告了一种算法,该算法可以确定强连接的组件(SCC).是否有一种解决方案,可以在不使用属性变量的情况下确定SCC,并且可以随时使用.这样某些顶点可以具有无限多个边?
Markus Triska has reported an algorithm to determine strongly connected components (SCC). Is there a solution which determines the SCC without making use of attributed variable and that can work anytime. So that some vertices can have infinitely many edges?
我之所以问是因为我想知道B-Prologs 他们随时渴望的制表是否可以复制. B-Prolog确定群集,它们是SCC的名称.但是,它还有一种制表模式,可以快速返回表格结果.
I am asking because I am wondering whether B-Prologs anytime tabling which they call eager can be replicated. B-Prolog determines clusters which is their name for SCC. But it has also a tabling mode where it returns tabled results eagerly.
推荐答案
我猜这算法符合要求,因为只需稍加修改,它就可以在根中实现无限度.当所有边都指向有限多个顶点时,这是SCC算法:
I guess this algorithm fits the bill, since with a little modification it would allow an infinite degree in the root. This is the SCC algorithm when all edges point to finitely many vertices:
% plan(+Atom, -Assoc)
plan(P, R) :-
sccforpred(P, [], [], R, _).
% sccforpred(+Atom, +List, +Assoc, -Assoc, -List)
sccforpred(P, S, H, H, [P]) :-
member(P, S), !.
sccforpred(P, _, H, H, []) :-
member(Q-L, H), (Q = P; member(P, L)), !.
sccforpred(P, S, I, O2, R2) :-
findall(Q, edge(P, Q), L),
sccforlist(L, [P|S], I, O, R),
(member(U, R), member(U, S) ->
O2 = O, R2 = [P|R];
O2 = [P-R|O], R2 = []).
% sccforlist(+List, +List, +Assoc, -Assoc, -List)
sccforlist([], _, H, H, []).
sccforlist([P|Q], S, I, O, R) :-
sccforpred(P, S, I, H, R1),
sccforlist(Q, S, H, O, R2),
findall(U, (member(U, R1); member(U, R2)), K),
sort(K, R).
使用此示例图:
我得到这个结果:
Jekejeke Prolog 4, Runtime Library 1.4.1 (August 20, 2019)
?- plan(21,X).
X = [21-[], 22-[22, 23], 26-[24, 25, 26], 27-[]]
这篇关于通过Prolog随时建立牢固连接的组件的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!