Exercice sur les graphes en prolog

Bonjour. J’ai besoin d’aide pour un exercice. D’abord, je pense n’avoir pas bien compris l’énoncer. Voilà l’énoncé :

Bravo, vous venez d’être embauché(e) comme détective à l’université. Votre tâche est de coffrer sans pitié les bandes d’enseignants et étudiants corrompus. L’avantage, c’est que suivant la structure de la bande, il peut suffire de capturer un petit groupe de personnes pour aussi embarquer tout le reste, par effet «avalanche». Cependant, votre carrière débute seulement et vous risquez d’avoir de nombreux groupes de personnes malhonnêtes à mettre derrière les barreaux. Aussi aimeriez vous avoir un programme qui fasse la sale besogne à votre place. Heureusement, vous avez suivi un cours de méthodes discrètes. Vous pouvez donc modéliser ces mafias comme suit. Appelons M un ensemble de personnes mal intentionnées. Afin de capturer la structure du groupe on va introduire une relation binaire A( comme «Avalanche» ) qui associe deux personnes p1,p2 de M.On notera p1Ap2 pour dire «si on attrape p1, p2 tombe aussi». Attention! A n’est pas symétrique (les lois des malfrats sont parfois impénétrables). Les énigmes à résoudre sont les suivantes:

  1. Etant donné (M,A) et F ⊆ M, déterminer toutes les personnes que l’on capturera par la relation A partant de F.

  2. Pour une paire (M,A) donnée, trouver les groupes de personnes minimaux par inclusion qui permettent de capturer tout le monde. Autrement dit, on veut trouver les plus petits F dont la réponse serait M dans la question précédente.

  3. Calculer tous les ensembles de personnes «capturables», c’est-à-dire les F ⊆ M qui ne permettent pas d’embarquer d’autres personnes que celles de F. Autrement dit, on cherche les F ⊆ M pour lesquels la première question renvoie F.

Figure 2 text. Click triangle to expand

Votre premiere affaire concerne 5 personnes: Vincent, Aurelie, Lucas, Oscar, Yannick. On pose donc M = {v,a,l,o,y}. La relation A est illustree dans la Figure 2. Une paire (M,A) peut etre representee par un graphe dirige ou M sont les sommets et un arc(u,v) signifie uAv. Par example dans la figure, on a aAo, c’est-a-dire <Si Aurelie tombe, Oscar aussi. > Quand on choisit F = {l,y} et qu’on suit tous les chemins possibles (en vert), on capture au final {l,y,v,o} mais pas a. Un ensemble qui permetter de capture tout le monde est par exaemple f = {a,y}. Il est in plus minimial car on ne peut ni recuperer y par a, ni a par y ; on ne peut enlever ni l’un ni l’autre de F .

Dans le cas de l’exemple j’ai fais ça :

arc(a, o).
arc(a, l).
arc(l, v).
arc(v, l).
arc(y, v).
arc(y, o).

successeur(X, Y) :- arc(X, Y).

Le predicat successeur permet de repondre aux deux premières questions. Mais par exemple pour la première question F = {a, y}, il faut faire successeur(a, X) puis successeur(y, X) pour trouver toutes les solutions. Pour la deuxième question il suffit de mettre le paramètre inconni en première position . Mais c’est trop facile pour ètre la solution voulue. Mon objectif est d’écir un prédicat qui me retournerit la liste des solutions pour chacunes des 2 premières questions.
Merci d’avance…

For me the page is in French but my native language is English and I am using Chrome browser. The normal way for me to translate the page is to right click on part of the the page and choose translate to English. However upon doing so for this page I receive an error that the page can not be translated. Are others also having the same problem?

I can translate it by cutting and pasting into Google translate.

Also I am surprised that Discourse is also not automatically translating the page for me, but that is another topic.

I do want to thank AdNana for posting the exercise as given in the original language. While that might seem odd to others, I have learned from helping others with exercise problems that if the entire problem is given in the native language that I can better understand that problem if the automatic translation makes a mistake and I can manually adjust it. :smiley:

I can write in English.

