Friends: Solution

class FriendGraph(object):   # ...
    def are_connected(self, name1, name2):
        """Is this name1 friends with name2?"""

        # START SOLUTION

        def _are_connected(node, name2, seen):
            """Recursive function to check if node connects w/person name.

            :seen: is a set of all nodes that have been visited.
            """

            # Use a DFS (depth-first search) to see if the nodes connect.
            # This recurses for each adjacent node of the passed-in node,
            # but it keeps track of nodes visited in a set, so it can avoid loops.

            if node.name == name2:
                # Yes, they're connected
                return True

            # Keep track of the fact that we've visited here
            seen.add(node)

            for n in node.adjacent:
                # Recursively check all friends of node

                if n in seen:
                    # We've already checked (or are mid-checking!) this node,
                    # so don't start a search again. Otherwise, this could
                    # loop forever in a cycle.
                    continue

                if _are_connected(n, name2, seen):
                    # We found a match -- get out of loop and return upward
                    return True

            # No match here (or deeper) -- so pass upward
            return False

        # Call recursive function, using node-of-name1 as a start,
        # looking for name2, and with a fresh, empty set for people-we've-seen.
        return _are_connected(self.nodes[name1], name2, set())