Recursive connection

TrustyTony 0 Tallied Votes 1K Views Share

Based on thread http://www.daniweb.com/forums/thread323401.html, I did this recursive version for comparision. Thanks for posters of the thread!

from collections import defaultdict
data = ["Apollo 13, Kevin Bacon, Tom Hanks, Gary Sinise",
                "Hollow Man, Elisabeth Shue, Kevin Bacon, Josh Brolin",
                "A Few Good Men, Tom Cruise, Demi Moore, Jack Nicholson, Kevin Bacon",
                "One Crazy Summer, John Cusack, Demi Moore",
                "Da Vinci Code, Tom Hanks, Ian McKellen, Audrey Tautou"]
def connection(start,end, previous = set()):
    """ Find recursively connection without using previous between actors start and end"""
    if not previous:
        previous.add(start)
    common = in_movies[start] & in_movies[end] # directly in same movie
    if common:
        return  '\t%s was in %r with %s.' % (start, ', '.join(common), end)
    else:
        for title in in_movies[start]:  # all start actor's movie titles
             for actor in actors_in[title]- previous- set([start]):   # actors in this start actors film
                 res = connection(actor, end, previous | set([actor]))  
                 if res:
                     return  '\t%s was in %r with %s,\n%s' % (start, title, actor, res)


# a dictionary of titles --> actors
actors_in = defaultdict(set)
# a dictionary of actors --> movie titles
in_movies = defaultdict(set)
for movie_bio in data:
   info = (word.strip() for word in movie_bio.split(","))
   movie_name = next(info)
   for actor in info:   ## all actors in the movie
       actors_in[movie_name].add(actor)
       in_movies[actor].add(movie_name)


for pair in (("John Cusack", "Tom Hanks"),
             ('Audrey Tautou', 'Tom Cruise'),
             ('Elisabeth Shue', 'John Cusack'),
             ('Tom Cruise', 'Kevin Bacon'),
             ('John Cusack', 'Kevin Bacon'),
             ('Tom Cruise', 'Arnold Swartzenegger')
             ):
   print 'Connection between %s and %s:\n' % pair,connection(*pair)
   print
Gribouillis 1,391 Programming Explorer Team Colleague

And here is the code to create an image of the data, using the snippet http://www.daniweb.com/code/snippet323792.html

data = ["Apollo 13, Kevin Bacon, Tom Hanks, Gary Sinise",
        "Hollow Man, Elisabeth Shue, Kevin Bacon, Josh Brolin",
        "A Few Good Men, Tom Cruise, Demi Moore, Jack Nicholson, Kevin Bacon",
        "One Crazy Summer, John Cusack, Demi Moore",
        "Da Vinci Code, Tom Hanks, Ian McKellen, Audrey Tautou"]
                

from fastgraph import *
import webbrowser

def items():
    for line in data:
        line = [word.strip() for word in line.split(",")]
        for w in line[1:]:
            yield edge(line[0], w)
            
def label(word):
    return word

image = "actors.png"
graph(items(), label).draw(image, prog="dot") # or neato|dot|twopi|circo|fdp|nop
webbrowser.open(image)
TrustyTony 888 pyMod Team Colleague Featured Poster

Did version which does not do double jump

Connection between Tom Cruise and Ian McKellen:
    Tom Cruise was in 'A Few Good Men' with Demi Moore,
    Demi Moore was in 'A Few Good Men' with Kevin Bacon,
    Kevin Bacon was in 'Apollo 13' with Tom Hanks,
    Tom Hanks was in 'Da Vinci Code' with Ian McKellen.

in single movie by putting also movie titles in previous in the loop.

from collections import defaultdict
data = ["Apollo 13, Kevin Bacon, Tom Hanks, Gary Sinise",
                "Hollow Man, Elisabeth Shue, Kevin Bacon, Josh Brolin",
                "A Few Good Men, Tom Cruise, Demi Moore, Jack Nicholson, Kevin Bacon",
                "One Crazy Summer, John Cusack, Demi Moore",
                "Da Vinci Code, Tom Hanks, Ian McKellen, Audrey Tautou"]