arc(a, o).
arc(a, l).
arc(l, v).
arc(v, l).
arc(y, v).
arc(y, o).

conc([], B, B).
conc([T|R], B, [T|Q]) :- conc(R, B, Q).

addHead(D, [D], []).
addHead(D, [D|P], [T|R]) :- conc([T|R], [], P).

successeur(X, Y) :- arc(X, Y).
suivant([X], Z) :- arc(X, Y),
    addHead(Y, Z, _),!.
suivant([X|R], Y) :- suivant([X], Z),
    suivant(R, T),
    conc(Z, T, Y).

The problem is that suivant([a, y], X). returns [o, v], because arc(X, Y) just takes the first solution and that’s why the list is not complete .
I am sorry the original exercise was in French.

Thanks, that is appreciated. During the discussion about an exercise I do prefer English, but would help regardless of original language as long as I can translate to English.

I have translated the exercise and am now reading it; give me a few minutes.

No problem. Thanks.

Since this is an exercise for learning I will not give you the answers, but give you some help.

The keyword that will help you find what you seek is transitive closure

This is a good place to start and in particular pay attention to

prerequisite (X, Y) :- prereq(X, Y).
prerequisite (X, Y) :- prereq(X, Z), prerequisite(Z, Y).


One you understand how transitive closure works and can code it in Prolog and have successfully solved the exercise then take a look at the SWI-Prolog predicate transitive_closure/2, Do not use that to solve your problem as it will not help understand how to write code for transitive closure; it can be used to check your work though, but using it might cause you more confusion than help so I would avoid it until you are sure you understand how to write and use transitive closure on your own.

Also if you query for transitive closure here you will run into post about tabling, again avoid these as they are making use of an advanced topic not meant for a beginner.

Lastly the code given above has problems as noted in

