플로이드와 Warshall의 알고리즘 Prolog에서

Question

이 알고리즘을 Prolog에서 프로그래밍하고 싶습니다. 그리고 먼저 그래프 목록에서 행렬을 만들어야합니다. 나는 (여러분 중 몇몇의 도움을 받아) 전에 이것을했는데, 이제 목록의 목록에 그것을 저장하는 방법을 모른다 (나는 프롤로그의 경우에 가장 좋은 방법이라고 생각한다). 나는 거기에서 계속할 수 있다고 생각한다. (각각의 알고리듬에서 3 중 반복을 사용한다.) 프로그램의 논리는 나를 위해 어렵지는 않지만 데이터로 작업하는 방법입니다. 귀찮게하고 미리 감사드립니다.

내 행렬 생성기 :

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. 

Answer 1

이전 질문 Adjacency Matrix in prolog 그래프의 인접 행렬의 시각적 디스플레이 (행 위에 행) 처리. 여기에서는 인접성 매트릭스를 Prolog 용어로 실현/표현하는 방법에 대해 설명합니다. 특히 모든 노드의 목록을 가져 오는 수단으로 위에 표시된 allnodes/1 술어를 채택 할 것입니다.

프롤로그에는 원시 "매트릭스"데이터 유형이 없으므로 여기에서 수행 한 접근 방식은 목록 목록을 사용하여 인접성 매트릭스를 나타내는 것입니다. 항목은 열에 해당 노드가있는 행에 해당하는 노드의 인접성을 나타내는 0 및 1의 "행"으로 구성됩니다.

예 : 그래프/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))로 대체되어야한다.