ASSIGNMENT 2: “SIX DEGREES OF SEPARATION: NOT SUCH A SMALL WORLD”
You have heard of the “six degrees of separation” experiment and decided to test it by yourself. Your
plan is simple: choose two people at random, Alice and Bob, and a secret word. Ask Alice to go on their
favourite social media, Touhiter , and post that message to all their followers, asking them to retouhit
it, with the same instructions.
Then wait until Bob gets the message and ask them how many retouhits it took. (Of course, once is not
enough, so you will have to repeat the experiment a few times to build confidence.)
In this assignment, you will implement and simulate this. There is an underlying (directed) graph with
400 million vertices: you are given the following access to each user (represented as a vertex; you do not
have to implement this):
- add_follower(Vertex): Adds a follower to the current user.
- get_followers(): Returns a list of all the followers connected to the Vertex.
- get_username(): Returns the (guaranteed unique) username of the user.
Your goal is to implement a BFS to perform the experiment, starting at Alice (a starting vertex provided
to you as input) and stopping when Bob (another node provided to you) is reached. Unfortunately, you
just cannot afford to use too much memory, definitely not for a data structure of size 400,000,000. You
are OK with some small probability of error, though, so you will have to implement a Bloom filter (class
BloomFilter) first and modify the BFS algorithm seen it class to use it, by implementing the Graph’s
BFS method:
bfs(self, start: Vertex, end: Vertex, bloom_filter: BloomFilter)
Note that you do not have to implement the class Vertex, and do not have to create your own hash
functions. They will be provided to your code during the tests! You also do not have to specify the
number of bits BITS and the number of hash functions m, this will also be passed by your code during
the test (though, of course, for your own testing, you might want to use the settings found in question
e). of the written part of the assignment, for instance).