[vtkusers] Bug in vtkBoostPrimMinimumSpanningTree?

[David Doria]

On Sun, May 16, 2010 at 12:29 AM, Thompson, David C <dcthomp at sandia.gov> wrote:
> 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()

David T,

I've used this many times, but only in c++:
http://vtk.org/Wiki/VTK/Examples/Graphs/MinimumSpanningTree

Maybe it is a problem with the python wrapping?

Thanks,

David D.