def connection(start,end, previous = set()):
    """ Find recursively connection of between actors start and end without visiting previous"""
    if not previous:
        previous.add(start)
    common = in_movies[start] & in_movies[end] # directly in same movie
    if common:
        return  '\t%s was in %r with %s.' % (start, ', '.join(common), end)
    else:
        for title in in_movies[start] - previous:  # all start actor's movie titles
             for actor in actors_in[title]- previous- set([start]):   # actors in this start actors film
                 res = connection(actor, end, previous | set([actor]) | set([title]))  
                 if res:
                     return  '\t%s was in %r with %s,\n%s' % (start, title, actor, res)


# a dictionary of titles --> actors
actors_in = defaultdict(set)
# a dictionary of actors --> movie titles
in_movies = defaultdict(set)
for movie_bio in data:
   info = (word.strip() for word in movie_bio.split(","))
   movie_name = next(info)
   for actor in info:   ## all actors in the movie
       actors_in[movie_name].add(actor)
       in_movies[actor].add(movie_name)


for pair in (("John Cusack", "Tom Hanks"),
             ('Audrey Tautou', 'Tom Cruise'),
             ('Elisabeth Shue', 'Audrey Tautou'),
             ('Tom Cruise', 'Ian McKellen'), ## double jump fixed
             ('John Cusack', 'Kevin Bacon'),
             ('Tom Cruise', 'Arnold Swartzenegger')
             ):
   print 'Connection between %s and %s:\n' % pair, connection(*pair)
   print
TrustyTony 888 pyMod Team Colleague Featured Poster

One more thing, the previous parameter remembers values from previous calling, so must use the None pattern, runs also in Python3 by changing prints, recursion counter added and error for missing actors:

from collections import defaultdict
data = ["Apollo 13, Kevin Bacon, Tom Hanks, Gary Sinise",
        "Hollow Man, Elisabeth Shue, Kevin Bacon, Josh Brolin",
        "A Few Good Men, Tom Cruise, Demi Moore, Jack Nicholson, Kevin Bacon",
        "One Crazy Summer, John Cusack, Demi Moore",
        "Da Vinci Code, Tom Hanks, Ian McKellen, Audrey Tautou"]

def connection(start,end, previous = None):
    """ Find recursively connection of between actors start and end without visiting previous"""
    global counter
    if any(actor not in in_movies.keys() for actor in (start,end)):
        raise ValueError('Unknown actor error in function:\n\tconnection(%r, %r, %r)' % (start, end, previous))
    counter += 1
    if not previous:
        previous = set([start])
    common = in_movies[start] & in_movies[end] # directly in same movie
    if common:
        return  '\t%s was in %s with %s.' % (start, ', '.join(('%r' % c for c in common)), end)
    else:
        for title in in_movies[start] - previous:  # all start actor's movie titles
             for actor in actors_in[title]- previous- set([start]):   # actors in this start actors film
                 res = connection(actor, end, previous | set([actor]) | set([title]))  
                 if res:
                     return  '\t%s was in %r with %s,\n%s' % (start, title, actor, res)


# a dictionary of titles --> actors
actors_in = defaultdict(set)
# a dictionary of actors --> movie titles
in_movies = defaultdict(set)
for movie_bio in data:
   info = (word.strip() for word in movie_bio.split(","))
   movie_name = next(info)
   for actor in info:   ## all actors in the movie
       actors_in[movie_name].add(actor)
       in_movies[actor].add(movie_name)
print('Available actors are:\n\n%s' % sorted(in_movies.keys()))

for pair in (("John Cusack", "Tom Hanks"),
             ('Audrey Tautou', 'Tom Cruise'),
             ('Elisabeth Shue', 'Audrey Tautou'),
             ('Tom Cruise', 'Ian McKellen'),
             ('John Cusack', 'Kevin Bacon'),
             ('Tom Cruise', 'Arnold Swartzeneger')
             ):
   counter = 0
   print('Connection between %s and %s:\n' % pair, connection(*pair))
   print('Recursive calls required: %i\n' % counter)
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.