Working with graphs - Kevin Bacon game

[MRAB]

On 2019-01-09 14:09, Josip Skako wrote:
> I get it now, basically you are accessing class atributes with "self.something", thank You.
> 
> So now I get this:
> 
> "['Apollo 13 (1995)', 'Bill Paxton', 'Tom Hanks', 'Kevin Bacon\n', 'Begyndte ombord, Det (1937)', 'Aage Schmidt', 'Valso Holm\n', 'Bersaglio mobile (1967)', 'Dana Young', 'Bebe Drake\n', 'Bezottsovshchina (1976)', 'Yelena Maksimova', 'Lev Prygunov\n', 'Dark, The (1979)', 'Angelo Rossitto', 'William Devane\n', 'Death to Smoochy (2002)',..."
> 
I notice that some of the strings end with '\n'. The best way to deal 
with that is to use .rstrip() on the line before splitting it.

> That is great.
> What would be the best way now to find shortest path between ex. Tom Hanks and ex. William Devane?
> 
> I should get something like: https://oracleofbacon.org/
> 
> Should I insert this data into networkx somehow, would it be easier?
> 
No, I wouldn't bother.

You have 2 dicts:

     person_dict: the key is a person and the value is a list of films 
that contained that person.

     film_dict: the key is a film and the value is a list of persons in 
that film.

You're looking for a list of links. Let's call that a "chain".

You're working breadth-first, so you have a multiple chains, i.e. a list 
of lists.

Start with a person.

Initially you have a list that contains a list that in turn contains the 
starting person.

[[person]]

For each chain, look in person_dict for all of the films that the last 
person is in and duplicate the chain however many times you need, 
putting a film at the end of each.

[[person, film], [person, film], ...]

Then, for each chain, look in film_dict for all of the people who are in 
the last film and duplicate the chain however many times you need, 
putting a person at the end of each.

[[person, film, person], [person, film, person], ...]

Repeat until the last person in a chain is the target person (success!) 
or there are no chains remaining (no chain possible with the available 
information).

Also, remove cycles, e.g. ['Bill Paxton', 'Apollo 13', 'Tom Hanks', 
'Apollo 13', 'Bill Paxton'].