3
\$\begingroup\$

I have created a program but I feel the def common(friendships, person1, person2) function can be more efficient, if anyone has any good idea how I can improve it I would appreciate it.

from My_graph import Graph

def friends_of_friends(friendships, person):
    """Return the set of friends of the person's friends.
    Don't return people that are already friends of person.
    """
    assert person in friendships.nodes()

    result = set()
    people = friendships.nodes()
    for person1 in people:
        for person2 in people:
            # the () around the whole condition are necessary to
            # break the condition over multiple lines
            if (friendships.has_edge(person1, person2) and
                friendships.has_edge(person2, person) and
                not friendships.has_edge(person1, person) and
                person1 != person):
                result.add(person1)
    return result

def common(friendships, person1, person2):
    """Return the number of common friends of person1 and person2."""
    assert person1 != person2
    assert person1 in friendships.nodes()
    assert person2 in friendships.nodes()

    mutual = 0
    for person in friendships.nodes():
        if (friendships.has_edge(person, person1) and
            friendships.has_edge(person, person2)):
            mutual = mutual + 1
    return mutual

def suggested_friends(friendships, person):
    """Return a list of suggested people for person to befriend.

    Each suggestion is a friend of a friend of person but isn't person's friend.
    The suggestions are ordered from most to fewest mutual friends with person.
    """
    assert person in friendships.nodes()

    scored_suggestions = []
    for friend_of_friend in friends_of_friends(friendships, person):
        score = common(friendships, person, friend_of_friend)
        scored_suggestions.append((score, friend_of_friend))
    scored_suggestions.sort(reverse=True)
    suggestions = []
    for (score, suggestion) in scored_suggestions:
        suggestions.append(suggestion)
    return suggestions

class Graph:

    # Representation
    # --------------
    # We use the adjacency list representation, but with sets instead of lists.
    # The graph is a dictionary where each key is a node and
    # the corresponding value is the set of the node's neighbours.
    # The graph being undirected, each edge is represented twice.
    # For example, the dictionary {1: {2, 3}, 2: {1}, 3: {1}} represents a
    # graph with three nodes and two edges connecting node 1 with the other two.

    # Creator
    # -------

    def __init__(self):
        """Initialise the empty graph."""
        self.graph = dict()

    # Inspectors
    # ----------

    def has_node(self, node):
        """Return True if the graph contains the node, otherwise False."""
        return node in self.graph

    def has_edge(self, node1, node2):
        """Check if there's an edge between the two nodes.
        Return False if the edge or either node don't exist, otherwise True.
        """
        return self.has_node(node1) and node2 in self.graph[node1]

    def neighbours(self, node):
        """Return the set of neighbours of node.
        Assume the graph has the node.
        """
        assert self.has_node(node)

        # copy the set of neighbours, to prevent clients modifying it directly
        result = set()
        for neighbour in self.graph[node]:
            result.add(neighbour)
        return result

    def nodes(self):
        """Return the set of all nodes in the graph."""
        result = set()
        for node in self.graph:
            result.add(node)
        return result

    def edges(self):
        """Return the set of all edges in the graph.
        An edge is a tuple (node1, node2).
        Only one of (node1, node2) and (node2, node1) is included in the set.
        """
        result = set()
        for node1 in self.nodes():
            for node2 in self.nodes():
                if self.has_edge(node1, node2):
                    if (node2, node1) not in result:
                        result.add((node1, node2))
        return result

    def __eq__(self, other):
        """Implement == to check two graphs have the same nodes and edges."""
        nodes = self.nodes()
        if nodes != other.nodes():
            return False
        for node1 in nodes:
            for node2 in nodes:
                if self.has_edge(node1, node2) != other.has_edge(node1, node2):
                    return False
        return True

    # Breadth-first search
    # --------------------

    def bfs(self, start):
        """Do a breadth-first search of the graph, from the start node.
        Return a list of nodes in visited order, the first being start.
        Assume the start node exists.
        """
        assert self.has_node(start)

        # Initialise the list to be returned.
        visited = []
        # Keep the nodes yet to visit in another list, used as a queue.
        # Initially, only the start node is to be visited.
        to_visit = [start]
        # While there are nodes to be visited:
        while to_visit != []:
            # Visit the next node at the front of the queue.
            next_node = to_visit.pop(0)
            visited.append(next_node)
            # Look at its neighbours.
            for neighbour in self.neighbours(next_node):
                # Add node to the back of the queue if not already
                # visited or not already in the queue to be visited.
                if neighbour not in visited and neighbour not in to_visit:
                    to_visit.append(neighbour)
        return visited

    # Depth-first search
    # ------------------

    def dfs(self, start):
        """Do a depth-first search of the graph, from the start node.
        Return a list of nodes in visited order, the first being start.
        Assume the start node exists.
        """
        assert self.has_node(start)

        # Use the BFS algorithm, but keep nodes to visit in a stack.
        visited = []
        to_visit = [start]
        while to_visit != []:
            next_node = to_visit.pop()
            visited.append(next_node)
            for neighbour in self.neighbours(next_node):
                if neighbour not in visited and neighbour not in to_visit:
                    to_visit.append(neighbour)
        return visited


    # Modifiers
    # ---------

    def add_node(self, node):
        """Add the node to the graph.
        Do nothing if the graph already has the node.
        Assume the node is of an immutable type.
        """
        if not self.has_node(node):
            self.graph[node] = set()

    def add_edge(self, node1, node2):
        """Add to the graph an edge between the two nodes.
        Add any node that doesn't exist.
        Assume the two nodes are different and of an immutable type.
        """
        assert node1 != node2

        self.add_node(node1)
        self.add_node(node2)
        self.graph[node1].add(node2)
        self.graph[node2].add(node1)
