CODEWITHSUNDEEP
prologgraph-theory
Madusanka
Madusanka

Reputation: 3018

How to check whether two vertices are connected or not in prolog?

Here my problem is I want to check whether two nodes are connected or not.

My Knowledge base is,

edge(a,b):-!.
edge(b,a):-!.
edge(a,e):-!.
edge(e,a):-!.
edge(b,c):-!.
edge(c,b):-!.
edge(b,d):-!.
edge(d,b):-!.
edge(c,e):-!.
edge(e,c):-!.
edge(d,e):-!.
edge(e,d):-!.
edge(a,f):-!.
edge(f,a):-!.

isConnected(X,X):-!.
isConnected(X,Y):-edge(X,Y),!.
isConnected(X,Z):-not(edge(X,Y)),edge(X,Y),isConnected(Y,Z),!.
isConnected(X,Z):not(edge(X,Y)),edge(X,Z),not(isConnected(Y,Z)),isConnected(Z,Y),!.

Upvotes: 3

Views: 2359

Answers (1)

Daniel Lyons
Daniel Lyons

Reputation: 22803

Whoa there. That's a lot of cuts. Cuts are sometimes helpful in Prolog for pruning unnecessary answers, but when you have a fact like this:

edge(a, b).

There is absolutely nothing to be gained by writing it as:

edge(a, b) :- !.

After all, there's no choice point there, because there are no variables there and no alternate solutions. So first, let's fix your facts by removing all those cuts.

Next let's look at what isConnected is saying. Let's read it aloud in English and see if it makes sense.

  1. X is connected to X.
  2. X is connected to Y if there is an edge from X to Y.
  3. X is connected to Z if there is not an edge from X to Y, but there is an edge from X to Y and Y is connected to Z. (???)
  4. X is connected to Z if there is not an edge from X to Y, but there is an edge from X to Z, and Y is not connected to Z but Z is connected to Y. (???)

The first two seem quite reasonable. The third one seems to contradict itself right away. How can not(edge(X, Y)) be true at the same time as edge(X, Y)? Keep in mind that the comma in Prolog means and, not just then. The rest of the clause is meaningless because these two conditions cannot ever both be true. Probably what you meant to say was something like this: X is connected to Z if there is an edge from X to Y and Y is connected to Z. That would look like this in Prolog:

isConnected(X, Z) :- edge(X, Y), isConnected(Y, Z).

Logically, this is certainly true, but for any kind of complex graph this is going to be monstrously expensive to calculate, because checking if X is connected to Z might imply checking if Y is connected to Z for all the same nodes.

Your fourth clause has a typo in that the : should be a :-. More importantly, it looks like you're trying to compensate here for the directionality of your edges. A better place to do this would have been around step 2, providing both cases:

isConnected(X, Y) :- edge(X, Y) ; edge(Y, X).

I'm not sure, based on your fact database, whether you actually mean this though; you've duplicated all your facts to account for both directions. If the fact database represents a directed graph, this is probably necessary and the rules should not try inverting the nodes. If it instead represents an undirected graph, your predicate should just account for it with a rule like this that checks both sides, and you should only list each edge once. Doing it both ways, you're telling Prolog to do a bunch of unnecessary work, as it first checks edge(a, b), then the rule inverts it to edge(b, a), then moves on to the next fact edge(b, a) and then the rule inverts it to edge(a, b), in effect checking everything twice.

The elephant in the room here is that even if you do successfully turn this into a logical solution to the problem it's going to be hideously inefficient. There are algorithms for determining if two things are connected that keep track of what has been seen and what has not, and I think you'd be much better off implementing one of those.

Upvotes: 2

Related Questions