Алгоритмы Флойда и Варшалла в Прологе - PullRequest
Новая
       22

Алгоритмы Флойда и Варшалла в Прологе

1 голос
/ 21 апреля 2011

Я хочу запрограммировать эти алгоритмы на Прологе, и сначала мне нужно создать матрицу из списка графиков. Я делал это раньше (также с помощью некоторых из вас, ребята), но теперь я не знаю, как сохранить это в списке списков (что, я полагаю, лучший подход в случае пролога). Я думаю, что смогу продолжить оттуда (с тройным циклом for в каждом из алгоритмов). Логика программы не сложная для меня, но как работать с данными. Извините за беспокойство и заранее спасибо!

Мой матричный генератор: 

graph(a,b).
graph(a,a).
graph(b,c).
graph(b,d).
graph(c,d).
graph(a,e).
graph(e,f).

matrix :- allnodes(X),printmatrix(X).

node(X) :- graph(X,_).
node(X) :- graph(_,X).
allnodes(Nodes) :- setof(X, node(X), Nodes).

printedge(X,Y) :-    graph(Y,X), write('1 ').
printedge(X,Y) :- \+ graph(Y,X), write('0 ').

printmatrix(List):- member(Y, List),nl,member(X, List),printedge(X,Y),fail.

1 Ответ

2 голосов
/ 06 мая 2011

Ваш предыдущий вопрос Матрица смежности в прологе касалась визуального отображения (строка за строкой) матрицы смежности графика.Здесь мы рассмотрим, как реализовать / представить матрицу смежности как термин Пролог.В частности, мы будем использовать предикат allnodes / 1 , показанный выше, в качестве средства получения списка всех узлов.

В Прологе отсутствует какой-либо собственный тип данных "матрицы", поэтому подходздесь будет использоваться список списков для представления матрицы смежности.Записи организованы по «строке» в 0 и 1, которые обозначают смежность узла, соответствующего строке, с этим узлом, соответствующим столбцу.

Глядя на ваш пример graph / 2 фактыЯ вижу, что вы включили один край (от a до a).Я не уверен, хотите ли вы, чтобы график был направленным или ненаправленным, поэтому я предполагаю, что ориентированный граф был задуман, и отмечу, где потребуется небольшое изменение, если в противном случае имелся в виду ненаправленный граф.

это «шаблон дизайна», который определяет список, применяя правило к каждому элементу в списке.Здесь мы делаем это одним способом построения каждой строки «матрицы», а также (принимая это как наше правило) для построения всего списка списков. 

/* construct adjacency matrix for directed graph (allow self-edges) */
adjacency(AdjM) :-
    allnodes(L),
    adjMatrix(L,L,AdjM).

adjMatrix([ ],_,[ ]).
adjMatrix([H|T],L,[Row|Rows]) :-
    row_AdjM(H,L,Row),
    adjMatrix(T,L,Rows).

row_AdjM(_,[ ],[ ]).
row_AdjM(X,[Y|Ys],[C|Cs]) :-
    (   graph(X,Y)
     -> C = 1
     ;  C = 0
    ),
    row_AdjM(X,Ys,Cs).

Если подразумевается неориентированный граф, товызов graph(X,Y) должен быть заменен альтернативным ( graph(X,Y); graph(Y,X) ), который позволяет рассматривать ребро в любом направлении.

...