[vtkusers] vtkBoostPrimMinimumSpanningTree unexpected result: MST is a forest

[David Doria]

On Mon, Nov 2, 2009 at 6:33 AM, Jeff Baumes <jeff.baumes at kitware.com> wrote:
>
>> However, it never passes the "degree == 0" test, so I'm assuming the
>> graph is connected. If that is the case, why would I get this "MST is
>> a forest" error? Or have I done something wrong with checking if the
>> graph is connected (every vertex must be of degree at least 1)?
>>
>
> It can still be disconnected with every vertex having degree at least one,
> e.g., a 4-vertex undirected graph with the following edges:
>
> 0--1
> 2--3
> Jeff
>

Ah yes, what a terrible algorithm I came up with haha. Do you have any
recommendations on how connect the the graph? The only thing I came up
with was:

1) Somehow find a tree on each disconnected part of the graph and then
use a DFS iterator to see which vertices could be reached from the
root of the tree. The vtkBoostPrimMinimumSpanningTree seems to know
that the resulting MST on the entire graph is a forest - is there any
way to get it to give me the forest of MSTs so I can use all of the
trees in my ConnectGraph function?

2) build a KDTree out of the points that cannot be reached by the root
of each tree.

3) Do an "all nearest neighbors" search (which there is no algorithm
for in VTK) to find the closest points in the two point sets

4) add an edge between the closest points

5) do this for every disconnected part of the graph (now in tree form)

Is this a reasonable way to go?

Thanks,

David