From UBC Wiki

Degrees to Bacon

Authors: Wing Wai Danial Cheung, Andres Rama

What is the problem?

Kevin Bacon is the problem. More specifically, who his associates are. The Hollywood industry has had a knack of pairing many famous actors together, posing the question: how many degrees of separation are between one movie star and another? For our point of reference, we will be using Kevin Bacon compared with another star. The idea is that our program will list the chain of actor pairings starting from Kevin Bacon until we reach the other movie star in question.

What is the something extra?

Our program will show the path it took to get to Kevin Bacon.

What did we learn from doing this?

Our project was a success overall and managed to go beyond using Kevin Bacon as a reference point. Our program can take two celebrities and count the degrees of separation between them. We have also created an array that shows a path from one celebrity to the other by listing out the names of other people or stars that are associated with each other. The order of names specifies the degrees of separation and shows the path of relationships that ends at the name of the other desired celebrity. Our information was obtained by traversing a graph, which prolog handled pretty well. We were able to extract our results through recursion and a list of visited nodes.

Some of the troubles we ran into were incompatible formats. We noticed that some of the links in our rdf file obtained through LinkedDB were not formatted correctly. To solve this, we had to write a script in Python that collected our desired information and structured it into the correct format. This was the biggest hinderance in our project and one of the main reasons we chose not to do a natural language program. We also found that LinkedDB did not contain every celebrity and was formatted in such a way that we couldn't directly input the celebrity name, but the link to the profile.

There are many take-aways we gained from doing this project. Firstly, if things don't go your way, be flexible and carry-on. Whether it's faulty data or too much data, don't panic and find another solution. Secondly, being able to traverse through an undirected graph. One of the major problems we encountered was an infinite loop for unsuccessful cases. Thus we resorted to using an accumulator that built a history of nodes visited, and took advantage of the member/2 function. Lastly, an interesting look at Meta-Call Predicates. Out of curiosity, we went looking for other possible solutions to our infinite loop bug. We found the two Meta-Call predicates call_with_depth_limit/3 and call_with_inference_limit/3 that would stop the execution of our program if too many inferences were made or if the depth limit was exceeded. Even though we never took advantage of both of those, we learned that these could come in handy for testing future prolog projects.