CODEWITHSUNDEEP
prolog
Marijn P
Marijn P

Reputation: 15

Prolog weighted undirected graph

Ik keep struggling with making a weighted undirected graph in Prolog.

The graph is represented by a x-number of predicates like:

% connection(+Source, +Destination, +Weight).
connection(A,B,2).
connection(A,C,3).

What i want to achieve is to make an predicate which gives me the route between two given points (like the route between point A and G)

The graph will be like this:

edge(A,B). 
edge(A,C). 
edge(B,D). 
edge(C,D). 
edge(D,F). 
edge(D,E). 
edge(B,F). 
edge(E,G).

The predicate has to be like this: route(+From, +To, -Path)

Any help is really appreciated!

*Edit

When I use this code:

path(Node, Node, _, [Node]).
path(Start, Finish, Visited, [Start | Path]) :-
    verbinding(Start, X,_),
    not(member(X, Visited)),
    path(X, Finish, [X | Visited], Path).

It gives me the result I want, but it is not following the predicate route(+From, +To, -Path). I would like to get the route from point X to Y without having to worry about the weights.

Upvotes: 0

Views: 1584

Answers (1)

user1812457
user1812457

Reputation:

You need to define your problem a bit more carefully. If you had a directed, acyclic graph, you could say:

path(To, To, [To]).
path(This, To, [This|Rest]) :-
    edge(This, Next),
    path(Next, To, Rest).

If your graph is not acyclic, you definitely need an extra argument.

path(From, To, Path) :-
    path_1(From, To, [], Path).

and your path_1 you sort of have already. You could re-write your check as

\+ memberchk(X, Visited)

but this is a detail. Also, don't leave spaces between the head, pipe symbol and tail in [Head|Tail]. The pipe in some implementations can be a synonym for the disjunction, ;.

But: your graph is at the moment directed, it seems. If you want to make it an undirected graph, the easiest (it seems) would be to add each edge twice, once for each direction, say:

edge(a, b).
edge(b, a).

Or, maybe:

edge(A, B) :- connection(A, B).
edge(A, B) :- connection(B, A).

Then, you most certainly need the Visited context argument, as you do at the moment.

This answer so far completely ignores weights.

Upvotes: 1

Related Questions