Clever Geek Handbook

Determining if a graph is connected in a prologue

I need to make a predicate isConnected/1

that takes a graph as an argument and determines if there is an undirected path between 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 must fail.
How should I approach this problem? Should I go through each edge and write the edges in the list? or is there a better approach for this?

+3


source to share


2 answers


Solution 1: Using the library

It's easy if you use the graph theory library. First, I'll rewrite your graph using S-view:

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

Then I will use the library ugraph

included with 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 (recommended if you want to be a better programmer!). One way to implement this form is to use clos0 / 3 , which implements reflexive-transitive closure on a binary predicate (generated by SO user false).

If you add matching edges to your database:

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

... now you can request:

?- 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].
+2


source


Assuming this is a follow-up 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 define a set of nodes. Usually a set of nodes is given, but it seems that you want them to be defined implicitly across all edges:

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


Now connection means every 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 of this assumes that nodes are actually terrestrial members.)

Here are all the missing meta-predicate declarations:

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


source






More articles:


All Articles