SWI Prolog 中无向图的最大空子图

Question

An undirected graph is given. Find the number of internal stability of the graph. That means finding the power of the largest empty subgraph. (The empty subgraph is one with no vertices directly connected by edges).

我设置了边和顶点。我正在显示一个由边未连接的顶点列表。

接下来我该做什么？

reb(a,1,2).   % (* 1 ---a--- 2 ---b--- 3 ---d--- 4 ---e--- 6  *)
reb(b,2,3).   % (*  \_________c_______/                   /   *)
reb(c,1,3).   % (*                      7 ---g--- 5 ---f-*    *)
reb(d,3,4).                             
reb(e,4,6).
reb(f,5,6).
reb(g,5,7).

ver(1).   % (* empty subgraphs here are                   *)
ver(2).   % (*  145, 146, 147, 245, 246, 247, 35, 36, ... *)
ver(3).   % (* the length of the largest of them is 3     *)
ver(4).   
ver(5).
ver(6).
ver(7).

edge(A, B) :- reb(_,A,B) ; reb(_,B,A).

nonadjacency(A, B) :-
    ver(A), ver(B), \+(edge(A,B)).

do(L) :-
    findall( (A,B), nonadjacency (A,B), L), write(L), nl.

dfs(From, To, _, [edge(From, To)]) :-
    edge(From, To).

dfs(From, To, VisitedNodes, [(From, X) | TailPath]) :- 
    edge(From, X), 
    not(member(X, VisitedNode)),
    dfs(X, To, [From | VisitedNodes], TailPath).

Answer 1

与其自己努力构建非连接（你称之为“空”）子图，不如让 Prolog 为我们努力，构建一个最大的子集是not“非空”，即not连接：

empty_subgraph(       E, M ) :-
    findall( X, ver(X), Vertices),
    subset( Vertices, E ),
    \+ is_connected(  E ),
    length(           E, M ).

is_connected(  E ) :-
    select( A, E, N ), 
    select( B,    N, _),
    \+ \+ ( reb(_,A,B) ; reb(_,B,A) ).   % an edge exists

使用 select/3.

剩下的就是枚举 Vertices 的子集，从大到小。

简单的代码行不通：

subset( S, S).
subset( S, X) :- select(_, S, N), subset( N, X).

你明白为什么了吗？

。 . .

答案是，Prolog的深度优先搜索策略。为了在较短的子集之前获得较大的子集，我们需要广度优先搜索。必须自己编码：

subset( S, X) :- XS = [S|T], bfs_subsets(XS,T), member(X,XS).

bfs_subsets( [[] | _], []  ) :- !.
bfs_subsets( [[_]| _], [[]]) :- !.
bfs_subsets( [S  | T],   Q ) :-
    findall( N, select(_, S, N), NS ),
    append( NS,       Z, Q ),
    bfs_subsets(   T, Z ).

有很多多余的答案，但它们的产生顺序是我们想要的。先正确，后效率！产生的第一个答案将是最长的空子图中的一个，我们不关心是哪一个。

70 ?- empty_subgraph( E, M ).
E = [3, 6, 7],
M = 3 ;
E = [3, 6, 7],
M = 3 ;
E = [2, 6, 7],
M = 3 ;
E = [2, 6, 7],
M = 3 ;
E = [2, 4, 7],
M = 3 ;
.......

欢迎您找到消除重复项的方法，或者更好的是，首先不生成任何重复项。

SWI Prolog 中无向图的最大空子图

Largest empty subgraph of an undirected graph in SWI Prolog

graph

prolog

undirected-graph