1

このアルゴリズムを Prolog でプログラムしたいのですが、まずグラフのリストから行列を作成する必要があります。私は以前にこれを行ったことがありますが（あなたの何人かの助けを借りて）、リストのリスト内に保存する方法がわかりません（プロローグの場合はこれが最善のアプローチだと思います）。そこから続けられると思います (各アルゴリズムにトリプル 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.
4

1 に答える 1

2

Your previous question Adjacency Matrix in prolog dealt with the visual display (row over row) of the adjacency matrix of a graph. Here we address how to realize/represent the adjacency matrix as a Prolog term. In particular we will adopt as given the allnodes/1 predicate shown above as a means of getting a list of all nodes.

Prolog lacks any native "matrix" data type, so the approach taken here will be to use a list of lists to represent the adjacency matrix. Entries are organized by "row" in 0's and 1's that denote the adjacency of the node corresponding to a row with that node corresponding to a column.

Looking at your example graph/2 facts, I see that you've included one self-edge (from a to a). I'm not sure if you intend the graph to be directed or undirected, so I'll assume a directed graph was intended and note where a small change would be needed if otherwise an undirected graph was meant.

There is a "design pattern" here that defines a list by applying a rule to each item in a list. Here we do this one way to construct each row of the "matrix" and also (taking that as our rule) to construct the whole list of lists.

/* 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).

If an undirected graph were meant, then the call to graph(X,Y) should be replaced with an alternative ( graph(X,Y); graph(Y,X) ) that allows an edge to be considered in either direction.

于 2011-05-06T12:44:42.073 に答える