Solutions for Session 8

Graphs

1. all_parents(Graph,Node,ParentList) :-
   	findall(Parent,member(Parent/Node,Graph),ParentList).
   

   Some queries:

   ?- all_parents([a/c,c/d,c/e,b/d,d/e],d,Parents).
   Parents = [c, b] 
   Yes
   ?- all_parents([a/c,c/d,c/e,b/d,d/e],e,Parents).
   Parents = [c, d] 
   Yes
   ?- all_parents([a/c,c/d,c/e,b/d,d/e],b,Parents).
   Parents = []
   

2. Given a graph and a node, the predicate p writes all the parents of that node to the screen followed by 'end'.

   ?- p([a/c,c/d,c/e,b/d,d/e],b).
   end
   Yes
   
   ?- p([a/c,c/d,c/e,b/d,d/e],d).
   c
   b
   end
   Yes
   
   ?- p([a/c,c/d,c/e,b/d,d/e],e).
   c
   d
   end
   Yes
   

3. shortest_path(From,To,Graph,ShortestPath):-
           findall(Path,find_path_2(From,To,Graph,Path), Paths),
           Paths = [FirstPath|OtherPaths], % fails if no path exists
           length(FirstPath,L),
           find_shortest(OtherPaths,FirstPath,L,ShortestPath).
   
   % Find shortest path given all paths using accumulating parameters:
   find_shortest([],ShortestPath,_,ShortestPath).
   
   find_shortest([Path1|Paths],_CurrentShortestPath,CurrentLength,ShortestPath):-
           length(Path1,Length1), Length1 < CurrentLength, !,
           find_shortest(Paths,Path1,Length1,ShortestPath).
   
   find_shortest([_|Paths],CurrentShortestPath,CurrentLength,ShortestPath):-
           find_shortest(Paths,CurrentShortestPath,CurrentLength,ShortestPath).
   

Mixing chemical products

advice(List):-
        findall(Reactval,(reacts(A,B,Reactval),member(A,List),member(B,List)),ReactList),
	list_sum(ReactList,Sum,0),
	message(Sum,Text),
	write(Text),nl.
	
	
list_sum([],Result,Result).
list_sum([H|T],Result,Acc):-
        NAcc is H+Acc,        
	list_sum(T,Result,NAcc).

The classification problem

• Hamming distance:

  hamming_dist(List1,List2,Distance) :-
  	hamming_acc(List1,List2,0,Distance).
  
  hamming_acc([],[],Distance,Distance).
  
  hamming_acc([X1|List1],[X2|List2],Current,Distance) :-
  	New is Current+abs(X1-X2),
  	hamming_acc(List1,List2,New,Distance).
  

  Euclidean distance:

  euclidean_dist(List1,List2,Distance) :-
  	euclidean_acc(List1,List2,0,SquaredDistance),
  	Distance is sqrt(SquaredDistance).
  
  euclidean_acc([],[],Distance,Distance).
  
  euclidean_acc([X1|List1],[X2|List2],Current,SquaredDistance) :-
  	New is Current+(X1-X2)**2, % (X1-X2)**2 means X1-X2 squared
  	euclidean_acc(List1,List2,New,SquaredDistance).
  

