vtkGraph.cxx

/*=========================================================================

  Program:   Visualization Toolkit
  Module:    vtkGraph.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 "vtkGraph.h"

#include "vtkAdjacentVertexIterator.h"
#include "vtkCellArray.h"
#include "vtkDataSetAttributes.h"
#include "vtkDistributedGraphHelper.h"
#include "vtkEdgeListIterator.h"
#include "vtkGraphEdge.h"
#include "vtkGraphInternals.h"
#include "vtkIdTypeArray.h"
#include "vtkInEdgeIterator.h"
#include "vtkInformation.h"
#include "vtkInformationVector.h"
#include "vtkMath.h"
#include "vtkObjectFactory.h"
#include "vtkOutEdgeIterator.h"
#include "vtkPoints.h"
#include "vtkSmartPointer.h"
#include "vtkVertexListIterator.h"
#include "vtkVariantArray.h"
#include "vtkStringArray.h"

#include <assert.h>
#include <vtksys/stl/algorithm>
#include <vtksys/stl/set>
#include <vtksys/stl/vector>

double vtkGraph::DefaultPoint[3] = {0, 0, 0};

//----------------------------------------------------------------------------
// private class vtkGraphEdgePoints
//----------------------------------------------------------------------------
class vtkGraphEdgePoints : public vtkObject
{
public:
  static vtkGraphEdgePoints *New();
  vtkTypeMacro(vtkGraphEdgePoints, vtkObject);
  vtksys_stl::vector< vtksys_stl::vector<double> > Storage;

protected:
  vtkGraphEdgePoints() { }
  ~vtkGraphEdgePoints() { }

private:
  vtkGraphEdgePoints(const vtkGraphEdgePoints&);  // Not implemented.
  void operator=(const vtkGraphEdgePoints&);  // Not implemented.
};
vtkStandardNewMacro(vtkGraphEdgePoints);

//----------------------------------------------------------------------------
// class vtkGraph
//----------------------------------------------------------------------------
vtkCxxSetObjectMacro(vtkGraph, Points, vtkPoints);
vtkCxxSetObjectMacro(vtkGraph, Internals, vtkGraphInternals);
vtkCxxSetObjectMacro(vtkGraph, EdgePoints, vtkGraphEdgePoints);
vtkCxxSetObjectMacro(vtkGraph, EdgeList, vtkIdTypeArray);
//----------------------------------------------------------------------------
vtkGraph::vtkGraph()
{
  this->VertexData = vtkDataSetAttributes::New();
  this->EdgeData = vtkDataSetAttributes::New();
  this->Points = 0;
  vtkMath::UninitializeBounds(this->Bounds);

  this->Information->Set(vtkDataObject::DATA_EXTENT_TYPE(), VTK_PIECES_EXTENT);
  this->Information->Set(vtkDataObject::DATA_PIECE_NUMBER(), -1);
  this->Information->Set(vtkDataObject::DATA_NUMBER_OF_PIECES(), 1);
  this->Information->Set(vtkDataObject::DATA_NUMBER_OF_GHOST_LEVELS(), 0);

  this->Internals = vtkGraphInternals::New();
  this->DistributedHelper = 0;
  this->EdgePoints = 0;
  this->EdgeList = 0;
}

//----------------------------------------------------------------------------
vtkGraph::~vtkGraph()
{
  this->VertexData->Delete();
  this->EdgeData->Delete();
  if (this->Points)
    {
    this->Points->Delete();
    }
  this->Internals->Delete();
  if (this->DistributedHelper)
    {
    this->DistributedHelper->Delete();
    }
  if (this->EdgeList)
    {
    this->EdgeList->Delete();
    }
  if (this->EdgePoints)
    {
    this->EdgePoints->Delete();
    }
}

//----------------------------------------------------------------------------
double *vtkGraph::GetPoint(vtkIdType ptId)
{
  if (this->Points)
    {
    return this->Points->GetPoint(ptId);
    }
  return this->DefaultPoint;
}

//----------------------------------------------------------------------------
void vtkGraph::GetPoint(vtkIdType ptId, double x[3])
{
  if (this->Points)
    {
    vtkIdType index = ptId;
    if (vtkDistributedGraphHelper *helper = this->GetDistributedGraphHelper())
      {
        int myRank = this->Information->Get(vtkDataObject::DATA_PIECE_NUMBER());
        if (myRank != helper->GetVertexOwner(ptId))
          {
          vtkErrorMacro("vtkGraph cannot retrieve a point for a non-local vertex");
          return;
          }

        index = helper->GetVertexIndex(ptId);
      }

    this->Points->GetPoint(index, x);
    }
  else
    {
    for (int i = 0; i < 3; i++)
      {
      x[i] = this->DefaultPoint[i];
      }
    }
}

//----------------------------------------------------------------------------
vtkPoints *vtkGraph::GetPoints()
{
  if (!this->Points)
    {
    this->Points = vtkPoints::New();
    }
  if (this->Points->GetNumberOfPoints() != this->GetNumberOfVertices())
    {
    this->Points->SetNumberOfPoints(this->GetNumberOfVertices());
    for (vtkIdType i = 0; i < this->GetNumberOfVertices(); i++)
      {
      this->Points->SetPoint(i, 0, 0, 0);
      }
    }
  return this->Points;
}

//----------------------------------------------------------------------------
void vtkGraph::ComputeBounds()
{
  double *bounds;

  if ( this->Points )
    {
    bounds = this->Points->GetBounds();
    for (int i=0; i<6; i++)
      {
      this->Bounds[i] = bounds[i];
      }
    // TODO: how to compute the bounds for a distributed graph?
    this->ComputeTime.Modified();
    }
}

//----------------------------------------------------------------------------
double *vtkGraph::GetBounds()
{
  this->ComputeBounds();
  return this->Bounds;
}

//----------------------------------------------------------------------------
void vtkGraph::GetBounds(double bounds[6])
{
  this->ComputeBounds();
  for (int i=0; i<6; i++)
    {
    bounds[i] = this->Bounds[i];
    }
}

//----------------------------------------------------------------------------
unsigned long int vtkGraph::GetMTime()
{
  unsigned long int doTime = vtkDataObject::GetMTime();

  if ( this->VertexData->GetMTime() > doTime )
    {
    doTime = this->VertexData->GetMTime();
    }
  if ( this->EdgeData->GetMTime() > doTime )
    {
    doTime = this->EdgeData->GetMTime();
    }
  if ( this->Points )
    {
    if ( this->Points->GetMTime() > doTime )
      {
      doTime = this->Points->GetMTime();
      }
    }

  return doTime;
}

//----------------------------------------------------------------------------
void vtkGraph::Initialize()
{
  this->ForceOwnership();
  Superclass::Initialize();
  this->EdgeData->Initialize();
  this->VertexData->Initialize();
  this->Internals->NumberOfEdges = 0;
  this->Internals->Adjacency.clear();
  if (this->EdgePoints)
    {
    this->EdgePoints->Storage.clear();
    }
}

//----------------------------------------------------------------------------
void vtkGraph::GetOutEdges(vtkIdType v, vtkOutEdgeIterator *it)
{
  if (vtkDistributedGraphHelper *helper = this->GetDistributedGraphHelper())
    {
    int myRank = this->Information->Get(vtkDataObject::DATA_PIECE_NUMBER());
    if (myRank != helper->GetVertexOwner(v))
      {
      vtkErrorMacro("vtkGraph cannot retrieve the out edges for non-local vertex " << v);
      int* p = 0;
      *p = 17;
      return;
      }
    }

  if (it)
    {
    it->Initialize(this, v);
    }
}

//----------------------------------------------------------------------------
vtkOutEdgeType vtkGraph::GetOutEdge(vtkIdType v, vtkIdType i)
{
  vtkIdType index = v;
  if (vtkDistributedGraphHelper *helper = this->GetDistributedGraphHelper())
    {
    int myRank = this->Information->Get(vtkDataObject::DATA_PIECE_NUMBER());
    if (myRank != helper->GetVertexOwner(v))
      {
      vtkErrorMacro("vtkGraph cannot retrieve the out edges for non-local vertex " << v);
      int* p = 0;
      *p = 17;
      return vtkOutEdgeType();
      }
    index = helper->GetVertexIndex(v);
    }

  if (i < this->GetOutDegree(v))
    {
    return this->Internals->Adjacency[index].OutEdges[i];
    }
  vtkErrorMacro("Out edge index out of bounds");
  return vtkOutEdgeType();
}

//----------------------------------------------------------------------------
void vtkGraph::GetOutEdge(vtkIdType v, vtkIdType i, vtkGraphEdge* e)
{
  vtkOutEdgeType oe = this->GetOutEdge(v, i);
  e->SetId(oe.Id);
  e->SetSource(v);
  e->SetTarget(oe.Target);
}

//----------------------------------------------------------------------------
void vtkGraph::GetOutEdges(vtkIdType v, const vtkOutEdgeType *& edges, vtkIdType & nedges)
{
  vtkIdType index = v;
  if (vtkDistributedGraphHelper *helper = this->GetDistributedGraphHelper())
    {
    int myRank = this->Information->Get(vtkDataObject::DATA_PIECE_NUMBER());
    if (myRank != helper->GetVertexOwner(v))
      {
      vtkErrorMacro("vtkGraph cannot retrieve the out edges for non-local vertex " << v);
      int* p = 0;
      *p = 17;
      return;
      }

    index = helper->GetVertexIndex(v);
    }

  nedges = this->Internals->Adjacency[index].OutEdges.size();
  if (nedges > 0)
    {
    edges = &(this->Internals->Adjacency[index].OutEdges[0]);
    }
  else
    {
    edges = 0;
    }
}

//----------------------------------------------------------------------------
vtkIdType vtkGraph::GetOutDegree(vtkIdType v)
{
  vtkIdType index = v;
  if (vtkDistributedGraphHelper *helper = this->GetDistributedGraphHelper())
    {
    int myRank = this->Information->Get(vtkDataObject::DATA_PIECE_NUMBER());
    if (myRank != helper->GetVertexOwner(v))
      {
      vtkErrorMacro("vtkGraph cannot determine the out degree for a non-local vertex");
      return 0;
      }

    index = helper->GetVertexIndex(v);
    }
  return this->Internals->Adjacency[index].OutEdges.size();
}

//----------------------------------------------------------------------------
vtkIdType vtkGraph::GetDegree(vtkIdType v)
{
  vtkIdType index = v;

  if (vtkDistributedGraphHelper *helper = this->GetDistributedGraphHelper())
    {
    int myRank = this->Information->Get(vtkDataObject::DATA_PIECE_NUMBER());
    if (myRank != helper->GetVertexOwner(v))
      {
      vtkErrorMacro("vtkGraph cannot determine the degree for a non-local vertex");
      return 0;
      }

    index = helper->GetVertexIndex(v);
    }

  return this->Internals->Adjacency[index].InEdges.size() +
         this->Internals->Adjacency[index].OutEdges.size();
}

//----------------------------------------------------------------------------
void vtkGraph::GetInEdges(vtkIdType v, vtkInEdgeIterator *it)
{
  if (vtkDistributedGraphHelper *helper = this->GetDistributedGraphHelper())
    {
    int myRank = this->Information->Get(vtkDataObject::DATA_PIECE_NUMBER());
    if (myRank != helper->GetVertexOwner(v))
      {
      vtkErrorMacro("vtkGraph cannot retrieve the in edges for a non-local vertex");
      return;
      }
    }

  if (it)
    {
    it->Initialize(this, v);
    }
}

//----------------------------------------------------------------------------
vtkInEdgeType vtkGraph::GetInEdge(vtkIdType v, vtkIdType i)
{
  vtkIdType index = v;
  if (vtkDistributedGraphHelper *helper = this->GetDistributedGraphHelper())
    {
    int myRank = this->Information->Get(vtkDataObject::DATA_PIECE_NUMBER());
    if (myRank != helper->GetVertexOwner(v))
      {
      vtkErrorMacro("vtkGraph cannot retrieve the in edges for a non-local vertex");
      return vtkInEdgeType();
      }
    index = helper->GetVertexIndex(v);
    }

  if (i < this->GetInDegree(v))
    {
    return this->Internals->Adjacency[index].InEdges[i];
    }
  vtkErrorMacro("In edge index out of bounds");
  return vtkInEdgeType();
}

//----------------------------------------------------------------------------
void vtkGraph::GetInEdge(vtkIdType v, vtkIdType i, vtkGraphEdge* e)
{
  vtkInEdgeType ie = this->GetInEdge(v, i);
  e->SetId(ie.Id);
  e->SetSource(ie.Source);
  e->SetTarget(v);
}

//----------------------------------------------------------------------------
void vtkGraph::GetInEdges(vtkIdType v, const vtkInEdgeType *& edges, vtkIdType & nedges)
{
  vtkIdType index = v;

  if (vtkDistributedGraphHelper *helper = this->GetDistributedGraphHelper())
    {
    int myRank = this->Information->Get(vtkDataObject::DATA_PIECE_NUMBER());
    if (myRank != helper->GetVertexOwner(v))
      {
      vtkErrorMacro("vtkGraph cannot retrieve the in edges for a non-local vertex");
      return;
      }

    index = helper->GetVertexIndex(v);
    }

  nedges = this->Internals->Adjacency[index].InEdges.size();
  if (nedges > 0)
    {
    edges = &(this->Internals->Adjacency[index].InEdges[0]);
    }
  else
    {
    edges = 0;
    }
}

//----------------------------------------------------------------------------
vtkIdType vtkGraph::GetInDegree(vtkIdType v)
{
  vtkIdType index = v;

  if (vtkDistributedGraphHelper *helper = this->GetDistributedGraphHelper())
    {
    int myRank = this->Information->Get(vtkDataObject::DATA_PIECE_NUMBER());
    if (myRank != helper->GetVertexOwner(v))
      {
      vtkErrorMacro("vtkGraph cannot determine the in degree for a non-local vertex");
      return 0;
      }

    index = helper->GetVertexIndex(v);
    }

  return this->Internals->Adjacency[index].InEdges.size();
}

//----------------------------------------------------------------------------
void vtkGraph::GetAdjacentVertices(vtkIdType v, vtkAdjacentVertexIterator *it)
{
  if (vtkDistributedGraphHelper *helper = this->GetDistributedGraphHelper())
    {
    int myRank = this->Information->Get(vtkDataObject::DATA_PIECE_NUMBER());
    if (myRank != helper->GetVertexOwner(v))
      {
      vtkErrorMacro("vtkGraph cannot retrieve the adjacent vertices for a non-local vertex");
      return;
      }
    }

  if (it)
    {
    it->Initialize(this, v);
    }
}

//----------------------------------------------------------------------------
void vtkGraph::GetEdges(vtkEdgeListIterator *it)
{
  if (it)
    {
    it->SetGraph(this);
    }
}

//----------------------------------------------------------------------------
vtkIdType vtkGraph::GetNumberOfEdges()
{
  return this->Internals->NumberOfEdges;
}

//----------------------------------------------------------------------------
void vtkGraph::GetVertices(vtkVertexListIterator *it)
{
  if (it)
    {
    it->SetGraph(this);
    }
}

//----------------------------------------------------------------------------
vtkIdType vtkGraph::GetNumberOfVertices()
{
  return this->Internals->Adjacency.size();
}

//----------------------------------------------------------------------------
void vtkGraph::SetDistributedGraphHelper(vtkDistributedGraphHelper *helper)
{
  if (this->DistributedHelper)
    this->DistributedHelper->AttachToGraph(0);

  this->DistributedHelper = helper;
  if (this->DistributedHelper)
    {
    this->DistributedHelper->Register(this);
    this->DistributedHelper->AttachToGraph(this);
    }
}

//----------------------------------------------------------------------------
vtkDistributedGraphHelper *vtkGraph::GetDistributedGraphHelper()
{
  return this->DistributedHelper;
}

//----------------------------------------------------------------------------
vtkIdType vtkGraph::FindVertex(const vtkVariant& pedigreeId)
{
  vtkAbstractArray *pedigrees = this->GetVertexData()->GetPedigreeIds();
  if (pedigrees == NULL)
    {
    return -1;
    }

  if (vtkDistributedGraphHelper *helper = this->GetDistributedGraphHelper())
    {
    vtkIdType myRank
      = this->Information->Get(vtkDataObject::DATA_PIECE_NUMBER());
    if (helper->GetVertexOwnerByPedigreeId(pedigreeId)
          != myRank)
      {
      // The vertex is remote; ask the distributed graph helper to find it.
      return helper->FindVertex(pedigreeId);
      }

    vtkIdType result = pedigrees->LookupValue(pedigreeId);
    if (result == -1)
      {
      return -1;
      }
    return helper->MakeDistributedId(myRank, result);
    }

  return pedigrees->LookupValue(pedigreeId);
}

//----------------------------------------------------------------------------
bool vtkGraph::CheckedShallowCopy(vtkGraph *g)
{
  if (!g)
    {
    return false;
    }
  bool valid = this->IsStructureValid(g);
  if (valid)
    {
    this->CopyInternal(g, false);
    }
  return valid;
}

//----------------------------------------------------------------------------
bool vtkGraph::CheckedDeepCopy(vtkGraph *g)
{
  if (!g)
    {
    return false;
    }
  bool valid = this->IsStructureValid(g);
  if (valid)
    {
    this->CopyInternal(g, true);
    }
  return valid;
}

//----------------------------------------------------------------------------
void vtkGraph::ShallowCopy(vtkDataObject *obj)
{
  vtkGraph *g = vtkGraph::SafeDownCast(obj);
  if (!g)
    {
    vtkErrorMacro("Can only shallow copy from vtkGraph subclass.");
    return;
    }
  bool valid = this->IsStructureValid(g);
  if (valid)
    {
    this->CopyInternal(g, false);
    }
  else
    {
    vtkErrorMacro("Invalid graph structure for this type of graph.");
    }
}

//----------------------------------------------------------------------------
void vtkGraph::DeepCopy(vtkDataObject *obj)
{
  vtkGraph *g = vtkGraph::SafeDownCast(obj);
  if (!g)
    {
    vtkErrorMacro("Can only shallow copy from vtkGraph subclass.");
    return;
    }
  bool valid = this->IsStructureValid(g);
  if (valid)
    {
    this->CopyInternal(g, true);
    }
  else
    {
    vtkErrorMacro("Invalid graph structure for this type of graph.");
    }
}

//----------------------------------------------------------------------------
void vtkGraph::CopyStructure(vtkGraph *g)
{
  // Copy on write.
  this->SetInternals(g->Internals);
  if (g->Points)
    {
    if (!this->Points)
      {
      this->Points = vtkPoints::New();
      }
    this->Points->ShallowCopy(g->Points);
    }
  else if (this->Points)
    {
    this->Points->Delete();
    this->Points = 0;
    }

  // Propagate information used by distributed graphs
  this->Information->Set
    (vtkDataObject::DATA_PIECE_NUMBER(),
     g->Information->Get(vtkDataObject::DATA_PIECE_NUMBER()));
  this->Information->Set
    (vtkDataObject::DATA_NUMBER_OF_PIECES(),
     g->Information->Get(vtkDataObject::DATA_NUMBER_OF_PIECES()));
}

//----------------------------------------------------------------------------
void vtkGraph::CopyInternal(vtkGraph *g, bool deep)
{
  if (deep)
    {
    vtkDataObject::DeepCopy(g);
    }
  else
    {
    vtkDataObject::ShallowCopy(g);
    }
  if (g->DistributedHelper)
    {
    if (!this->DistributedHelper)
      {
      this->SetDistributedGraphHelper(g->DistributedHelper->Clone());
      }
    }
  else if (this->DistributedHelper)
    {
    this->SetDistributedGraphHelper(0);
    }

  // Copy on write.
  this->SetInternals(g->Internals);

  if (deep)
    {
    this->EdgeData->DeepCopy(g->EdgeData);
    this->VertexData->DeepCopy(g->VertexData);
    this->DeepCopyEdgePoints(g);
    }
  else
    {
    this->EdgeData->ShallowCopy(g->EdgeData);
    this->VertexData->ShallowCopy(g->VertexData);
    this->ShallowCopyEdgePoints(g);
    }

  // Copy points
  if (g->Points && deep)
    {
    if (!this->Points)
      {
      this->Points = vtkPoints::New();
      }
    this->Points->DeepCopy(g->Points);
    }
  else
    {
    this->SetPoints(g->Points);
    }

  // Copy edge list
  if (g->EdgeList && deep)
    {
    if (!this->EdgeList)
      {
      this->EdgeList = vtkIdTypeArray::New();
      }
    this->EdgeList->DeepCopy(g->EdgeList);
    }
  else
    {
    this->SetEdgeList(g->EdgeList);
    }

  // Propagate information used by distributed graphs
  this->Information->Set
    (vtkDataObject::DATA_PIECE_NUMBER(),
     g->Information->Get(vtkDataObject::DATA_PIECE_NUMBER()));
  this->Information->Set
    (vtkDataObject::DATA_NUMBER_OF_PIECES(),
     g->Information->Get(vtkDataObject::DATA_NUMBER_OF_PIECES()));
}

//----------------------------------------------------------------------------
void vtkGraph::Squeeze()
{
  if ( this->Points )
    {
    this->Points->Squeeze();
    }
  this->EdgeData->Squeeze();
  this->VertexData->Squeeze();
}

//----------------------------------------------------------------------------
vtkGraph *vtkGraph::GetData(vtkInformation *info)
{
  return info? vtkGraph::SafeDownCast(info->Get(DATA_OBJECT())) : 0;
}

//----------------------------------------------------------------------------
vtkGraph *vtkGraph::GetData(vtkInformationVector *v, int i)
{
  return vtkGraph::GetData(v->GetInformationObject(i));
}

//----------------------------------------------------------------------------
vtkIdType vtkGraph::GetSourceVertex(vtkIdType e)
{
  if (vtkDistributedGraphHelper *helper = this->GetDistributedGraphHelper())
    {
    int myRank = this->Information->Get(vtkDataObject::DATA_PIECE_NUMBER());
    if (myRank != helper->GetEdgeOwner(e))
      {
        if (e != this->Internals->LastRemoteEdgeId)
          {
          helper->FindEdgeSourceAndTarget
            (e,
             &this->Internals->LastRemoteEdgeSource,
             &this->Internals->LastRemoteEdgeTarget);
          }

        return this->Internals->LastRemoteEdgeSource;
      }

    e = helper->GetEdgeIndex(e);
    }

  if (e < 0 || e >= this->GetNumberOfEdges())
    {
    vtkErrorMacro("Edge index out of range.");
    return -1;
    }
  if (!this->EdgeList)
    {
    this->BuildEdgeList();
    }
  return this->EdgeList->GetValue(2*e);
}

//----------------------------------------------------------------------------
vtkIdType vtkGraph::GetTargetVertex(vtkIdType e)
{
  if (vtkDistributedGraphHelper *helper = this->GetDistributedGraphHelper())
    {
    int myRank = this->Information->Get(vtkDataObject::DATA_PIECE_NUMBER());
    if (myRank != helper->GetEdgeOwner(e))
      {
        if (e != this->Internals->LastRemoteEdgeId)
          {
          this->Internals->LastRemoteEdgeId = e;
          helper->FindEdgeSourceAndTarget
            (e,
             &this->Internals->LastRemoteEdgeSource,
             &this->Internals->LastRemoteEdgeTarget);
          }

        return this->Internals->LastRemoteEdgeTarget;
      }

    e = helper->GetEdgeIndex(e);
    }

  if (e < 0 || e >= this->GetNumberOfEdges())
    {
    vtkErrorMacro("Edge index out of range.");
    return -1;
    }
  if (!this->EdgeList)
    {
    this->BuildEdgeList();
    }
  return this->EdgeList->GetValue(2*e  + 1);
}

//----------------------------------------------------------------------------
void vtkGraph::BuildEdgeList()
{
  if (this->EdgeList)
    {
    this->EdgeList->SetNumberOfTuples(this->GetNumberOfEdges());
    }
  else
    {
    this->EdgeList = vtkIdTypeArray::New();
    this->EdgeList->SetNumberOfComponents(2);
    this->EdgeList->SetNumberOfTuples(this->GetNumberOfEdges());
    }
  vtkEdgeListIterator* it = vtkEdgeListIterator::New();
  this->GetEdges(it);
  while (it->HasNext())
    {
    vtkEdgeType e = it->Next();
    this->EdgeList->SetValue(2*e.Id, e.Source);
    this->EdgeList->SetValue(2*e.Id + 1, e.Target);
    }
  it->Delete();
}

//----------------------------------------------------------------------------
void vtkGraph::SetEdgePoints(vtkIdType e, vtkIdType npts, double* pts)
{
  if (vtkDistributedGraphHelper *helper = this->GetDistributedGraphHelper())
    {
    int myRank = this->Information->Get(vtkDataObject::DATA_PIECE_NUMBER());
    if (myRank != helper->GetEdgeOwner(e))
      {
      vtkErrorMacro("vtkGraph cannot set edge points for a non-local vertex");
      return;
      }

    e = helper->GetEdgeIndex(e);
    }

  if (e < 0 || e > this->Internals->NumberOfEdges)
    {
    vtkErrorMacro("Invalid edge id.");
    return;
    }
  if (!this->EdgePoints)
    {
    this->EdgePoints = vtkGraphEdgePoints::New();
    }
  vtksys_stl::vector< vtksys_stl::vector<double> >::size_type numEdges = this->Internals->NumberOfEdges;
  if (this->EdgePoints->Storage.size() < numEdges)
    {
    this->EdgePoints->Storage.resize(numEdges);
    }
  this->EdgePoints->Storage[e].clear();
  for (vtkIdType i = 0; i < 3*npts; ++i, ++pts)
    {
    this->EdgePoints->Storage[e].push_back(*pts);
    }
}

//----------------------------------------------------------------------------
void vtkGraph::GetEdgePoints(vtkIdType e, vtkIdType& npts, double*& pts)
{
  if (vtkDistributedGraphHelper *helper = this->GetDistributedGraphHelper())
    {
    int myRank = this->Information->Get(vtkDataObject::DATA_PIECE_NUMBER());
    if (myRank != helper->GetEdgeOwner(e))
      {
      vtkErrorMacro("vtkGraph cannot retrieve edge points for a non-local vertex");
      return;
      }

    e = helper->GetEdgeIndex(e);
    }

  if (e < 0 || e > this->Internals->NumberOfEdges)
    {
    vtkErrorMacro("Invalid edge id.");
    return;
    }
  if (!this->EdgePoints)
    {
    npts = 0;
    pts = 0;
    return;
    }
  vtksys_stl::vector< vtksys_stl::vector<double> >::size_type numEdges = this->Internals->NumberOfEdges;
  if (this->EdgePoints->Storage.size() < numEdges)
    {
    this->EdgePoints->Storage.resize(numEdges);
    }
  npts = this->EdgePoints->Storage[e].size() / 3;
  if (npts > 0)
    {
    pts = &this->EdgePoints->Storage[e][0];
    }
  else
    {
    pts = 0;
    }
}

//----------------------------------------------------------------------------
vtkIdType vtkGraph::GetNumberOfEdgePoints(vtkIdType e)
{
  if (vtkDistributedGraphHelper *helper = this->GetDistributedGraphHelper())
    {
    int myRank = this->Information->Get(vtkDataObject::DATA_PIECE_NUMBER());
    if (myRank != helper->GetEdgeOwner(e))
      {
      vtkErrorMacro("vtkGraph cannot retrieve edge points for a non-local vertex");
      return 0;
      }

    e = helper->GetEdgeIndex(e);
    }

  if (e < 0 || e > this->Internals->NumberOfEdges)
    {
    vtkErrorMacro("Invalid edge id.");
    return 0;
    }
  if (!this->EdgePoints)
    {
    return 0;
    }
  vtksys_stl::vector< vtksys_stl::vector<double> >::size_type numEdges = this->Internals->NumberOfEdges;
  if (this->EdgePoints->Storage.size() < numEdges)
    {
    this->EdgePoints->Storage.resize(numEdges);
    }
  return this->EdgePoints->Storage[e].size() / 3;
}

//----------------------------------------------------------------------------
double* vtkGraph::GetEdgePoint(vtkIdType e, vtkIdType i)
{
  if (vtkDistributedGraphHelper *helper = this->GetDistributedGraphHelper())
    {
    int myRank = this->Information->Get(vtkDataObject::DATA_PIECE_NUMBER());
    if (myRank != helper->GetEdgeOwner(e))
      {
      vtkErrorMacro("vtkGraph cannot receive edge points for a non-local vertex");
      return 0;
      }

    e = helper->GetEdgeIndex(e);
    }

  if (e < 0 || e > this->Internals->NumberOfEdges)
    {
    vtkErrorMacro("Invalid edge id.");
    return 0;
    }
  if (!this->EdgePoints)
    {
    this->EdgePoints = vtkGraphEdgePoints::New();
    }
  vtksys_stl::vector< vtksys_stl::vector<double> >::size_type numEdges = this->Internals->NumberOfEdges;
  if (this->EdgePoints->Storage.size() < numEdges)
    {
    this->EdgePoints->Storage.resize(numEdges);
    }
  vtkIdType npts = this->EdgePoints->Storage[e].size() / 3;
  if (i >= npts)
    {
    vtkErrorMacro("Edge point index out of range.");
    return 0;
    }
  return &this->EdgePoints->Storage[e][3*i];
}

//----------------------------------------------------------------------------
void vtkGraph::SetEdgePoint(vtkIdType e, vtkIdType i, double x[3])
{
  if (vtkDistributedGraphHelper *helper = this->GetDistributedGraphHelper())
    {
    int myRank = this->Information->Get(vtkDataObject::DATA_PIECE_NUMBER());
    if (myRank != helper->GetEdgeOwner(e))
      {
      vtkErrorMacro("vtkGraph cannot set edge points for a non-local vertex");
      return;
      }

    e = helper->GetEdgeIndex(e);
    }

  if (e < 0 || e > this->Internals->NumberOfEdges)
    {
    vtkErrorMacro("Invalid edge id.");
    return;
    }
  if (!this->EdgePoints)
    {
    this->EdgePoints = vtkGraphEdgePoints::New();
    }
  vtksys_stl::vector< vtksys_stl::vector<double> >::size_type numEdges = this->Internals->NumberOfEdges;
  if (this->EdgePoints->Storage.size() < numEdges)
    {
    this->EdgePoints->Storage.resize(numEdges);
    }
  vtkIdType npts = this->EdgePoints->Storage[e].size() / 3;
  if (i >= npts)
    {
    vtkErrorMacro("Edge point index out of range.");
    return;
    }
  for (int c = 0; c < 3; ++c)
    {
    this->EdgePoints->Storage[e][3*i + c] = x[c];
    }
}

//----------------------------------------------------------------------------
void vtkGraph::ClearEdgePoints(vtkIdType e)
{
  if (vtkDistributedGraphHelper *helper = this->GetDistributedGraphHelper())
    {
    int myRank = this->Information->Get(vtkDataObject::DATA_PIECE_NUMBER());
    if (myRank != helper->GetEdgeOwner(e))
      {
      vtkErrorMacro("vtkGraph cannot clear edge points for a non-local vertex");
      return;
      }

    e = helper->GetEdgeIndex(e);
    }

  if (e < 0 || e > this->Internals->NumberOfEdges)
    {
    vtkErrorMacro("Invalid edge id.");
    return;
    }
  if (!this->EdgePoints)
    {
    this->EdgePoints = vtkGraphEdgePoints::New();
    }
  vtksys_stl::vector< vtksys_stl::vector<double> >::size_type numEdges = this->Internals->NumberOfEdges;
  if (this->EdgePoints->Storage.size() < numEdges)
    {
    this->EdgePoints->Storage.resize(numEdges);
    }
  this->EdgePoints->Storage[e].clear();
}

//----------------------------------------------------------------------------
void vtkGraph::AddEdgePoint(vtkIdType e, double x[3])
{
  if (vtkDistributedGraphHelper *helper = this->GetDistributedGraphHelper())
    {
    int myRank = this->Information->Get(vtkDataObject::DATA_PIECE_NUMBER());
    if (myRank != helper->GetEdgeOwner(e))
      {
      vtkErrorMacro("vtkGraph cannot set edge points for a non-local vertex");
      return;
      }

    e = helper->GetEdgeIndex(e);
    }
  if (e < 0 || e > this->Internals->NumberOfEdges)
    {
    vtkErrorMacro("Invalid edge id.");
    return;
    }
  if (!this->EdgePoints)
    {
    this->EdgePoints = vtkGraphEdgePoints::New();
    }
  vtksys_stl::vector< vtksys_stl::vector<double> >::size_type numEdges = this->Internals->NumberOfEdges;
  if (this->EdgePoints->Storage.size() < numEdges)
    {
    this->EdgePoints->Storage.resize(numEdges);
    }
  for (int c = 0; c < 3; ++c)
    {
    this->EdgePoints->Storage[e].push_back(x[c]);
    }
}

//----------------------------------------------------------------------------
void vtkGraph::ShallowCopyEdgePoints(vtkGraph* g)
{
  this->SetEdgePoints(g->EdgePoints);
}

//----------------------------------------------------------------------------
void vtkGraph::DeepCopyEdgePoints(vtkGraph* g)
{
  if (g->EdgePoints)
    {
    if (!this->EdgePoints)
      {
      this->EdgePoints = vtkGraphEdgePoints::New();
      }
    this->EdgePoints->Storage = g->EdgePoints->Storage;
    }
  else
    {
    this->SetEdgePoints(0);
    }
}

//----------------------------------------------------------------------------
void vtkGraph::GetInducedEdges(vtkIdTypeArray *verts, vtkIdTypeArray *edges)
{
  edges->Initialize();
  if (this->GetDistributedGraphHelper())
    {
    vtkErrorMacro("Cannot get induced edges on a distributed graph.");
    return;
    }
  vtkSmartPointer<vtkEdgeListIterator> edgeIter =
    vtkSmartPointer<vtkEdgeListIterator>::New();
  this->GetEdges(edgeIter);
  while (edgeIter->HasNext())
    {
    vtkEdgeType e = edgeIter->Next();
    if (verts->LookupValue(e.Source) >= 0 &&
        verts->LookupValue(e.Target) >= 0)
      {
      edges->InsertNextValue(e.Id);
      }
    }
}

//----------------------------------------------------------------------------
void vtkGraph::AddVertexInternal(vtkVariantArray *propertyArr,
                                 vtkIdType *vertex)
{
  this->ForceOwnership();

  vtkDistributedGraphHelper *helper = this->GetDistributedGraphHelper();

  if (propertyArr)      // Add/replace vertex properties if passed in
    {
    vtkAbstractArray *peds = this->GetVertexData()->GetPedigreeIds();
    // If the properties include pedigreeIds, we need to see if this
    // pedigree already exists and, if so, simply update its properties.
    if (peds)
      {
      // Get the array index associated with pedIds.
      vtkIdType pedIdx = this->GetVertexData()->SetPedigreeIds(peds);
      vtkVariant pedigreeId = propertyArr->GetValue(pedIdx);
      if (helper)
        {
        vtkIdType myRank
          = this->Information->Get(vtkDataObject::DATA_PIECE_NUMBER());
        if (helper->GetVertexOwnerByPedigreeId(pedigreeId) != myRank)
          {
          helper->AddVertexInternal(propertyArr, vertex);
          return;
          }
        }

      vtkIdType vertexIndex = this->FindVertex(pedigreeId);

      // FindVertex returns distributed ids for parallel graphs, must account
      // for this prior to the range check.
      if (helper)
        {
        vertexIndex = helper->GetVertexIndex(vertexIndex);
        }
      if (vertexIndex != -1 && vertexIndex < this->GetNumberOfVertices())
        {
        for (int iprop=0; iprop<propertyArr->GetNumberOfValues(); iprop++)
          {
          vtkAbstractArray* arr = this->GetVertexData()->GetAbstractArray(iprop);
          arr->InsertVariantValue(vertexIndex, propertyArr->GetValue(iprop));
          }
        if (vertex)
          {
          *vertex = vertexIndex;
          }
        return;
        }

      this->Internals->Adjacency.push_back(vtkVertexAdjacencyList());  // Add a new (local) vertex
      vtkIdType index = this->Internals->Adjacency.size() - 1;

      vtkDataSetAttributes *vertexData = this->GetVertexData();
      int numProps = propertyArr->GetNumberOfValues();
      assert(numProps == vertexData->GetNumberOfArrays());
      for (int iprop=0; iprop<numProps; iprop++)
        {
        vtkAbstractArray* arr = vertexData->GetAbstractArray(iprop);
        arr->InsertVariantValue(index, propertyArr->GetValue(iprop));
        }
      }  // end if (peds)
    //----------------------------------------------------------------
    else   // We have propArr, but not pedIds - just add the propArr
      {
      this->Internals->Adjacency.push_back(vtkVertexAdjacencyList());
      vtkIdType index = this->Internals->Adjacency.size() - 1;

      vtkDataSetAttributes *vertexData = this->GetVertexData();
      int numProps = propertyArr->GetNumberOfValues();
      assert(numProps == vertexData->GetNumberOfArrays());
      for (int iprop=0; iprop<numProps; iprop++)
        {
        vtkAbstractArray* arr = vertexData->GetAbstractArray(iprop);
        arr->InsertVariantValue(index, propertyArr->GetValue(iprop));
        }
      }
    }
  else  // No properties, just add a new vertex
    {
    this->Internals->Adjacency.push_back(vtkVertexAdjacencyList());
    }

  if (vertex)
    {
    if (helper)
      {
      *vertex = helper->MakeDistributedId
                  (this->Information->Get(vtkDataObject::DATA_PIECE_NUMBER()),
                   this->Internals->Adjacency.size() - 1);
      }
    else
      {
      *vertex = this->Internals->Adjacency.size() - 1;
      }
    }
}
//----------------------------------------------------------------------------
void vtkGraph::AddVertexInternal(const vtkVariant& pedigreeId,
                                 vtkIdType *vertex)
{
  // Add vertex V, given a pedId:
  //   1) if a dist'd G and this proc doesn't own V, add it (via helper class) and RETURN.
  //   2) if V already exists for this pedId, RETURN it.
  //   3) add V locally and insert its pedId
  vtkDistributedGraphHelper *helper = this->GetDistributedGraphHelper();
  if (helper)
    {
    vtkIdType myRank
      = this->Information->Get(vtkDataObject::DATA_PIECE_NUMBER());
    if (helper->GetVertexOwnerByPedigreeId(pedigreeId) != myRank)
      {
      helper->AddVertexInternal(pedigreeId, vertex);
      return;
      }
    }

  vtkIdType vertexIndex = this->FindVertex(pedigreeId);

  // If we're on a distributed graph, FindVertex returns a distributed-id,
  // must account for that.
  if(helper)
    {
    vertexIndex = helper->GetVertexIndex(vertexIndex);
    }
  if (vertexIndex != -1 && vertexIndex < this->GetNumberOfVertices())
    {
    // We found this vertex; nothing more to do.
    if (vertex)
      {
      *vertex = vertexIndex;
      }
    return ;
    }

  // Add the vertex locally
  this->ForceOwnership();
  vtkIdType v;
  this->AddVertexInternal(0, &v);
  if (vertex)
    {
    *vertex = v;
    }

  // Add the pedigree ID of the vertex
  vtkAbstractArray *pedigrees = this->GetVertexData()->GetPedigreeIds();
  if (pedigrees == NULL)
    {
    vtkErrorMacro("Added a vertex with a pedigree ID to a vtkGraph with no pedigree ID array");
    return;
    }

  vtkIdType index = v;
  if (helper)
    {
    index = helper->GetVertexIndex(v);
    }

  pedigrees->InsertVariantValue(index, pedigreeId);
}
//----------------------------------------------------------------------------
void vtkGraph::AddEdgeInternal(vtkIdType u, vtkIdType v, bool directed,
                               vtkVariantArray *propertyArr, vtkEdgeType *edge)
{
  this->ForceOwnership();
  if (this->DistributedHelper)
    {
    this->DistributedHelper->AddEdgeInternal(u, v, directed,
                                             propertyArr, edge);
    return;
    }

  if (u >= this->GetNumberOfVertices() || v >= this->GetNumberOfVertices())
    {
    vtkErrorMacro(<< "Vertex index out of range");
    return;
    }

  vtkIdType edgeId = this->Internals->NumberOfEdges;
  vtkIdType edgeIndex = edgeId;
  this->Internals->NumberOfEdges++;
  this->Internals->Adjacency[u].OutEdges.push_back(vtkOutEdgeType(v, edgeId));
  if (directed)
    {
    this->Internals->Adjacency[v].InEdges.push_back(vtkInEdgeType(u, edgeId));
    }
  else if (u != v)
    {
    // Avoid storing self-loops twice in undirected graphs.
    this->Internals->Adjacency[v].OutEdges.push_back(vtkOutEdgeType(u, edgeId));
    }

  if (this->EdgeList)
    {
    this->EdgeList->InsertNextValue(u);
    this->EdgeList->InsertNextValue(v);
    }

  if (edge)
    {
    *edge = vtkEdgeType(u, v, edgeId);
    }

  if (propertyArr)
    {
    // Insert edge properties
    vtkDataSetAttributes *edgeData = this->GetEdgeData();
    int numProps = propertyArr->GetNumberOfValues();
    assert(numProps == edgeData->GetNumberOfArrays());
    for (int iprop=0; iprop<numProps; iprop++)
      {
      vtkAbstractArray* array = edgeData->GetAbstractArray(iprop);
      array->InsertVariantValue(edgeIndex, propertyArr->GetValue(iprop));
      }
    }
}

//----------------------------------------------------------------------------
void vtkGraph::AddEdgeInternal(const vtkVariant& uPedigreeId, vtkIdType v,
                               bool directed, vtkVariantArray *propertyArr,
                               vtkEdgeType *edge)
{
  this->ForceOwnership();
  if (this->DistributedHelper)
    {
    this->DistributedHelper->AddEdgeInternal(uPedigreeId, v,
                                                        directed, propertyArr,
                                                        edge);
    return;
    }

  vtkIdType u;
  this->AddVertexInternal(uPedigreeId, &u);
  this->AddEdgeInternal(u, v, directed, propertyArr, edge);
}

//----------------------------------------------------------------------------
void vtkGraph::AddEdgeInternal(vtkIdType u, const vtkVariant& vPedigreeId,
                               bool directed, vtkVariantArray *propertyArr,
                               vtkEdgeType *edge)
{
  this->ForceOwnership();
  if (this->DistributedHelper)
    {
    this->DistributedHelper->AddEdgeInternal(u, vPedigreeId,
                                                        directed, propertyArr,
                                                        edge);
    return;
    }

  vtkIdType v;
  this->AddVertexInternal(vPedigreeId, &v);
  this->AddEdgeInternal(u, v, directed, propertyArr, edge);
}

//----------------------------------------------------------------------------
void vtkGraph::AddEdgeInternal(const vtkVariant& uPedigreeId,
                               const vtkVariant& vPedigreeId,
                               bool directed,
                               vtkVariantArray *propertyArr,
                               vtkEdgeType *edge)
{
  this->ForceOwnership();
  if (this->DistributedHelper)
    {
    this->DistributedHelper->AddEdgeInternal(uPedigreeId,
                                             vPedigreeId, directed,
                                             propertyArr, edge);
    return;
    }

  vtkIdType u, v;
  this->AddVertexInternal(uPedigreeId, &u);
  this->AddVertexInternal(vPedigreeId, &v);
  this->AddEdgeInternal(u, v, directed, propertyArr, edge);
}

//----------------------------------------------------------------------------
void vtkGraph::RemoveVertexInternal(vtkIdType v, bool directed)
{
  if (this->DistributedHelper)
    {
    vtkErrorMacro("Cannot remove vertices in a distributed graph.");
    return;
    }
  if (v < 0 || v >= this->GetNumberOfVertices())
    {
    return;
    }

  this->ForceOwnership();
  this->BuildEdgeList(); // This function assumes the edge list is created.

  // Remove connected edges
  vtksys_stl::set<vtkIdType> edges;
  vtksys_stl::vector<vtkOutEdgeType>::iterator oi, oiEnd;
  oiEnd = this->Internals->Adjacency[v].OutEdges.end();
  for (oi = this->Internals->Adjacency[v].OutEdges.begin(); oi != oiEnd; ++oi)
    {
    edges.insert(oi->Id);
    }
  vtksys_stl::vector<vtkInEdgeType>::iterator ii, iiEnd;
  iiEnd = this->Internals->Adjacency[v].InEdges.end();
  for (ii = this->Internals->Adjacency[v].InEdges.begin(); ii != iiEnd; ++ii)
    {
    edges.insert(ii->Id);
    }
  vtksys_stl::set<vtkIdType>::reverse_iterator ei, eiEnd;
  eiEnd = edges.rend();
  for (ei = edges.rbegin(); ei != eiEnd; ++ei)
    {
    this->RemoveEdgeInternal(*ei, directed);
    }

  // Replace all occurences of last vertex id with v
  vtkIdType lv = this->GetNumberOfVertices() - 1;
  this->Internals->Adjacency[v] = this->Internals->Adjacency[lv];
  oiEnd = this->Internals->Adjacency[v].OutEdges.end();
  for (oi = this->Internals->Adjacency[v].OutEdges.begin(); oi != oiEnd; ++oi)
    {
    if (oi->Target == lv)
      {
      oi->Target = v;
      this->EdgeList->SetValue(2*oi->Id + 1, v);
      continue;
      }
    if (directed)
      {
      iiEnd = this->Internals->Adjacency[oi->Target].InEdges.end();
      for (ii = this->Internals->Adjacency[oi->Target].InEdges.begin(); ii != iiEnd; ++ii)
        {
        if (ii->Source == lv)
          {
          ii->Source = v;
          this->EdgeList->SetValue(2*ii->Id + 0, v);
          }
        }
      }
    else
      {
      vtksys_stl::vector<vtkOutEdgeType>::iterator oi2, oi2End;
      oi2End = this->Internals->Adjacency[oi->Target].OutEdges.end();
      for (oi2 = this->Internals->Adjacency[oi->Target].OutEdges.begin(); oi2 != oi2End; ++oi2)
        {
        if (oi2->Target == lv)
          {
          oi2->Target = v;
          this->EdgeList->SetValue(2*oi2->Id + 1, v);
          }
        }
      }
    }

  if (directed)
    {
    iiEnd = this->Internals->Adjacency[v].InEdges.end();
    for (ii = this->Internals->Adjacency[v].InEdges.begin(); ii != iiEnd; ++ii)
      {
      if (ii->Source == lv)
        {
        ii->Source = v;
        this->EdgeList->SetValue(2*ii->Id + 0, v);
        continue;
        }
      oiEnd = this->Internals->Adjacency[ii->Source].OutEdges.end();
      for (oi = this->Internals->Adjacency[ii->Source].OutEdges.begin(); oi != oiEnd; ++oi)
        {
        if (oi->Target == lv)
          {
          oi->Target = v;
          this->EdgeList->SetValue(2*oi->Id + 1, v);
          }
        }
      }
    }

  // Update properties
  vtkDataSetAttributes* vd = this->GetVertexData();
  for (int i = 0; i < vd->GetNumberOfArrays(); ++i)
    {
    vtkAbstractArray* arr = vd->GetAbstractArray(i);
    arr->SetTuple(v, lv, arr);
    arr->SetNumberOfTuples(lv);
    }

  // Update points
  if (this->Points)
    {
    double x[3];
    this->Points->GetPoint(lv, x);
    this->Points->SetPoint(v, x);
    this->Points->SetNumberOfPoints(lv);
    }

  this->Internals->Adjacency.pop_back();
}

//----------------------------------------------------------------------------
void vtkGraph::RemoveEdgeInternal(vtkIdType e, bool directed)
{
  if (this->DistributedHelper)
    {
    vtkErrorMacro("Cannot remove edges in a distributed graph.");
    return;
    }
  if (e < 0 || e >= this->GetNumberOfEdges())
    {
    return;
    }
  this->ForceOwnership();
  vtkIdType u = this->GetSourceVertex(e);
  vtkIdType v = this->GetTargetVertex(e);

  this->Internals->RemoveEdgeFromOutList(e, this->Internals->Adjacency[u].OutEdges);
  if (directed)
    {
    this->Internals->RemoveEdgeFromInList(e, this->Internals->Adjacency[v].InEdges);
    }
  else if (u != v)
    {
    this->Internals->RemoveEdgeFromOutList(e, this->Internals->Adjacency[v].OutEdges);
    }

  // Replace last edge id with e
  vtkIdType le = this->GetNumberOfEdges() - 1;
  vtkIdType lu = this->GetSourceVertex(le);
  vtkIdType lv = this->GetTargetVertex(le);
  this->Internals->ReplaceEdgeFromOutList(le, e, this->Internals->Adjacency[lu].OutEdges);
  if (directed)
    {
    this->Internals->ReplaceEdgeFromInList(le, e, this->Internals->Adjacency[lv].InEdges);
    }
  else if (lu != lv)
    {
    this->Internals->ReplaceEdgeFromOutList(le, e, this->Internals->Adjacency[lv].OutEdges);
    }

  // Update edge list
  this->EdgeList->SetValue(2*e + 0, lu);
  this->EdgeList->SetValue(2*e + 1, lv);
  this->EdgeList->SetNumberOfTuples(le);

  // Update properties
  vtkDataSetAttributes* ed = this->GetEdgeData();
  for (int i = 0; i < ed->GetNumberOfArrays(); ++i)
    {
    vtkAbstractArray* arr = ed->GetAbstractArray(i);
    arr->SetTuple(e, le, arr);
    arr->SetNumberOfTuples(le);
    }

  // Update edge points
  if (this->EdgePoints)
    {
    this->EdgePoints->Storage[e] = this->EdgePoints->Storage[le];
    this->EdgePoints->Storage.pop_back();
    }

  this->Internals->NumberOfEdges--;
}

//----------------------------------------------------------------------------
void vtkGraph::RemoveVerticesInternal(vtkIdTypeArray* arr, bool directed)
{
  if (this->DistributedHelper)
    {
    vtkErrorMacro("Cannot remove vertices in a distributed graph.");
    return;
    }
  if (!arr)
    {
    return;
    }

  // Sort
  vtkIdType* p = arr->GetPointer(0);
  vtkIdType numVert = arr->GetNumberOfTuples();
  vtksys_stl::sort(p, p + numVert);

  // Collect all edges to be removed
  vtksys_stl::set<vtkIdType> edges;
  for (vtkIdType vind = 0; vind < numVert; ++vind)
    {
    vtkIdType v = p[vind];
    vtksys_stl::vector<vtkOutEdgeType>::iterator oi, oiEnd;
    oiEnd = this->Internals->Adjacency[v].OutEdges.end();
    for (oi = this->Internals->Adjacency[v].OutEdges.begin(); oi != oiEnd; ++oi)
      {
      edges.insert(oi->Id);
      }
    vtksys_stl::vector<vtkInEdgeType>::iterator ii, iiEnd;
    iiEnd = this->Internals->Adjacency[v].InEdges.end();
    for (ii = this->Internals->Adjacency[v].InEdges.begin(); ii != iiEnd; ++ii)
      {
      edges.insert(ii->Id);
      }
    }

  // Remove edges in reverse index order
  vtksys_stl::set<vtkIdType>::reverse_iterator ei, eiEnd;
  eiEnd = edges.rend();
  for (ei = edges.rbegin(); ei != eiEnd; ++ei)
    {
    this->RemoveEdgeInternal(*ei, directed);
    }

  // Remove vertices in reverse index order
  for (vtkIdType vind = numVert - 1; vind >= 0; --vind)
    {
    this->RemoveVertexInternal(p[vind], directed);
    }
}

//----------------------------------------------------------------------------
void vtkGraph::RemoveEdgesInternal(vtkIdTypeArray* arr, bool directed)
{
  if (this->DistributedHelper)
    {
    vtkErrorMacro("Cannot remove edges in a distributed graph.");
    return;
    }
  if (!arr)
    {
    return;
    }

  // Sort
  vtkIdType* p = arr->GetPointer(0);
  vtkIdType numEdges = arr->GetNumberOfTuples();
  vtksys_stl::sort(p, p + numEdges);

  // Edges vertices in reverse index order
  for (vtkIdType eind = numEdges - 1; eind >= 0; --eind)
    {
    this->RemoveEdgeInternal(p[eind], directed);
    }
}

//----------------------------------------------------------------------------
void vtkGraph::ReorderOutVertices(vtkIdType v, vtkIdTypeArray *vertices)
{
  vtkIdType index = v;
  if (vtkDistributedGraphHelper *helper = this->GetDistributedGraphHelper())
    {
    int myRank = this->Information->Get(vtkDataObject::DATA_PIECE_NUMBER());
    if (myRank != helper->GetVertexOwner(v))
      {
      vtkErrorMacro("vtkGraph cannot reorder the out vertices for a non-local vertex");
      return;
      }

    index = helper->GetVertexIndex(v);
    }

  this->ForceOwnership();
  vtksys_stl::vector<vtkOutEdgeType> outEdges;
  vtksys_stl::vector<vtkOutEdgeType>::iterator it, itEnd;
  itEnd = this->Internals->Adjacency[index].OutEdges.end();
  for (vtkIdType i = 0; i < vertices->GetNumberOfTuples(); ++i)
    {
    vtkIdType vert = vertices->GetValue(i);
    // Find the matching edge
    for (it = this->Internals->Adjacency[index].OutEdges.begin(); it != itEnd; ++it)
      {
      if (it->Target == vert)
        {
        outEdges.push_back(*it);
        break;
        }
      }
    }
  if (outEdges.size() != this->Internals->Adjacency[index].OutEdges.size())
    {
    vtkErrorMacro("Invalid reorder list.");
    return;
    }
  this->Internals->Adjacency[index].OutEdges = outEdges;
}

//----------------------------------------------------------------------------
bool vtkGraph::IsSameStructure(vtkGraph *other)
{
  return (this->Internals == other->Internals);
}

//----------------------------------------------------------------------------
vtkGraphInternals* vtkGraph::GetGraphInternals(bool modifying)
{
  if (modifying)
    {
    this->ForceOwnership();
    }
  return this->Internals;
}

//----------------------------------------------------------------------------
void vtkGraph::ForceOwnership()
{
  // If the reference count == 1, we own it and can change it.
  // If the reference count > 1, we must make a copy to avoid
  // changing the structure of other graphs.
  if (this->Internals->GetReferenceCount() > 1)
    {
    vtkGraphInternals *internals = vtkGraphInternals::New();
    internals->Adjacency = this->Internals->Adjacency;
    internals->NumberOfEdges = this->Internals->NumberOfEdges;
    this->SetInternals(internals);
    internals->Delete();
    }
  if (this->EdgePoints && this->EdgePoints->GetReferenceCount() > 1)
    {
    vtkGraphEdgePoints *oldEdgePoints = this->EdgePoints;
    vtkGraphEdgePoints *edgePoints = vtkGraphEdgePoints::New();
    edgePoints->Storage = oldEdgePoints->Storage;
    this->EdgePoints = edgePoints;
    oldEdgePoints->Delete();
    }
}

//----------------------------------------------------------------------------
vtkFieldData* vtkGraph::GetAttributesAsFieldData(int type)
{
  switch(type)
    {
    case VERTEX:
      return this->GetVertexData();
      break;
    case EDGE:
      return this->GetEdgeData();
      break;
    }
  return this->Superclass::GetAttributesAsFieldData(type);
}

//----------------------------------------------------------------------------
vtkIdType vtkGraph::GetNumberOfElements(int type)
{
  switch (type)
    {
    case VERTEX:
      return this->GetNumberOfVertices();
      break;
    case EDGE:
      return this->GetNumberOfEdges();
      break;
    }
  return this->Superclass::GetNumberOfElements(type);;
}

//----------------------------------------------------------------------------
void vtkGraph::Dump()
{
  cout << "vertex adjacency:" << endl;
  for (size_t v = 0; v < this->Internals->Adjacency.size(); ++v)
    {
    cout << v << " (out): ";
    for (size_t eind = 0; eind < this->Internals->Adjacency[v].OutEdges.size(); ++eind)
      {
      cout << "[" << this->Internals->Adjacency[v].OutEdges[eind].Id
           << "," << this->Internals->Adjacency[v].OutEdges[eind].Target << "]";
      }
    cout << " (in): ";
    for (size_t eind = 0; eind < this->Internals->Adjacency[v].InEdges.size(); ++eind)
      {
      cout << "[" << this->Internals->Adjacency[v].InEdges[eind].Id
           << "," << this->Internals->Adjacency[v].InEdges[eind].Source << "]";
      }
    cout << endl;
    }
  if (this->EdgeList)
    {
    cout << "edge list:" << endl;
    for (vtkIdType e = 0; e < this->EdgeList->GetNumberOfTuples(); ++e)
      {
      cout << e << ": (" << this->EdgeList->GetValue(2*e + 0) << ","
           << this->EdgeList->GetValue(2*e + 1) << ")" << endl;
      }
    cout << endl;
    }
}

//----------------------------------------------------------------------------
void vtkGraph::PrintSelf(ostream& os, vtkIndent indent)
{
  this->Superclass::PrintSelf(os,indent);
  os << indent << "VertexData: " << (this->VertexData ? "" : "(none)") << endl;
  if (this->VertexData)
    {
    this->VertexData->PrintSelf(os, indent.GetNextIndent());
    }
  os << indent << "EdgeData: " << (this->EdgeData ? "" : "(none)") << endl;
  if (this->EdgeData)
    {
    this->EdgeData->PrintSelf(os, indent.GetNextIndent());
    }
  if (this->Internals)
    {
    os << indent << "DistributedHelper: "
       << (this->DistributedHelper ? "" : "(none)") << endl;
    if (this->DistributedHelper)
      {
      this->DistributedHelper->PrintSelf(os, indent.GetNextIndent());
      }
    }
}

//----------------------------------------------------------------------------
// Supporting operators
//----------------------------------------------------------------------------

//----------------------------------------------------------------------------
bool operator==(vtkEdgeBase e1, vtkEdgeBase e2)
{
  return e1.Id == e2.Id;
}

//----------------------------------------------------------------------------
bool operator!=(vtkEdgeBase e1, vtkEdgeBase e2)
{
  return e1.Id != e2.Id;
}

//----------------------------------------------------------------------------
ostream& operator<<(ostream& out, vtkEdgeBase e)
{
  return out << e.Id;
}