Prima-Kraskala problem in Prolog

In this topic we will discuss the Prima-Kraskal problem ( “greedy algorithm” ) and its solution in the Prolog language.

Started!


Task: It is given a flat country and there are n cities in it. It is necessary to connect all cities by telephone so that the total length of telephone lines is minimal.
')
Clarification of the problem. The problem is about telephone communication, i.e. implies transitivity of communication: if the i-th city is associated with the j-th, and the j-th with the k-th. It is also implied that telephone lines can be branched only at the telephone exchange, and not in the open field. Finally, the requirement of minimality (together with transitivity) means that there will be no cycles in the desired solution.

In terms of graph theory, the Prima-Kraskal problem is as follows:
Given a graph with n vertices; edge lengths are given. Find a spanning tree of minimum length.
As is known, a tree with n vertices has n-1 edges. It turns out that each edge must be chosen greedily (as long as there are no cycles).

Brief description of the Prima-Kraskal algorithm: Do n-1 times in a loop: ”select the shortest edge that has not yet been selected, provided that they do not form a cycle with those already selected”.
The edges chosen in this way form the desired tree.

To solve the problem, a graph will be created, represented as a list of edges and vertices.

Spanning tree search algorithm can be divided into the following steps:

• sort the list of edges in ascending order of their length;
• apply the “greedy” algorithm and get a list of edges;
• check whether the resulting list of edges is a spanning tree.

The greedy algorithm works as follows: it is necessary to select a not yet selected edge of the minimum length (the edge should not form a cycle with other selected edges).

Now the implementation of the resulting algorithm on SWI-Prolog:

%
launch:-
write_ln(':'), read(X),
write_ln(' :'), read(Y),
city(X,Y,Z),
write_ln(' :'),
write(Z).

launch:-
write_ln(' ').

%
%
%Z1 - ,
%Y-
%Z2 -
minimum([],Z,Z):- !.

minimum([[X1,X2,_]|Y],Z1,Z2):-
not(search(X1,X2,Z1,[X1])),!,
minimum(Y,[[X1,X2]|Z1],Z2).

minimum([_|Y],Z1,Z2):- minimum(Y,Z1,Z2). %

% 1 2
% - 7.
%, Y - , Z - ( ).
search(X1,X2,Y,_):- member([X1,X2],Y).

search(X1,X2,Y,_):- member([X2,X1],Y).

search(X1,X2,Y,Z):- member([X1,X3],Y),
not(member(X3,Z)), search(X3,X2,Y,[X3|Z]).

search(X1,X2,Y,Z):- member([X3,X1],Y),
not(member(X3,Z)), search(X3,X2,Y,[X3|Z]).

% ( )
%
% L1 - , X - , L2 -
ins(X,[],[X]).

ins([X1,X2,R1],[[Y1,Y2,R2]|L],[[X1,X2,R1]|[[Y1,Y2,R2]|L]]):- R1<R2,!.
ins(X,[Y|L1],[Y|L2]):- ins(X,L1,L2).

%
%
%L - ,Y1 - , Y3 - .
sortrast([],Y,Y). sortrast([X|L],Y1,Y3):- ins(X,Y1,Y2), sortrast(L,Y2,Y3).

% .
%
%Z - X - , Y - ,
city([X|L],Y,Z):- sortrast(Y,[],Y1), minimum(Y1,[],Z), all(X,L,Z).

%
%
% x -, Z - L -
all(_,[],_).
all(X,[Y|L],Z):- search(X,Y,Z,[X]),!,all(X,L,Z).

The program has implemented the following predicates:
• Launch - used to display information on the screen. For example, a list of cities and scatterings between them.
• Sortrast (L1, L2, L3) - sorts the list of L1 by the method of inserts, where L2 is the current list, L3 is the result.
• ity (X, Y, Z) - connection of cities by telephone lines, where X is a list of cities, Y is a list of distances, Z is the result.
• Search (X1, X2, Y, Z ) - implements the search for the path from the vertex X1 to the vertex X2, where Y is the list of edges, Z is the list of vertices (which are passed).
• all (X, Y, Z) - checks for city coverage of the telephone network. Where X is the first city, L is the list of other cities, Z is the list of telephone lines.
• ins (X, L1, L2) - the predicate inserts the element X into L1 (sorted list of edges). L2 is the result.
• minimum (Y, Z1, Z2) - a predicate for finding the minimum (in length) connection. Where Y is the list of edges, Z1 is the selected edges, Z2 is the result.

The results of the program: