Checking if 2 people are connected via friends

Question

Every sublist means that they are friends and now I want to create a function def is_connected_via_friendships_with that checks if they are connected via friendships with another person. For example Marie is friends with Lucas. She is friends with Peter and Peter with Julie. So the function needs to return True for Marie and Julie. Also note that I can't use import for this. Thank you in advance.

network = {'friendships' :[['Marie', 'Lucas'], ['Lucas', 'Patsy'], ['Emma', 'Lucas'], ['Emma', 'Kevin'], ['Peter', 'Emma'], ['Peter', 'Lucas'], ['Peter', 'Julie'], ['Suzy', 'Tobias']]}
print (is_connected_via_friendships_with(network, 'Marie', 'Julie')) # true
print (is_connected_via_friendships_with(network, 'Julie', 'Tobias')) # false
print (is_connected_via_friendships_with(network, 'Julie', 'Frank'))  # false

What all have you tried? You might want to consider adding the code that you have tried ! — Akash Basudevan, Dec 09 '19 at 19:53
The problem is that it's part of a bigger code and use other functions. I know how to do it if they have a mutual friend but I really can't find a proper way to do it for this one. — matens, Dec 09 '19 at 20:00
You can use multiple ways to solve this, i've added an disjoint set solution ! — Akash Basudevan, Dec 10 '19 at 07:31

Akash Basudevan · Answer 1 · 2019-12-09T20:57:08.900

You basically have to find if two friends lie in the same connected components of the graph. Multiple ways to check if 2 nodes lie in the same connected component. You can use Disjoint sets for an optimized implementation of this question. The Disjoint set implementation used from Here

The Code would be as follows :

class DisjointSet:
    def __init__(self, vertices, parent):
        self.vertices = vertices
        self.parent = parent

    def find(self, item):
        if self.parent[item] == item:
            return item
        else:
            return self.find(self.parent[item])

    def union(self, set1, set2):
        root1 = self.find(set1)
        root2 = self.find(set2)
        self.parent[root1] = root2

    def is_in_same_set(self, fa, fb):
        return self.find(fb) == self.find(fa)

def get_vertices(network):
    myset = set()
    for a,b in network['friendships']:
        myset.add(a)
        myset.add(b)
    return list(myset)


def is_connected_via_friendships_with(network, fa,fb):
    return network.is_in_same_set(fa,fb)

def main():

    network = {'friendships' :[['Marie', 'Lucas'], ['Lucas', 'Patsy'], ['Emma','Lucas'], ['Emma', 'Kevin'], ['Peter', 'Emma'], ['Peter', 'Lucas'], ['Peter', 'Julie'],     ['Suzy', 'Tobias']]}

    vertices = get_vertices(network)
    parent = {}

    for v in vertices:
        parent[v] = v

    ds = DisjointSet(vertices, parent)

    for a,b in network['friendships']:
        ds.union(a,b)

    print(is_connected_via_friendships_with(ds, 'Marie', 'Julie'))
    print(is_connected_via_friendships_with(ds, 'Peter', 'Suzy'))
main()

The Output being:

True
False

score 1 · Answer 2 · answered Dec 09 '19 at 20:48

This is a classic connected component problem. Since friendships are bidirectional, it is more efficient to convert the list of sub-lists to a set of hashable frozensets as a candidate pool so that for each starting vertex you can find the connected component by iterating through the candidates in the set of frozensets to find a frozenset that intersects with the current component set and remove it from the pool of candidates, until there is no more candidate in the pool:

pool = set(map(frozenset, network['friendships']))
groups = []
while pool:
    groups.append(set(pool.pop()))
    while True:
        for candidate in pool:
            if groups[-1] & candidate:
                groups[-1] |= candidate
                pool.remove(candidate)
                break
        else:
            break

groups would become:

[{'Patsy', 'Emma', 'Peter', 'Marie', 'Julie', 'Kevin', 'Lucas'}, {'Suzy', 'Tobias'}]

It is then trivial to convert the list of sets to a dict of sets with each name as the key for efficient lookups:

connected = {name: group for group in groups for name in group}
def is_connected_via_friendships_with(name1, name2):
    return name2 in connected.get(name1, ())

so that:

print(is_connected_via_friendships_with('Marie', 'Julie'))
print(is_connected_via_friendships_with('Julie', 'Tobias'))
print(is_connected_via_friendships_with('Julie', 'Frank'))

outputs:

True
False
False

How do you write this without using `break `? It's bad practive they say and I can't use this. — matens, Dec 10 '19 at 19:59
Not sure who "they" are but `break` is a great tool to make your code clean and efficient. It is never a bad practice. If you don't use it you would have to use a Boolean flag instead to signal when to end a loop, making the code much messier. — blhsing, Dec 10 '19 at 20:01
My university says so. It's stupid I can't use it because I've read a lot about how it's very useful — matens, Dec 10 '19 at 20:04

Checking if 2 people are connected via friends

2 Answers2