[vtkusers] Bug in vtkBoostPrimMinimumSpanningTree?

[Thompson, David C]

Hi all,

I'm curious if anyone has ever used vtkBoostPrimMinimumSpanningTree. I'm
trying to but unexpectedly get an empty tree out no matter what I put in. A
python script that should generate a non-NULL spanning tree is attached.
I've tracked down what I think is the problem but I'm not sure enough of
my fix to commit it.

The problem seems to be in vtkBoostPrimMinimumSpanningTree.cxx around
line 195 where the input vertices are copied to temp:

    temp->GetVertexData()->PassData(input->GetVertexData());
    temp->GetPoints()->ShallowCopy(input->GetPoints());

and then later (at line 222), this loop

    for( i = 0; i < temp->GetNumberOfVertices(); i++ ) { ... }

fails because GetNumberOfVertices() relies on temp's Internals->Adjacency.size()
which has not been adjusted to match the number of vertices. Adding

    vtkVertexAdjacencyList blank;
    temp->GetGraphInternals( true )->Adjacency.resize( input->GetNumberOfVertices(), blank );

to the code around line 195 produces some output but I'm not sure this
is the correct fix. Can someone with Boost graph experience weigh in?

    Thanks,
    David

Python script to demonstrate the problem:

#!/bin/env vtkpython
from vtk import *

g = vtkMutableDirectedGraph()
r = vtkIntArray()
r.SetName( 'Revision' )
w = vtkIntArray()
w.SetName( 'Weight' )
revs = [ 4296, 5051, 6061, 8264, 9999 ]
wgts = [     1,    8,    8,    1      ]
g.GetVertexData().AddArray(r)
g.GetEdgeData().AddArray(w)
for i in range(len(revs)):
  g.AddVertex()
  r.InsertNextValue( revs[i] )
for i in range(len(wgts)):
  g.AddGraphEdge( i, i+1 )
  w.InsertNextValue( wgts[i] )
g.AddGraphEdge( 1, 3 ) # add a cycle to make life interesting
w.InsertNextValue( 1 )

mst = vtkBoostPrimMinimumSpanningTree()
mst.SetInput( g )
mst.SetEdgeWeightArrayName( 'Weight' )
mst.SetOriginVertex( 0 )
mst.Update()
rtree = mst.GetOutput()
rtree.Dump()