Permalink
Switch branches/tags
Nothing to show
Find file
Fetching contributors…
Cannot retrieve contributors at this time
220 lines (193 sloc) 5.57 KB
/*=========================================================================
Program: Visualization Toolkit
Module: vtkTree.cxx
Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
All rights reserved.
See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
This software is distributed WITHOUT ANY WARRANTY; without even
the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE. See the above copyright notice for more information.
=========================================================================*/
/*-------------------------------------------------------------------------
Copyright 2008 Sandia Corporation.
Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
the U.S. Government retains certain rights in this software.
-------------------------------------------------------------------------*/
#include "vtkTree.h"
#include "vtkInformation.h"
#include "vtkInformationVector.h"
#include "vtkObjectFactory.h"
#include "vtkOutEdgeIterator.h"
#include "vtkSmartPointer.h"
#include <vtksys/stl/vector>
using vtksys_stl::vector;
vtkStandardNewMacro(vtkTree);
//----------------------------------------------------------------------------
vtkTree::vtkTree()
{
this->Root = -1;
}
//----------------------------------------------------------------------------
vtkTree::~vtkTree()
{
}
//----------------------------------------------------------------------------
vtkIdType vtkTree::GetChild(vtkIdType v, vtkIdType i)
{
const vtkOutEdgeType *edges;
vtkIdType nedges;
this->GetOutEdges(v, edges, nedges);
if (i < nedges)
{
return edges[i].Target;
}
return -1;
}
//----------------------------------------------------------------------------
vtkIdType vtkTree::GetParent(vtkIdType v)
{
const vtkInEdgeType *edges;
vtkIdType nedges;
this->GetInEdges(v, edges, nedges);
if (nedges > 0)
{
return edges[0].Source;
}
return -1;
}
//----------------------------------------------------------------------------
vtkEdgeType vtkTree::GetParentEdge(vtkIdType v)
{
const vtkInEdgeType *edges;
vtkIdType nedges;
this->GetInEdges(v, edges, nedges);
if (nedges > 0)
{
return vtkEdgeType(edges[0].Source, v, edges[0].Id);
}
return vtkEdgeType();
}
//----------------------------------------------------------------------------
vtkIdType vtkTree::GetLevel(vtkIdType vertex)
{
if (vertex < 0 || vertex >= this->GetNumberOfVertices())
{
return -1;
}
vtkIdType level = 0;
while (vertex != this->Root)
{
vertex = this->GetParent(vertex);
level++;
}
return level;
}
//----------------------------------------------------------------------------
bool vtkTree::IsLeaf(vtkIdType vertex)
{
return (this->GetNumberOfChildren(vertex) == 0);
}
//----------------------------------------------------------------------------
vtkTree *vtkTree::GetData(vtkInformation *info)
{
return info? vtkTree::SafeDownCast(info->Get(DATA_OBJECT())) : 0;
}
//----------------------------------------------------------------------------
vtkTree *vtkTree::GetData(vtkInformationVector *v, int i)
{
return vtkTree::GetData(v->GetInformationObject(i));
}
//----------------------------------------------------------------------------
bool vtkTree::IsStructureValid(vtkGraph *g)
{
if (vtkTree::SafeDownCast(g))
{
// Since a tree has the additional root propery, we need
// to set that here.
this->Root = (vtkTree::SafeDownCast(g))->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.
vector<bool> visited(g->GetNumberOfVertices(), false);
vector<vtkIdType> stack;
stack.push_back(root);
vtkSmartPointer<vtkOutEdgeIterator> outIter =
vtkSmartPointer<vtkOutEdgeIterator>::New();
while (!stack.empty())
{
vtkIdType v = stack.back();
stack.pop_back();
visited[v] = true;
g->GetOutEdges(v, outIter);
while (outIter->HasNext())
{
vtkIdType id = outIter->Next().Target;
if (!visited[id])
{
stack.push_back(id);
}
else
{
return false;
}
}
}
for (vtkIdType v = 0; v < g->GetNumberOfVertices(); ++v)
{
if (!visited[v])
{
return false;
}
}
// Since a tree has the additional root propery, we need
// to set that here.
this->Root = root;
return true;
}
//----------------------------------------------------------------------------
void vtkTree::ReorderChildren(vtkIdType parent, vtkIdTypeArray *children)
{
this->ReorderOutVertices(parent, children);
}
//----------------------------------------------------------------------------
void vtkTree::PrintSelf(ostream& os, vtkIndent indent)
{
this->Superclass::PrintSelf(os,indent);
os << indent << "Root: " << this->Root << endl;
}