Largest empty subgraph of an undirected graph in 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).

I set the edges and vertices. And I'm displaying a list of vertices unconnected by edges.

What should I do next?

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

I changed "most" to "biggest", hope it is OK. (you probably had it translated from some term in Russian). ---- your graph has no unconnected subgraph, all 7 of the vertices are connected -- if we consider connectivity as the symmetric transitive closure of reb/3 relation. i.e. 1--2--3--4--6--5--7. or is it not the case? could you just show us the unconnected subgraph in your case please? just the result, not the code. — Will Ness
empty subgraphs here are 145, 146, 147, 245, 246, 247, 35, 36, 37. the length of the largest of them is 3 — Anastasia Selikova
why not 167? wouldn't it too be considered "empty subgraph"? could "empty subgraph" be defined as "the set of vertices of the original graph such that there are no edges in the original graph immediately connecting any of the vertices in that set"? (just trying to understand the question) — Will Ness
My SWI-Prolog reports a syntax error on line 23 because of the illegal space in nonadjacency (A,B), and a severe singleton variable warning because of the VisitedNode typo on line 30. Please update the question. — Isabelle Newbie

Will Ness Will Ness · Accepted Answer · 2020-11-12T15:34:53

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

Using select/3.

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

Do you see why?

. . .

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.

Largest empty subgraph of an undirected graph in SWI Prolog

1 Answers