Not all foreign nearest neighbors are updated for a component

[chrisnatali]

Consider the following graph

1--2----3--4

After the initial finding nearest neighbors and one round of MST, the following components will exist: C = {(1, 2), (3, 4)} each with the same priority.

When we go to update the foreign nearest neighbors in the next round, the top of the queue for C[0] is (1, 2), and we'll add edge (1, 3) to Ep without considering edge (2, 3) which is a shorter connection between C[0] and C[1]. This would result in a non minimum MSF.

I missed the fact that the queue for components that are nearest neighbors of each other will contain both edges. So, the above should read:

When we go to update the foreign nearest neighbors in the next round, the queue for C[0] is [(1, 2), (2, 1)] and we'll add edge (1, 3) and (2, 3) to C[0]'s queue. Since (2, 3) is shorter, the min edge will be added to the tree.

To ensure we select the min edge between components, the Boruvka Meets Nearest Neighbors paper suggests that all component queues maintain all contained node, foreign nearest neighbor pairs (page 6 para 2). I believe implementing this would resolve this.

The above is ensured.

I believe this block needs to change to accomodate setting foreign nearest neighbors for ALL nodes within the component.

It does NOT need to change.

[chrisnatali]

Maybe this is what was going to be addressed by the 'neighborhood' attribute in UnionFind ?

[chrisnatali]

Turns out this is a non-issue. Updated original Issue. Still not sure what the 'neighborhood' attribute was to be used for, but I'll open another one if needed.