SWI Prolog中无向图的最大空子图 [英] Largest empty subgraph of an undirected graph in SWI Prolog

问题描述

给出了无向图.查找图形的内部稳定性数.这意味着找到最大的空子图的幂. (空子图是一个没有顶点通过边直接连接的子图.)

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).

设置边和顶点.而且我正在显示未由边连接的顶点列表.

I set the edges and vertices. And I'm displaying a list of vertices unconnected 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).

推荐答案

让我们自己完成 Prolog 的工作，而不是自己努力构造非连接(称为空")子图.对于我们来说很困难，构造一个最大的子集，该子集是 not "non-empty"，即 not 相连:

Instead of working hard at constructing the non-connected (what you call "empty") subgraphs ourselves, let's have Prolog work hard for us, constructing a largest subset that is not "non-empty", i.e. not connected:

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的子集，从最大到最小.

All that's left is to enumerate the Vertices's subsets, from biggest to smallest.

简单的代码不会削减它:

Simple code won't cut it:

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

你知道为什么吗?

. .

. .

答案是Prolog的深度优先搜索策略.为了在较短的子集之前获得较大的子集，我们需要广度优先搜索.将不得不自己编写代码:

The answer is, Prolog's depth-first search strategy. To get the larger subsets before the shorter ones, we need breadth-first search. Will have to code it ourselves:

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 ).

有很多多余的答案，但是生成它们的顺序是我们想要的.正确至上，效率至上！产生的第一个答案将是最长的空白子图中的一个，我们不在乎哪个.

There's a lot of redundant answers, but the order in which they are produced is as we wanted it. Correctness first, efficiency later! The first answer produced will be one from among the longest empty subgraphs, and we don't care which one.

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 ;
.......

欢迎您找到一种方法来消除重复项，或者更好的办法是一开始就不产生任何重复项.

You're welcome to find a way to get rid of the duplicates, or better yet, to not produce any in the first place.

这篇关于SWI Prolog中无向图的最大空子图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！