代写data程序、代写C++，Python程序-代写Python编程

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).