CODEWITHSUNDEEP
optimizationprologdijkstrapath-findinglogic-programming
Caspian Ahlberg
Caspian Ahlberg

Reputation: 976

Finding all nodes connected to a vertex in Prolog

I am curious about pathfinding algorithms, so I took a look at Dijkstra's. I'm using this video as a guide (and it's what I'm basing my graph on). Here is the graph I am working from:

Image

I now want to be able to find all connections of a given vertex. I think that I should use findall for this, which I tried to use in the all_connections goal below. However, with main, my output is [b,b,b,b]. Why is that happening? That makes no sense. If you understand what I am doing wrong please let me know.

connection(s, c, 3).
connection(c, l, 2).
connection(l, i, 4).
connection(l, j, 4).
connection(i, j, 6).
connection(i, k, 4).
connection(j, k, 4).
connection(k, e, 5).
connection(e, g, 2).
connection(g, h, 2).
connection(h, f, 3).
connection(f, d, 5).
connection(d, a, 4).
connection(b, d, 4).
connection(b, a, 3).
connection(b, s, 2).
connection(b, h, 1).
connection(a, s, 7).

are_connected(A, B, Score) :-
    connection(A, B, Score);
    connection(B, A, Score).

all_connections(A, Z) :-
    findall(A, are_connected(A, _, _), Z).

main :-
    all_connections(b, X),
    write(X).

Upvotes: 3

Views: 342

Answers (2)

Caspian Ahlberg
Caspian Ahlberg

Reputation: 976

Here is how I solved my problem:

are_connected(A, B, S) :-
    connection(A, B, S)
    ;
    connection(B, A, S).

Many thanks to Isabelle for giving me advice on proper conventions.

Upvotes: 2

Isabelle Newbie
Isabelle Newbie

Reputation: 9378

Congratulations on solving your problem. If you post the solution as an answer, we can upvote it.

This is a comment on something else: Since you are a relative beginner, now is the best possible time to learn good coding conventions. Specifically, this:

are_connected(A, B, Score) :-
    connection(A, B, Score);
    connection(B, A, Score).

is very bad. Prolog's disjunction is a very powerful, and often confusing, tool. When you use it, the use should really stick out. Otherwise it's easy to mistake your code for this:

are_connected(A, B, Score) :-
    connection(A, B, Score),
    connection(B, A, Score).

The way you have written this, the semicolon is very easy to miss at the end of a line. Rule of thumb: You should never use ; at the end of a line.

Alternatives:

are_connected(A, B, Score) :-
    connection(A, B, Score).
are_connected(A, B, Score) :-
    connection(B, A, Score).

(This transformation only works since the entire body of your definition is a disjunction.)

are_connected(A, B, Score) :-
    (   connection(A, B, Score)
    ;   connection(B, A, Score) ).

Or:

are_connected(A, B, Score) :-
    (
        connection(A, B, Score)
    ;
        connection(B, A, Score)
    ).

You get the idea. Each of these variants make it clear that what you are doing is very different from using conjunction.

Upvotes: 4

Related Questions