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?

@false: the edge between 4 and 5 is on purpose to have a disconnected graph. btw, it's also an example of what closure0 should handle, but I can't see how it could be extended, without much complexity... — CapelliC, Nov 17 '14 at 10:56
@CapelliC: I agree that my comment is ambiguous, I wanted to refer to what @ Sam said. Will rewrite it .. — false, Nov 17 '14 at 11:00
[with clarification] "So because there is no edge between 3 and 4 this should fail." Why does there have to be an edge between 3 and 4? An edge between 5 and one of 1,2,3 would be just as good. Brief: it is not clear how you are defining the set of vertices. — false, Nov 17 '14 at 11:01

score 2 · Answer 1 · edited May 23 '17 at 10:28

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

@false Yup, altered my answer accordingly. Is the `0` suffix a convention of some kind / what does it mean? — Wouter Beek, Nov 17 '14 at 07:40
`closure/3` is commonly the name for transitive closure, without the reflexive part. — false, Nov 17 '14 at 07:41
Ah, so it's mainly to prevent interference with existing libraries. Plus the 0 may be taken to refer to the "reflexive closure"-part, i.e. a traversion of depth 0 in the graph. — Wouter Beek, Nov 17 '14 at 07:43
The name would not fit. See [this](http://stackoverflow.com/a/15483764/772868) for `closure/3`. If you have a better name add it to my question. — false, Nov 17 '14 at 07:46

score 2 · Answer 2 · edited May 23 '17 at 12:16

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

Determining if graph is connected in prolog

2 Answers2

Solution 1: Using a library

Solution 2: "Do it yourself"