0
$\begingroup$

I have a tree T with 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.

Here is a toy example: toy example for message passing

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.

Here are three steps of the algorithm for the toy example: enter image description here enter image description here enter image description here enter image description here

and then send back info until you reach childs:

enter image description here

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 O(N).

$\endgroup$
  • 1
    $\begingroup$ Do you have a specific question? Are you asking about the running time of your algorithm? As a function of what variable? Can you provide concise pseudocode for your algorithm? I had some difficulty understanding based on the English description. Requests for software packages or programs are off-topic here, so please remove that part. $\endgroup$ – D.W. Apr 12 at 23:51
  • $\begingroup$ @D.W. I change the description, and I added some examples. Thanks. $\endgroup$ – ameerosein Apr 14 at 2:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.