[vtkusers] Bug in vtkBoostPrimMinimumSpanningTree?
jeff.baumes at kitware.com
Fri May 21 08:59:53 EDT 2010
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
>> 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
//FIXME - We're not copying the edge data, see FIXME note below.
@@ -218,11 +219,6 @@ int vtkBoostPrimMinimumSpanningTree::RequestData(
- 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.
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.
More information about the vtkusers