\$\endgroup\$
  • \$\begingroup\$ It would help to add some sample code that uses the functions and Graph class. For example, create a sample friendships graph and call common(). \$\endgroup\$ – RootTwo May 7 at 22:00
3
\$\begingroup\$

Generally, if a function can't handle an exception, let the exception pass up the call stack in case a higher level can handle it. For example, don't assert that node is in the graph. Assume it is and try the operation. If the node isn't in the graph, an IndexError will be thrown. (Some people say "it's easier to ask forgiveness than get permission".)

Presuming that friendships is a Graph, and that person1 and person2 are nodes in the Graph, common() can be implemented using the neighbors() method and set operations:

def common(friendships, person1, person2):
    """Return the number of common friends of person1 and person2."""
    return friendships.neighbors(person1) & friendships.neighbors(person2)

A neighbors() and nodes() can be simplified:

def neighbors(self, node):
    """Return a copy of the set of neighbors of node.
    Assume the graph has the node.
    """
    return set(self.graph[node])

def nodes(self):
    """Return a set of all nodes in the graph."""
    return set(self.graph)

The doc-string suggests Graph is a non-directed graph, so edges() can be simplified:

def edges(self):
    """Return the set of all edges in the graph.
    An edge is a tuple (node1, node2).
    Only one of (node1, node2) and (node2, node1) is included in the set.
    """
    seen = set()
    result = set()
    for node1, neighbors in self.graph.items():
        result.union((node1, node2) for node2 in neighbors if node2 not in seen)
        seen.add(node1)

    return result
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ What if you could only change the common() function and nothing else to make it efficient? \$\endgroup\$ – Hassan May 8 at 10:20
  • \$\begingroup\$ @Hassan, the revised functions are independent of each other. So, the revised common() can be used without changing the other functions/methods. \$\endgroup\$ – RootTwo May 8 at 13:59
  • 1
    \$\begingroup\$ ok thank you mate \$\endgroup\$ – Hassan May 8 at 14:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.