Dictionary looping getting every value

Question

without any imports

# given
deps = {'W': ['R', 'S'], 'C': [], 'S': ['C'], 'R': ['C'], 'F': ['W']}
prob = {'C': [0.5], 'R': [0.2, 0.8], 'S': [0.5, 0.1], 'W': [0.01, 0.9, 0.9,     0.99], 'F' : [0.4, 0.3]}
k = 'F'
# want to return:  L = [[0.2, 0.8], [0.5, 0.1], [0.01, 0.9, 0.9, 0.99], [0.4, 0.3]]


# attempt

L = []

for i in deps[k]:
    s = i
    while(deps[s] != []):
        L.append(prob[s])
        s = deps[s]
print(L)

I'm having trouble figuring this out. So given 2 dictionaries: dependents and probability I wish to traverse through a select point and set every value so for the above example I chose 'F'.

It would first go into the deps of 'F', find 'W' and then check the deps of that being ['R', 'S'] then check 'R' seeing that the depedent of 'R' is 'C' and 'C' does not a depedent so we stop at 'R' and append its probability into L.

 [[0.2, 0.8]]

then we go into S and do the same thing

[[0.2, 0.8], [0.5, 0.1]]

then we're done with that and we're back at W

[[0.2, 0.8], [0.5, 0.1], [0.01, 0.9, 0.9, 0.99]]

and finally since we're done with W we get the prob dict of F

[[0.2, 0.8], [0.5, 0.1], [0.01, 0.9, 0.9, 0.99], [0.4, 0.3]]

My code fails when theres more than one dependent value. Not sure how to wrap my head around that. Trying to make a function that will do this given deps and prob and value of k

Answer 1

Here is a solution that uses a stack-based depth-first search to traverse the dependency tree. It adds probabilities at each step iff. the node has dependencies, and then simply reverses the list at the end.

def prob_list(root):
    nodes_to_visit = [root]
    prob_list = []

    while nodes_to_visit:
        curr = nodes_to_visit.pop()
        print(f"Visiting {curr}")

        if deps[curr]:
            prob_list.append(prob[curr])
            for dep in deps[curr]:
                nodes_to_visit.append(dep)

    return list(reversed(prob_list))

print(prob_list("F"))  # [[0.2, 0.8], [0.5, 0.1], [0.01, 0.9, 0.9, 0.99], [0.4, 0.3]]