“The Craft of Prolog” by Richard A. O` Keefe (WorldCat)
Section: 5.4 The problem of Transitive Closure

but again read that after you complete your exercises as it too will cause you confusion until you understand how to code and use transitive closure.

There is no need to say sorry for the language the exercise is given. Do you see those that post exercises in English saying sorry it is written in English?

I understand the notion of transitive closure even if I do not yet know how to code it in prolog. But to answers to the first and second questions of the exercise, I think that I dont need to use transitive closure. I did this :

arc(a, o).
arc(a, l).
arc(l, v).
arc(v, l).
arc(y, v).
arc(y, o).

conc([], B, B).
conc([T|R], B, [T|Q]) :- conc(R, B, Q).

addHead(D, [D], []).
addHead(D, [D|P], [T|R]) :- conc([T|R], [], P).

successeur(X, Y) :- arc(X, Y).
suivant([X], Z) :- arc(X, Y),
    addHead(Y, Z, _),!.
suivant([X|R], Y) :- suivant([X], Z),
    suivant(R, T),
    conc(Z, T, Y).

When posting code it also helps if you give example queries of how to use it. Sometimes when helping others the problem is not the code but the way they write the query. So by default when I add a code example I also try to give a few query examples to show how to, and how not to use the code.

I am looking at your code now with regards to answer the exercise parts 1 and 2, but have to guess as to what query you used. :smiley:

e.g.

?- suivant([a],Y).
Y = [o].

?- suivant([l],Y).
Y = [v].

?- suivant([v],Y).
Y = [l].

?- suivant([y],Y).
Y = [v].

?- suivant([o],Y).
Could not reenable global-stack
Could not reenable global-stack
Could not reenable global-stack
Could not reenable global-stack
Could not reenable global-stack
Could not reenable global-stack
Could not reenable global-stack
Could not reenable global-stack
Could not reenable global-stack
Could not reenable global-stack
Could not reenable global-stack
Could not reenable global-stack
Could not reenable global-stack
Could not reenable global-stack
Could not reenable local-stack
Could not reenable global-stack
Could not reenable local-stack
Could not reenable global-stack
Could not reenable local-stack
ERROR: Out of global-stack.
ERROR: No room for exception term.  Aborting.
Could not reenable global-stack
Could not reenable local-stack
ERROR: Out of global-stack.
ERROR: No room for exception term.  Aborting.
Could not reenable global-stack
Could not reenable local-stack
Could not reenable global-stack
Could not reenable global-stack
Could not reenable global-stack
Could not reenable global-stack
Could not reenable global-stack
Could not reenable global-stack
Could not reenable global-stack
Could not reenable global-stack
% Execution Aborted

arc(X, Y) defined a direct path from X to Y.
I want suivant(X, Y) must ddetermine all the people captured by the Relation A from F.
For example suivant([y, l], X) returns X = [l, y, v, o].
But in my case suivant([l, y], X). returns [v, v], because arc(X, Y) just takes the first solution and that’s why the list is not complete .

The first part of the problem is to get next related node in the graph, this can be done using

suivant_2(X, Y) :- arc(X, Y).
suivant_2(X, Y) :- arc(X, Z), suivant_2(Z, Y).

Example queries

?- suivant_2(a,R).
R = o .

?- suivant_2(l,R).
R = v ;
R = l ;
R = v ;
R = l ;
R = v ;
...


?- suivant_2(v,R).
R = l .

?- suivant_2(y,R).
R = v ;
R = o ;
R = l ;
R = v ;
R = l ;
R = v ;
...

Obviously there needs to be a change to stop the back and forth between l and v but that is easy to fix, e.g. member/2. Yes that means the code now needs to capture the values into a list but you learned that in the previous exercise.

Once you have valid results, then collect them into a list with something from Finding all Solutions to a Goal

suivant_2(X, Y, [X, Y]) :- arc(X, Y).
suivant_2(X, Y, [X, Y|T]) :- arc(X, Z), suivant_2(Z, Y, T),
X /== Y.

? - suivant_2(y, X, Y).
X = o, Y = [y, o]
X = v, Y = [y, v]

it is not yet completely fair. The ideal would be to have in return [y, o, v].

This page may help. I am looking at it but it doesn’t look correct for this exact problem so I am creating unit test to check it out.

Okay, I’m going to try on my side, too.

Here are the test cases that I believe are valid for part 1 of the exercise

:- begin_tests(part_1).

test(1) :-
    suivant(a,Result),
    assertion( Result == [a,l,o,v]).

test(2) :-
    suivant(o,Result),
    assertion( Result == [o]).

test(3) :-
    suivant(l,Result),
    assertion( Result == [l,v]).

test(4) :-
    suivant(v,Result),
    assertion( Result == [l,v]).

test(5) :-
    suivant(y,Result),
    assertion( Result == [l,o,v,y]).

:- end_tests(part_1).

Following but hidden is suivant/2 that pass the test cases. You should not look at the hidden code unless you are really stuck, but it is here to see another way to solve part 1. I did not spend time to simplify it but it can probably be simplified but doing so would make it more confusing for beginners.

suivant/2. Click triangle to expand.
suivant(X,Sorted_nodes) :-
    findall(Path,suivant(X,[X],Path),Paths),
    flatten(Paths,Nodes),
    list_to_set(Nodes,Unique_nodes),
    sort(Unique_nodes,Sorted_nodes).

suivant(X,L,R) :-
    arc(X,Y),
    \+ member(Y,L),
    suivant(Y,[Y|L],R).
suivant(_,R,R).

To run the test just requires running make/0 from the top level, e.g.

?- make.
% c:/users/eric/documents/projects/prolog/swi-discourse_024 compiled 0.00 sec, -12 clauses
% PL-Unit: exercise_1  done
% PL-Unit: part_1 ..... done
% All 5 tests passed
true.

I’ve redefined my arches.

arcs(a, [l, o]).
arcs(l, [v]).
arcs(v, [l]).
arcs(y, [o, v]).

transform(X, Y) is true if Y is the set got
from the list X , keeping the order

supprime_All(X,L,R):- delete(L,X,R).
transform([],[]).
transform([X|L], [X|R]):-
supprime_All(X,L,Z),
transform(Z,R).

union (X, Y, Z) is true if Z is the union of sets X and Y
union([], B, B).

union([T|R], B, Y) :- union(R, B, Q),
transform([T|Q], Y).

And then I just write these two predicates

suivant_2([X], [X|Y]) :- arcs(X, Y).
test([], []).
test([T|R], Z) :- suivant_2([T], Y),
test(R, E),
union(Y, E, Z).

? - test([l, y], R) R =

Sorry, my message was not complete.

? - test([l, y], R) R = [l, v, y, o]
?- test([a, y], R) R = [a, l, o, y, u]
?- test([a]) R = [a, l, o]
? - test([o]) R = [o]
? - test([l]) R = [l, v]
? - test([v]) R = [v, l]
?- test([y]) R = [o, v, ]

I know your code works, but I have to admit I don’t understand it very well. The version I just posted works almost well. Except that when he finds a new knot he does not determine the knots that can be found thanks to this new knot. That’s why test([y]) and test([a]) don’t return the full list.

Let me see if I understand your exercise correctly, and then I will offer some suggestions.

You are given a set of arc/2 facts, which form a directed graph. The problem you are trying to solve is “given a start point (one of a, l, v, y, o), list all the successors”. For example, here are all the successors of y with paths qui suivent la structure des arcs of length ≤ 4, and the proof for each (lost of connected arcs):

y->v:[arc(y,v)]
y->o:[arc(y,o)]
y->l:[arc(y,v),arc(v,l)]
y->v:[arc(y,v),arc(v,l),arc(l,v)]  % has a cycle
y->l:[arc(y,v),arc(v,l),arc(l,v),arc(v,l)] % has a cycle

You can generate these successor lists with length ≤ 4 as follows:

successor(P, Q, [arc(P,Q)]) :- arc(P, Q).
successor(P, R, [arc(P,Q),arc(Q,R)]) :- arc(P, Q), arc(Q, R).
successor(P, S, [arc(P,Q),arc(Q,R),arc(R,S)]) :- arc(P, Q), arc(Q, R), arc(R, S).
successor(P, T, [arc(P,Q),arc(Q,R),arc(R,S),arc(S,T)]) :- arc(P, Q), arc(Q, R), arc(R, S), arc(S, T).
% etc. 

and list all the successors (with paths of length ≤ 4) by:

?- forall(successor(A, B, Arcs), writeln(A->B:Arcs)).
a->o:[arc(a,o)]
a->l:[arc(a,l)]
l->v:[arc(l,v)]
v->l:[arc(v,l)]
y->v:[arc(y,v)]
y->o:[arc(y,o)]
a->v:[arc(a,l),arc(l,v)]
l->l:[arc(l,v),arc(v,l)]
v->v:[arc(v,l),arc(l,v)]                                                                                                
y->l:[arc(y,v),arc(v,l)]
a->l:[arc(a,l),arc(l,v),arc(v,l)]
l->v:[arc(l,v),arc(v,l),arc(l,v)]
v->l:[arc(v,l),arc(l,v),arc(v,l)]
y->v:[arc(y,v),arc(v,l),arc(l,v)]
a->v:[arc(a,l),arc(l,v),arc(v,l),arc(l,v)]
l->l:[arc(l,v),arc(v,l),arc(l,v),arc(v,l)]
v->v:[arc(v,l),arc(l,v),arc(v,l),arc(l,v)]
y->l:[arc(y,v),arc(v,l),arc(l,v),arc(v,l)]

Except you want a general solution that allows any number of intermediate steps, and you don’t want any cycles in the list of arcs (e.g., do not allow solution paths such as [arc(v,l),arc(l,v)] or [arc(a,l),arc(l,v),arc(v,l),arc(l,v)].

If this is a correct understanding, then the next steps are:

  1. Generalize successor/3 for paths of any length.
  2. Prevent cycles in the paths.

Before I go any further, I wish to confirm that I understand your exercise correctly.

Yes. You understand that. However, I would also like to generate all possible knots from a list. In this case, for example, we would leave [a] or [a], or y, or from [a, l, y].
I can show you the original exercise; but it’s in french.