I am keeping a directed acyclic graph structure in a dictionary where each key is a parent and each value is another dictionary, which maps the children of the parent with corresponding edge weights. For example, in the graph below, parent 1 has 2 children; 2 and 3 with edge weights corresponding to 2:
g = {
0: Counter({1: 1}),
1: Counter({2: 2, 3: 6}),
2: Counter({4: 3, 5: 2, 6: 1}),
3: Counter({6: 2, 5: 7}),
4: Counter({}),
5: Counter({}),
6: Counter({})
}
I also have a frequency map for each node, where everyone has 0 counts (except the children nodes, where they have a count of 1), such that:
count_map = {i: 0 for i in range(7)}
I would like to increase the value of each node by the following scheme: each leaf (4, 5 and 6 in this case) sends a count of 1 to the upper nodes. Each parent node takes the count and multiplies it with the corresponding edge (e.g. if 5 sends the count 1 to upper level, then its parent 2 will get a count of 1x2 and its other parent 3 will get a count of 1x7). Then those parents also passes this message to their parents, e.g. 3 will pass a count of 7 to node 1 and node 1 will replace his count with 7x6. Each parent will pass the accumulated counts to upper levels until they reach to the root node.
Of course, if a node gets a message from multiple parents, it needs to add up the counts and pass it to its parent.
How can I compute this count_map? Any help, pointers or pseudo code is appreciated.