[vtk-developers] mods to vtkDijkstraGraphGeodesicPath

[dean.inglis at camris.ca]

Hi,

I am developing a filter to do Dijkstra's shortest
path algorithm along the lines of vtkDijkstraGraphGeodesicPath
which inherits from vtkPolyDataAlgorithm.  My version is
directed to vtkImageData and I have also written a 
vtkContourLineInterpolator so that one can interactively
generate polydata paths between vertices.

It works but I want to make this more efficient, since in the polydata
implementation: vtkPolygonalSurfaceContourLineInterpolator
instantiates a new vtkDijkstraGraphGeodesicPath (vtkDGGP) every time
a new pair of vertices are identified by the vtkContourWidget.
For every instantiation, vtkDGGP has to initialize itself,
build an adjacency list etc.  If the input is not changing,
this is unnecessary and only two ivars need to be reset:
  this->IdList->Reset();
  this->Hsize = 0;
currently this is done in Initialize, but Initialize could
be split with the previous two lines placed in a separate
Reset() method.  In this way Initialize could be done at
the point of SetInput or SetInputConnection rather than
in RequestData.  Am I on the right track here?
Would there need to be a time stamp mechanism
in the filter's  RequestData so that Initialize is called only when the
input to the filter is changed?

Dean

//----------------------------------------------------------------------------
int vtkDijkstraGraphGeodesicPath::RequestData(
  vtkInformation *           vtkNotUsed( request ),
  vtkInformationVector **    inputVector,
  vtkInformationVector *     outputVector) 
{
  vtkInformation * inInfo = inputVector[0]->GetInformationObject(0);
  vtkInformation *outInfo =   outputVector->GetInformationObject(0);

  vtkPolyData *input = vtkPolyData::SafeDownCast(  
    inInfo->Get(vtkDataObject::DATA_OBJECT()));
  if (!input)
    {
    return 0;
    }

  vtkPolyData *output = vtkPolyData::SafeDownCast(
    outInfo->Get(vtkDataObject::DATA_OBJECT()));
  if (!input)
    {
    return 0;
    }

/* HERE IS WHERE SOME FORM OF TIME STAMP CHECKING
   COULD BE DONE ???? */  

  this->Initialize();

/* I.E.:
   if (this->BuildTime > this->MTime)
     this->Reset();
  else
     this->Initialize();    */


  this->ShortestPath(this->StartVertex, this->EndVertex);
  this->TraceShortestPath(input, output, this->StartVertex, this->EndVertex);
  return 1;
}

//----------------------------------------------------------------------------
void vtkDijkstraGraphGeodesicPath::Initialize()
{
  vtkPolyData *input = vtkPolyData::SafeDownCast(
      this->GetExecutive()->GetInputData(0, 0));

  this->BuildAdjacency( input );
  
/*  this->IdList->Reset();  // move out to a method called Reset*/
  
  this->n = input->GetNumberOfPoints();
  
  this->d->SetNumberOfComponents(1);
  this->d->SetNumberOfTuples(this->n);
  this->pre->SetNumberOfComponents(1);
  this->pre->SetNumberOfTuples(this->n);
  this->f->SetNumberOfComponents(1);
  this->f->SetNumberOfTuples(this->n);
  this->s->SetNumberOfComponents(1);
  this->s->SetNumberOfTuples(this->n);
  this->p->SetNumberOfComponents(1);
  this->p->SetNumberOfTuples(this->n);
  
  // The heap has elements from 1 to n
  this->H->SetNumberOfComponents(1);
  this->H->SetNumberOfTuples(this->n+1);
  
 /* this->Hsize = 0;  // move out to a method called Reset*/

  this->Reset();  //*** new method
}

//----------------------------------------------------------------------------
void vtkDijkstraGraphGeodesicPath::Reset()
{
  this->IdList->Reset();
  this->Hsize = 0;
}