Question 3 (25 marks)
- Consider an ADT for undirected graphs, named UGraph, that includes these operations:
- nodes, which returns a sequence of all nodes in the graph, in no particular order
- has_edge, which takes two nodes and returns true only if there is an edge between those nodes
- edges, which returns a sequence of node-node pairs (tuples), in no particular order. Each edge only appears once in the returned sequence, i.e. if the pair (node1, node2) is in the sequence, the pair (node2, node1) is not.
How each node is represented is irrelevant. Because the graph is undirected, has_edge(node1, node2) and has_edge(node2, node1) return the same. You can assume the graph is connected and has no edge between a node and itself.
The following stand-alone Python function checks if an undirected graph is complete, i.e. if each node is connected to every other node. It assumes the ADT is implemented as a Python class.
- nodes = graph.nodes()
- for node1 in nodes:
- for node2 in nodes:
- edge_exists = graph.has_edge(node1, node2)
- if node1 != node2 and not edge_exists:
- return False
- return True
- Assume that nodeshas complexity O(n), where n is the number of nodes, and graph.has_edge has complexity O(1). State and justify a best-case scenario and a worst-case scenario for the above function. State and explain the Big-O complexity for each scenario. Assume the basic computational step is the assignment. State explicitly any other assumptions you make. (7 marks)
- This part is about ADT specifications (Unit 2 Section 3.6and Companion).
In graph theory, the number of nodes in a graph is called the order of the graph. The term ‘order’ is unrelated to sorting. Specify the problem of computing the order, as a UGraph operation.
- Creator / Inspector / Modifier (delete as appropriate): order
- Justify the kind of operation. (5 marks)
- This part is about initial insights (Unit 2 Section 2.3and Companion).
Give your initial insight for an algorithm that solves the order problem. You can use any of the M269 data structures listed in the Companion’s appendix but of the ADT operations given above you may only use edges. (4 marks)
- A city council is planning the city’s bus routes. It has decided which places will have a bus stop (schools, cinemas, hospital, etc.). Each bus route will start from the train station, visit a number of bus stops, and then return to the station, visiting the same bus stops in reverse order. Each bus stop has to be served by at least one bus route. The council wants to minimise the total amount of time that all buses are on the road when following their routes.
This problem can be solved by first defining a graph and then applying to it a graph algorithm to obtain the answer.
- This part is about modelling with graphs (Companion).
Define a graph that is suitable for this problem, by addressing the following questions. Justify your answers. Explicitly state any assumptions you make.
- What do the nodes and edges represent?
- Are edges directed? If so, what does the direction represent?
- Are edges weighted? If so, what do the weights represent?
- Is the graph acyclic or cyclic?
- Is the graph dense or sparse? (6 marks)
- This question is about graph algorithms (Unit 5 Section 2and the Companion).
What algorithm(s) would you adopt or adapt to efficiently compute the bus routes according to the council’s criterion? You do not need to explain any algorithm given in M269, only how it could be used or modified to solve the problem. State explicitly any assumptions you make. (3 marks)