I have a tree
N nodes (Min-Span-Tree of a graph), and what I am gonna do is to calculate for each node Vi, the number of nodes reachable from each of it's edges (Vi,Vj). So after running the algorithm, every node of degree
d will have
d values each on a single edge shows the number of noded reachable using that specific edge.
I can remember an approach to solve the problem, but I cannot exactly remember the name of it so I can find it on the internet. Here is a description of the approach:
1- Pick a random node 2- Treat it as root of the tree (structure the tree) 3- Start from leaves and send 1 to the parents. 4- for each interleaving node (non-leaf), if it has received the message from all the childs, send the summation plus 1 to the parent. 5- Do the step 4 recursively until you reach the root. 6- For root set x = 1 + (sum of messages from all the childs) 7- subtract the incoming value from x and send the resulting value back to childs. 8- send down the value recursively while subtracting, until you reach the leaves.
and then send back info until you reach childs:
I tought the name of this algorithm is message passing. But I found many other message passing concepts but this one through my search on the web.
So what I am exactly looking for, is the name of the algorithm, the complexity, and after all if available a python package for this.
For the complexity I beleive it must be the same as the number of edges
E, which is number of
N-1 so this should be