Graphs, Recursion
Graphs are like trees, except the relationships can be either directed or non-directed and they can contain loops (“cycles”). A tree is a “directed, acyclical graph”—arrows go in one direction and there aren’t cycles.
Graphs are often used to model relationships between things. Here’s a graph of two groups of friends:
We’ve written some code for each node in this graph, as well as a class for the graph itself. There are useful functions for creating the graph, adding people to it, and setting friendships in it.
There is a PersonNode class for each person:
class PersonNode(object):
"""A node in a graph representing a person.
This is created with a name and, optionally, a list of adjacent nodes.
"""
def __init__(self, name, adjacent=[]):
self.name = name
self.adjacent = set(adjacent)
def __repr__(self):
return "<PersonNode %s>" % self.name
You can create a person using it:
>>> frodo = PersonNode("Frodo")
(though you’ll typically create people using the FriendGraph.add_person method, below)
There’s also a FriendGraph class:
class FriendGraph(object):
"""Graph to keep track of social connections."""
def __init__(self):
"""Create an empty graph.
We keep a dictionary to map people's names -> nodes.
"""
self.nodes = {}
def add_person(self, name):
"""Add a person to our graph.
>>> f = FriendGraph()
>>> f.nodes
{}
>>> f.add_person("Dumbledore")
>>> f.nodes
{'Dumbledore': <PersonNode Dumbledore>}
"""
if name not in self.nodes:
# Be careful not to just add them a second time -- otherwise,
# if we accidentally added someone twice, we'd clear our their list
# of friends!
self.nodes[name] = PersonNode(name)
def set_friends(self, name, friend_names):
"""Set two people as friends.
This is reciprocal: so if Romeo is friends with Juliet, she's
friends with Romeo (our graph is "undirected").
>>> f = FriendGraph()
>>> f.add_person("Romeo")
>>> f.add_person("Juliet")
>>> f.set_friends("Romeo", ["Juliet"])
>>> f.nodes["Romeo"].adjacent
{<PersonNode Juliet>}
>>> f.nodes["Juliet"].adjacent
{<PersonNode Romeo>}
"""
person = self.nodes[name]
for friend_name in friend_names:
friend = self.nodes[friend_name]
# Since adjacent is a set, we don't care if we're adding duplicates ---
# it will only keep track of each relationship once. We do want to
# make sure that we're adding both directions for the relationship.
person.adjacent.add(friend)
friend.adjacent.add(person)
def are_connected(self, name1, name2):
"""Is this name1 friends with name2?"""
To make the friend graph pictured above:
>>> f = FriendGraph()
>>> f.add_person("Frodo")
>>> f.add_person("Sam")
>>> f.add_person("Gandalf")
>>> f.add_person("Merry")
>>> f.add_person("Pippin")
>>> f.add_person("Treebeard")
>>> f.add_person("Sauron")
>>> f.add_person("Dick Cheney")
>>> f.set_friends("Frodo", ["Sam", "Gandalf", "Merry", "Pippin"])
>>> f.set_friends("Sam", ["Merry", "Pippin", "Gandalf"])
>>> f.set_friends("Merry", ["Pippin", "Treebeard"])
>>> f.set_friends("Pippin", ["Treebeard"])
>>> f.set_friends("Sauron", ["Dick Cheney"])
The FriendGraph.are_connected method is unimplemented. It should be given two people’s names and should return True or False depending on whether they connect on the graph.
For example, since we specifically said Sam was a friend of Frodo’s, they should be connected:
>>> f.are_connected("Frodo", "Sam")
True
Our FriendGraph.set_friends method sets the reciprocal relationship automatically (this is an “undirected graph”), so Sam is also friends with Frodo:
>>> f.are_connected("Sam", "Frodo")
True
Sam isn’t friends with Treebeard—but we can find a connection (Sam → Frodo → {Merry or Pippin} → Treebeard)
>>> f.are_connected("Sam", "Treebeard")
True
Poor Sauron. He won’t be invited to Frodo’s tea party:;
>>> f.are_connected("Frodo", "Sauron")
False
Implement the FriendGraph.are_connected method.
Recursion and “seen”
A classic way to write this would be using recursion.
However, if you just recurse on all-friends-of-a-node, you can get stuck in a loop, since a friend-of-a-node will be friends with the first node, and you’ll keeping bouncing back and forth.
Can you think of a way to keep track of which nodes you’ve already visited? What kind of (built-in) data structure would be right for this?