% P88 (**) Connected components
% Write a predicate that splits a graph into its connected components.
:- ensure_loaded(p80). % conversions
:- ensure_loaded(p81). % path/4
% connected_components(G,Gs) :- Gs is the list of the connected components
% of the graph G (only for graphs, not for digraphs!)
% (gterm, list-of-gterms), (+,-)
connected_components(graph([],[]),[]) :- !.
connected_components(graph(Ns,Es),[graph(Ns1,Es1)|Gs]) :-
Ns = [N|_],
component(graph(Ns,Es),N,graph(Ns1,Es1)),
subtract(Ns,Ns1,NsR),
subgraph(graph(Ns,Es),graph(NsR,EsR)),
connected_components(graph(NsR,EsR),Gs).
component(graph(Ns,Es),N,graph(Ns1,Es1)) :-
Pred =..[is_path,graph(Ns,Es),N],
sublist(Pred,Ns,Ns1),
subgraph(graph(Ns,Es),graph(Ns1,Es1)).
is_path(Graph,A,B) :- path(Graph,A,B,_).
% subgraph(G,G1) :- G1 is a subgraph of G
subgraph(graph(Ns,Es),graph(Ns1,Es1)) :-
subset(Ns1,Ns),
Pred =.. [edge_is_compatible,Ns1],
sublist(Pred,Es,Es1).
edge_is_compatible(Ns1,Z) :-
(Z = e(X,Y),!; Z = e(X,Y,_)),
memberchk(X,Ns1),
memberchk(Y,Ns1).