Q$2($g$)$

Upon their turn, a player can $$attack$$ an adjoining territory by rolling a die against the defender$$s die. If they win, their armies can move into the new territory. The mechanics of attacking are not important in this question. A player cannot move through or attack their own territories. Therefore, regardless of how many armies they have in a given territory, the territories they can move into from a given starting point may be limited$.$

imageIn the image above, the owners are designated by different colours.

Eastern Australia is owned by a player designated yellow.

New Guinea and Western Australia are owned by a player designated orange.

Indonesia is owned by a player designated pink.

Siam is owned by a player designated green.

Ignoring the number of armies as written on the map, the orange player could, from Western Australia:

attack Eastern Australia, but that is as far as they could go$.$

attack Indonesia and then Siam.

imageIn this example, from Western Australia the orange player can only attack into Eastern Australia. As they own Indonesia, Siam now becomes inaccessible from Western Australia. Again, in this image we have to ignore the number of armies as the image is for illustration only.

Create a function, possible$\_$routes, which, given a graph and a starting node, will return a graph with one of the possible routes to all connected territories other than their own.

When you run the test you should get something that looks like this, based on the first illustration of Australia above:image

NOTE: There are multiple different solutions. This is indicative only!

REMEMBER to only use data types$/$structures$,$ constructs, methods, functions or operations listed in the chapter summaries.

$\%$run $-$i m$269\_$digraph #The M$269$ undirected graph code

$\%$run $-$i m$269\_$ungraph #The M$269$ directed graph code

$\%$run $-$i m$269\_$territories #Create the territories

$$

def possible$\_$routes$($graph: DiGraph, start: Hashable$)->$ DiGraph:

#Write your answer here

pass

$$

#If your code works, the following should draw a path:

#Siam $<-$ Indonesia $->$ Western Australia $->$ Eastern Australia $->$ New Guinea

# or

#Siam $<-$ Indonesia $->$ New Guinea $->$ Western Australia $->$ Eastern Australia

# or

#Siam $<-$ Indonesia $->$ New Guinea $->$ Eastern Australia $->$ Western Australia

$$

path $=$ possible$\_$routes$($australasia$,$Indonesia$)$

path.draw$()$