[vtkusers] vtkBoostPrimMinimumSpanningTree unexpected result: MST is a forest

David Doria daviddoria+vtk at gmail.com
Fri Oct 30 13:57:40 EDT 2009


I am trying to find the minimum spanning tree of a graph:

  vtkSmartPointer<vtkBoostPrimMinimumSpanningTree>
MinimumSpanningTreeFilter =
vtkSmartPointer<vtkBoostPrimMinimumSpanningTree>::New();
  MinimumSpanningTreeFilter->SetOriginVertex(MaxZId);
  MinimumSpanningTreeFilter->SetInput(NearestNeighborGraph);
  MinimumSpanningTreeFilter->SetEdgeWeightArrayName("Weights");

But I am getting this error:
vtkBoostPrimMinimumSpanningTree (0x85dda08): Unexpected result: MST is
a forest (collection of trees).

I was assuming the graph was disconnected, so I wrote this function to
connected the disconnected parts of the graph, and call it with:
ConnectGraph(NearestNeighborGraph, input->GetPoints());

void ConnectGraph(vtkMutableUndirectedGraph* G, vtkPoints* Points)
{
  //the graph already contains a vertex for every point in Points - we
need Points only to build the KDTree
  vtkSmartPointer<vtkKdTree> KDTree = vtkSmartPointer<vtkKdTree>::New();
  KDTree->BuildLocatorFromPoints(Points);

  std::queue <unsigned int> q;

  for(unsigned int i = 0; i < G->GetNumberOfVertices(); i++)
  {
      q.push(i);
  }

  while (!q.empty())
  {
    unsigned int id = q.front();
    q.pop();

    unsigned int degree = G->GetInDegree(id);

    if(degree == 0)
    {
      //add an edge from the current point (degree==0) to the closest
point in the graph
      double p[3];
      Points->GetPoint(id, p);
      double dist;
      unsigned int ClosestPointId = KDTree->FindClosestPoint(p, dist);
      G->AddEdge(id, ClosestPointId);
    }

  }

}

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)?

Thanks,

David



More information about the vtkusers mailing list