[vtkusers] Bug in vtkBoostPrimMinimumSpanningTree?

[Jeff Baumes]

On Wed, May 19, 2010 at 3:04 PM, David Thompson <dcthomp at sandia.gov> wrote:
> Hi David,
>
>>> Hm you're right, I am also seeing that the output has 0 vertices and
>>> edges.
>>
>> That fix worked for me.
>
> Thanks for verifying the fix.
>
>> ... Jeff - want to take a look and commit if it seems reasonable?
>
> I forwarded it to Jeff on Monday and haven't heard back so I assume he's out
> of the office. But if it works for you and no one else replies, I'll check
> in a fix tomorrow or Friday.

I indeed introduced a bug when I made the following change:

@@ -192,7 +192,8 @@ int vtkBoostPrimMinimumSpanningTree::RequestData(

   // Initialize copying data into tree
   temp->GetFieldData()->PassData(input->GetFieldData());
-  temp->GetVertexData()->CopyAllocate(input->GetVertexData());
+  temp->GetVertexData()->PassData(input->GetVertexData());
+  temp->GetPoints()->ShallowCopy(input->GetPoints());
   //FIXME - We're not copying the edge data, see FIXME note below.
   //  temp->GetEdgeData()->CopyAllocate(input->GetEdgeData());

@@ -218,11 +219,6 @@ int vtkBoostPrimMinimumSpanningTree::RequestData(
     }

   vtkIdType i;
-  for( i = 0; i < input->GetNumberOfVertices(); i++ )
-    {
-    vtkIdType tree_v = temp->AddVertex();
-    temp->GetVertexData()->CopyData( input->GetVertexData(), i, tree_v );
-    }
   for( i = 0; i < temp->GetNumberOfVertices(); i++ )
     {
     if( predecessorMap->GetValue(i) == i )

The correct fix is to add the loop back in, but just perform the
AddVertex(), not the CopyData(). This does the same thing as David T's
fix, but in a less hackish way. I've published the fix, let me know if
there are further issues.

commit 32a7f9d9f8189a7019d0e5e3c28a62dff9053b57
Author: Jeffrey Baumes <jeff.baumes at kitware.com>
Date:   Fri May 21 08:56:21 2010 -0400

    BUG: Fixing Prim's MST and adding test

    Prim's MST was always returning an empty tree due to a bug in
    a previous commit.

    Also added a test for Prim's algorithm.


Jeff