Les algorithmes de Floyd et Warshall dans Prolog

Question

Je veux programmer ces algorithmes dans Prolog, et d'abord j'ai besoin de créer une matrice à partir d'une liste de graphes. Je l'ai fait avant (aussi avec l'aide de certains d'entre vous, les gars), mais maintenant je ne sais pas comment le stocker dans une liste de listes (ce qui je suppose que c'est la meilleure approche dans le cas de Prolog). Je pense que je peux être capable de continuer à partir de là (avec le triple pour boucle dans chacun des algorithmes). La logique du programme n'est pas difficile pour moi, mais comment travailler avec des données. Désolé d'être dérangé et merci d'avance!

Mon générateur de matrice:

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

Votre question précédente Adjacency Matrix in prolog traite l'affichage visuel (ligne sur ligne) de la matrice de contiguïté d'un graphique. Nous abordons ici comment réaliser/représenter la matrice d'adjacence en tant que terme Prolog. En particulier, nous allons adopter comme donné le prédicat allnodes/1 montré ci-dessus comme un moyen d'obtenir une liste de tous les nœuds. Prolog n'a pas de type de données "matrice" natif, donc l'approche adoptée ici sera d'utiliser une liste de listes pour représenter la matrice d'adjacence. Les entrées sont organisées par "ligne" en 0 et 1 qui désignent l'adjacence du nœud correspondant à une ligne avec ce nœud correspondant à une colonne.

En regardant votre exemple graph/2 faits, je vois que vous avez inclus un self-edge (de a à). Je ne suis pas sûr si vous avez l'intention que le graphique soit dirigé ou non orienté, donc je suppose qu'un graphique orienté était prévu et notez où un petit changement serait nécessaire si autrement un graphique non orienté était signifié.

Il existe un "motif de conception" qui définit une liste en appliquant une règle à chaque élément d'une liste. Nous faisons ici une façon de construire chaque rangée de la «matrice» et aussi (en prenant cela comme notre règle) pour construire la liste entière des listes.

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

Si un graphe non orienté étaient destinés, l'appel à graph(X,Y) doit être remplacé par une (graph(X,Y); graph(Y,X)) alternative qui permet un avantage à considérer dans les deux sens.