Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
Assignment 4 - Fremen Travel
All submitted work must be done individually without consulting someone else’s solutions in accordance with the University’s Academic Dishonesty and Plagiarism policies.
Story
The year is 23,352, space travel is common, and we’re running a small Fremen travel agency on a tiny planet known as Arrakis. Travellers come to us to plan trips from literally anywhere to any other place on the planet. As this planet is 99% desert, we need to occasionally visit a water source to rehydrate and keep our customers happy. Unfortunately for us, not all locations on Arrakis are safe for unassuming travellers, as some are controlled by the cruel Harkonnen or infested with sandworms. Thus, we need to ensure that any route we plan avoids those unsafe locations.
You have been hired to help with maintaining our network of locations (modelled as a weighted simple undirected graph) as well as design some algorithms to determine a variety of travel routes on the planet:
• Maintain our travel network by supporting operations to add new locations (vertices), remove existing ones, change locations from safe to unsafe and vice versa, add and remove edges between them, and update travel times (edge weights).
• Our main operation will be to determine whether there exists a travel route from a starting location to a destination and visits only safe locations along the way.
• Now that we have a method of determining whether a path exists, you’re also asked to implement two extensions:
• The first is to find a shortest path from the source to the destination via a specific oasis that visits only safe locations. The length of the path is determined as the sum of the travel times of the edges that are part of the path.
• The second is to find a path from the source to the destination via some oasis that visits only safe locations that visits the fewest number of locations. If a location is visited both from the source to the oasis and from the oasis to the destination, this counts as two visited locations.
Your Task
Maintain a graph where each vertex stores a boolean value is_safe indicating whether it is a location that’s safe to be visited. You can assume that the initial weighted graph is undirected and simple and your operations should ensure it stays that way.
Find Path
You must also support the path_exists(source, destination) function, which returns whether a path from the source to the destination that visits only safe locations exists in our travel network. You can assume that the source and destination are distinct safe vertices.
Example:
A(safe) -5- B(safe) -4- C(safe) -2- D(unsafe) -5- E(safe)
• path_exists(A, C) returns true
• path_exists(A, E) returns false
Fastest Path
Your graph must support the fastest_path(source, destination, oasis) operation that returns a shortest path (as a sequence of locations) from the source to the destination that goes via the oasis and visits only safe locations if such a path exists, and none otherwise. You can assume that the source and destination and oasis are distinct safe vertices.
Example:
A(safe) -5- B(safe) -4- C(safe) -2- D(unsafe) -5- E(safe)
• fastest_path(A, C, B) returns [A,B,C]
• fastest_path(A, E, B) returns none
• fastest_path(A, B, C) returns [A,B,C,B]
Most Direct Path
Your graph must support the most_direct_path(source, destination, oases) operation that returns a path (as a sequence of locations) consisting of the fewest visited locations from the source to the destination that goes via at least one oasis from the provided list of oases and visits only safe locations if such a path exists, and none otherwise. You can assume that the source and destination and all oases are distinct safe vertices.
Example:
A(safe) -5- B(safe) -4- C(safe) -2- D(unsafe) -5- E(safe)
• most_direct_path(A, C, [B]) returns [A,B,C]
• most_direct_path(A, E, [B]) returns none
• most_direct_path(A, B, [C, E]) returns [A,B,C,B]You should strive to make your implementation as e[icient as possible. Note that while we don’t explicitly test for the e[iciency of your implementation, using ine6icient implementations may cause timeouts on Ed.
TO IMPLEMENT:
You will need to implement these functions:
vertex.py
• add_edge, remove_edge
• update_status
edge.py
• update_weight
graph.py
• add_vertex, remove_vertex
• add_edge, remove_edge
• exists_path
• fastest_path
• most_direct_path
(Note, you can add additional functions and variables to the classes if required, so feel free to modify and extend those as long as you leave the existing function signatures and variables intact.)
Code
vertex.py
This file holds all information about the vertices in the graph.
Properties
• is_safe – boolean: Indicates whether the vertex is safe or unsafe.
• edges – set[Edge]: The set of edges connected to this vertex.
Functions
• add_edge(edge)
o Adds an edge to the vertex, does nothing if this would result in a graph that isn’t simple. • remove_edge(edge)
o Removes the edge to the vertex, if it exists.
• get_edges() (OR vertex.edges)
o Returns the list of edges.
• update_status(is_safe)
o Updates is_safe.
• get_is_safe() (OR vertex.is_safe)
o Returns whether the vertex is safe.
edge.py
This file holds all information about the edges in the graph.
Properties
• weight – integer: The weight of the edge (a positive integer).
• endpoints – tuple[Vertex]: The two endpoints of the edge.
Functions
• get_endpoints() (OR edge.endpoints)
o Returns the endpoints of the edge.
• update_weight(integer)
o Updates the weight of the edge.
• get_weight() (OR edge.weight)
o Returns the weight of the edge.
graph.py
The main graph file, holds all interaction with the graph, vertices and edges.
Properties
• vertices – set[Vertex]: The vertices of the graph.
• edges – set[Edge]: The edges of the graph.
Functions
• add_vertex(vertex)
o Adds the vertex to the graph.• remove_vertex(vertex)
o Removes the vertex from the graph.
• add_edge(vertex_A, vertex_B, weight)
o Adds and edge between vertex A and vertex B with the specified weight,
unless the resulting graph wouldn’t be simple.
• remove_edge(vertex_A, vertex_B)
o Removes the edge between vertex A and vertex B, if it exists.
• exists_path(source, destination)
o Returns whether a path from the source to the destination that visits only safe vertices exists.
o You can assume that the source and the destination are distinct safe vertices.
• fastest_path(source, destination, oasis)
o Returns a shortest path from the source to the destination via the oasis that visits only safe vertices, if one exists. Otherwise, returns none.
o You can assume that the source, destination, and the oasis are distinct safe vertices.
• most_direct_path(source, destination, oases)
o Returns a path that visits the fewest vertices, starting from the source and ending at the destination via at least one of the oases that visits only safe vertices, if one exists. Otherwise, returns none.
o You can assume that the source, destination, and all oases are distinct safe vertices.
Important Information
Be careful with copy and deepcopy as this may a[ect checks in the testcases.
Please always return unmodified vertices when asked for a path.
The list of vertices that form a path is ordered. Its first element should be the source and its last should be the destination, with every pair of consecutive elements connected by an edge.
MarkingYou 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