Python算法代写｜Comp2123 Assignment 4 Chocolate Couriers

这是一篇澳洲的python算法代写

<A screen blinks to life showing a Belgian chocolate shop.>

Good evening, Mr. Hunt.

Our chocolate shop is seeking to expand its operations and we need to share our top secret recipes with our next location. For this we have worked long and hard to set up a network of trusted couriers. However, our Swiss competitors are keen to discover the secret to our success and are trying to convince some couriers to let them take a peek at our recipes.

<The screen changes to show a map of red and blue dots connected by line segments.> We have marked our couriers on this map. The blue vertices are couriers we know we can trust, but the red ones are the ones we aren’t sure about. The edges show which couriers can communicate with which other couriers.

Your mission, if you choose to accept, is to:

Good luck, Mr. Hunt. The fate of the chocolate-loving world is in your hands.

This message will self-destruct in 5 seconds…

<A puff of smoke comes out of a nearby device, but by that time we’re long gone.>

Maintain a graph where each vertex stores a boolean value is_trusted indicating whether it is a trusted courier. You can assume that the initial graph is undirected and simple and your operations should ensure it stays that way.

Send Message

You must also support the can_send_message(s, t) function, which returns a path from s to t that includes at most 1 untrusted vertex if such a path exists, and none otherwise. You can assume that s and t are distinct trusted vertices.

A(trusted) – B(untrusted) – C(trusted) – D(untrusted) – E(trusted)

can_send_message(A, C) returns [A, B, C]

can_send_message(A, E) returns none

Check Security

Your graph must support the check_security(s,t) operation that returns a set of edges.

We define an untrusted edge as an edge connecting two untrusted vertices. A semi-trusted edge is an edge connecting a trusted to an untrusted vertex. When called, the check_security(s,t) operation returns the set S of semi-trusted edges such that removing any edge in S from the graph forces any s-t path to traverse an untrusted edge.

You can assume that s and t are distinct trusted vertices.

A(trusted) – B(untrusted)

C(trusted) D(untrusted)

E(untrusted) – F(trusted)

check_security(A,F) returns {(C,E), (E,F)}, since only removing either of those edges forces every path between A and F to take at least one untrusted edge.

You should strive to make your implementation as efficient as possible. Note that while we don’t explicitly test for the efficiency of your implementation, using inefficient implementations may cause timeouts on Ed.

TO IMPLEMENT:

You will need to implement these functions:

vertex.py

Code

vertex.py

This file holds all information about the vertex in the graph.

Properties

add_vertex(vertex)

remove_vertex(vertex)

add_edge(vertex_A, vertex_B)

remove_edge(vertex_A, vertex_B)

send_message(s, t)

check_security(s, t)

You will be marked using a range of public and hidden tests. There won’t be additional tests added after the due date.

All tests are between 1 to 3 marks each.