Determining if graph is connected in prolog

Question

I need to make a predicate isConnected/1 that takes a graph as an argument and determines if there is an undirected path between the pairs.

Suppose I have a list of edges (where G is a graph):

isEdge(G,1,2).
isEdge(G,2,3).
isEdge(G,4,5).

So because there is no edge between 3 and 4 this should fail.
How would I approach this problem? Would I have to traverse though each edge and record the edges in a list? or is there a better approach to do this?

Answer 1

Solution 1: Using a library

This is easy once you use a graph theory library. I'll first rewrite your graph using S-representation:

[1-[2],2-[1,3],3-[2],4-[5],5-[4]]

Then I'll use library ugraph included in SWI-Prolog (thanks to Richard O'Keefe and Vitor Santos Costa):

?- use_module(library(ugraph)).
?- G = [1-[2],2-[1,3],3-[2],4-[5],5-[4]], vertices(G, Vs), member(V, Vs), reachable(V, G, Ws).
G = [1-[2], 2-[1, 3], 3-[2], 4-[5], 5-[4]],
Vs = [1, 2, 3, 4, 5],
V = 1,
Ws = [1, 2, 3] ;
G = [1-[2], 2-[1, 3], 3-[2], 4-[5], 5-[4]],
Vs = [1, 2, 3, 4, 5],
V = 2,
Ws = [1, 2, 3] ;
G = [1-[2], 2-[1, 3], 3-[2], 4-[5], 5-[4]],
Vs = [1, 2, 3, 4, 5],
V = 3,
Ws = [1, 2, 3] ;
G = [1-[2], 2-[1, 3], 3-[2], 4-[5], 5-[4]],
Vs = [1, 2, 3, 4, 5],
V = 4,
Ws = [4, 5] ;
G = [1-[2], 2-[1, 3], 3-[2], 4-[5], 5-[4]],
Vs = [1, 2, 3, 4, 5],
V = 5,
Ws = [4, 5].

Solution 2: "Do it yourself"

Instead of relying on existing libraries, you can also implement this yourself in various ways (much recommended if you want to become a better programmer!). One way to implement this form the ground up is to use closure0/3 which implements reflexive-transitive closure over a binary predicate (created by SO user false).

If you add the appropriate edges to your database:

edge(1,2).
edge(2,1).
edge(2,3).
edge(3,2).
edge(4,5).
edge(5,4).

... you can now query:

?- member(V, [1,2,3,4,5]), findall(W, closure0(edge, V, W), Ws).
V = 1,
Ws = [1, 2, 3] ;
V = 2,
Ws = [2, 1, 3] ;
V = 3,
Ws = [3, 2, 1] ;
V = 4,
Ws = [4, 5] ;
V = 5,
Ws = [5, 4].

Answer 2

Assuming that this is a followup to this question:

First, you need to define what it means to be connected:

connected_to(R_2, A,B) :-
   (  call(R_2, A,B)
   ;  call(R_2, B,A)
   ).

Then you need to determine the set of nodes. Commonly the set of nodes is given, but it seems you want them being defined implicitly through all the edges:

rel_nodes(R_2, Nodes) :-
   setof(Node, Next^connected_to(R_2, Node,Next), Nodes).

Now being connected means that each node is connected to all other nodes.

is_connected(R_2) :-
   rel_nodes(R_2, Vs),
   maplist({R_2,Vs}+\V0^setof(V, closure0(connected_to(R_2), V0,V), Vs), Vs).

(All this assumes that the nodes are actually ground terms.)

Here are all the missing meta predicate declarations:

:- meta_predicate connected_to(2,?,?), rel_nodes(2,?), is_connected(2).