python graph - how to sort a list of nodes in graph

Question

I am faced with the below question. Any ideas? Please help.

There are two pre-defined functions given. One creates a digraph, another uses DFS to get the path between nodes. Problem is to return a path in increasing order between n to m.

Eg: g = {0: [2], 1: [8, 3], 2: [4, 3, 8], 3: [4, 2, 0], 4: [8, 0], 5: [4, 1, 3], 8: [2, 0, 5, 3, 1]} n = 8 Output [0, 1, 2, 3, 4, 5]

import random
  
# You are given this function - do not modify
def createRandomGraph():
    """Creates a digraph with 7 randomly chosen integer nodes from 0 to 9 and
    randomly chosen directed edges (between 10 and 20 edges)
    """
    g = {}
    n = random.sample([0,1,2,3,4,5,6,7,8,9], 7)
    for i in n:
        g[i] = []
    edges = random.randint(10,20)
    count = 0
    while count < edges:
        a = random.choice(n)
        b = random.choice(n)
        if b not in g[a] and a != b:
            g[a].append(b)
            count += 1
    return g

# You are given this function - do not modify
def findPath(g, start, end, path=[]):
    """ Uses DFS to find a path between a start and an end node in g.
    If no path is found, returns None. If a path is found, returns the
    list of nodes """
    path = path + [start]
    if start == end:
        return path
    if not start in g:
        return None
    for node in g[start]:
        if node not in path:
            newpath = findPath(g, node, end, path)
            if newpath: return newpath
    return None
                
#########################        
## WRITE THIS FUNCTION ##
#########################        

def allReachable(g, n):
    """
    Assumes g is a directed graph and n a node in g.
    Returns a sorted list (increasing by node number) containing all 
    nodes m such that there is a path from n to m in g. 
    Does not include the node itself.
    """
    #TODO

I am very new to python graphs and I really need some help here.

Answer 1

You can choose a random node m, check if it's reachable from n using the supplied DFS function. If a path is found you will receive that path (all the nodes in that path are also reachable from n).

You then repeat the process with a different node that isn't present in the returned path until no nodes remain to be checked.

Pseudo-code:

nodes = g.nodes
nodes.pop(n)
node = nodes[0]
path = DFS(g,n, node)
nodes = nodes - path
while len(nodes)>0:
    node = nodes[0]
    path = DFS(g,n, node)
    nodes = nodes - path
return sorted(g.nodes - nodes)

Answer 2

def allReachable(g, n):
    nodes = []
    for key in g:
        path = findPath(g,n,key)
        if path != None:
            for i in path:
                if i not in nodes:
                    nodes.append(i)
    nodes.remove(n)
    return(sorted(nodes))