• classify(List,PredictedClass):-   % The class is the farmer who the bottle is from
  	findall(Distance1/Class1,(traindata(List1,Class1),hamming_dist(List,List1,Distance1)),AllDistances),
  	sort(AllDistances,SortedDistances),
  	first_n_elements(5,SortedDistances,FiveMostSimilar),
  	find_majority_class(FiveMostSimilar,PredictedClass).
  

  Note that we have used the predicate sort/2 to sort a list. This predicate is predefined in SWI. In session 9, we will see how to implement sort ourselves.

  first_n_elements(0,_,[]):-!.
  first_n_elements(_,[],[]):-!.
  first_n_elements(N,[_Distance/Class|Tail],[Class|Tail1]):-
  	N1 is N - 1,
  	first_n_elements(N1,Tail,Tail1).
  
  
  find_majority_class(List,MajorityClass):-
  	frequence(List,FrequencyTable),
  	most_frequent_element(FrequencyTable,MajorityClass).
  

  The definition of frequence/2 is copied from session 6:

  frequence(List, Table):-
          frequence_acc(List, Table, []).
  
  frequence_acc([], Table, Table).
  frequence_acc([El|Tail], Table, Acc):-
          member_remove(occur(El, Numb), Acc, Remainder),!,
          Numb1 is Numb +1,
          frequence_acc(Tail, Table, [occur(El, Numb1)|Remainder]).
  frequence_acc([El|Tail], Table, Acc):-
          frequence_acc(Tail, Table, [occur(El, 1)|Acc]).
  
  % member_remove/3 checks membership and removes member 
  member_remove(El , [El|Tail], Tail).
  member_remove(El1, [El2|Tail1], [El2| Tail2]):-
          member_remove(El1, Tail1, Tail2).
  

  Finally the definition of most_frequent_element/2:

  most_frequent_element([occur(Class1,Count1)|RestFrequencyTable],MajorityClass) :-
  	most_frequent_acc(RestFrequencyTable,Class1,Count1,MajorityClass).
  
  most_frequent_acc([],MajorityClass,_,MajorityClass) :- !.
  
  most_frequent_acc([occur(Class,Count)|RestFrequencyTable],_CurrentMajorityClass,CurrentMajorityCount,MajorityClass) :-
  	Count>CurrentMajorityCount, !,
  	most_frequent_acc(RestFrequencyTable,Class,Count,MajorityClass).
  
  most_frequent_acc([_|RestFrequencyTable],CurrentMajorityClass,CurrentMajorityCount,MajorityClass) :-
  	most_frequent_acc(RestFrequencyTable,CurrentMajorityClass,CurrentMajorityCount,MajorityClass).
  

• compute_accuracy(Accuracy) :-
  	findall(List/RealClass,(testdata(BottleNb,List),testdata_class(BottleNb,RealClass)),TestBottles),
  	check_classifications(TestBottles,NbOfClassifications,NbOfCorrectClassifications),
  	Accuracy is NbOfCorrectClassifications/NbOfClassifications.
  
  
  check_classifications(TestBottles,NbOfClassifications,NbOfCorrectClassifications) :-
  	check_classifications_acc(TestBottles,0,NbOfClassifications,0,NbOfCorrectClassifications).
  
  check_classifications_acc([],NbOfClassifications,NbOfClassifications,NbOfCorrectClassifications,NbOfCorrectClassifications).
  
  check_classifications_acc([List1/RealClass1|TestBottles],Acc,NbOfClassifications,Acc_Correct,NbOfCorrectClassifications) :-
  	New_Acc is Acc+1,
  	check_one_classification(List1,RealClass1,Check1), New_Acc_Correct is Acc_Correct+Check1,
  	check_classifications_acc(TestBottles,New_Acc,NbOfClassifications,New_Acc_Correct,NbOfCorrectClassifications). 
  
  
  check_one_classification(List,RealClass,Check) :- % Check=1 for correct prediction, else Check=0
  	classify(List,PredictedClass),
  	(PredictedClass=RealClass -> Check is 1 ; Check is 0).
  

Extra list exercises

1. squareboard(B,Width):-
   	length(B,Width),
   	rows(B,Width).
   rows([],_).
   rows([A|Tail],Width):-
   	length(A,Width),
   	rows(Tail,Width).
   

2. validboard(B):-
   	length(B,8), % the number of rows should be 8
   	validrows(B).
   validrows([]).
   validrows([R|Tail]):-
   	length(R,8), % each row should have 8 elements
   	allmember(R,[b,w,o]), % each element should be b, w or o
   	validrows(Tail).
   allmember([],_).
   allmember([A|Tail],List):-
   	member(A,List),
   	allmember(Tail,List).
   

   Note that member/2 is not a built-in predicate. In SWI, however, it is automatically loaded at start-up. If you use another prolog engine, you might have to define member/2 yourself.