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