Method IsStructureValid

Common/DataModel/vtkTree.cxx:100–192

------------------------------------------------------------------------------

//------------------------------------------------------------------------------
bool vtkTree::IsStructureValid(vtkGraph* g)
{
  if (!g)
  {
    return false;
  }

  vtkTree* tree = vtkTree::SafeDownCast(g);
  if (tree)
  {
    // Since a tree has the additional root property, we need
    // to set that here.
    this->Root = tree->Root;
    return true;
  }

  // Empty graph is a valid tree.
  if (g->GetNumberOfVertices() == 0)
  {
    this->Root = -1;
    return true;
  }

  // A tree must have one more vertex than its number of edges.
  if (g->GetNumberOfEdges() != g->GetNumberOfVertices() - 1)
  {
    return false;
  }

  // Find the root and fail if there is more than one.
  vtkIdType root = -1;
  for (vtkIdType v = 0; v < g->GetNumberOfVertices(); ++v)
  {
    vtkIdType indeg = g->GetInDegree(v);
    if (indeg > 1)
    {
      // No tree vertex should have in degree > 1, so fail.
      return false;
    }
    else if (indeg == 0 && root == -1)
    {
      // We found our first root.
      root = v;
    }
    else if (indeg == 0)
    {
      // We already found a root, so fail.
      return false;
    }
  }
  if (root < 0)
  {
    return false;
  }

  // Make sure the tree is connected with no cycles.
  std::vector<bool> visited(g->GetNumberOfVertices(), false);
  std::vector<vtkIdType> stack;