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

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

#include "vtkDataSetAttributes.h"
#include "vtkEdgeListIterator.h"
#include "vtkGraph.h"
#include "vtkInformation.h"
#include "vtkInformationVector.h"
#include "vtkMutableDirectedGraph.h"
#include "vtkMutableGraphHelper.h"
#include "vtkMutableUndirectedGraph.h"
#include "vtkObjectFactory.h"
#include "vtkPoints.h"
#include "vtkSmartPointer.h"

#include <vector>

vtkStandardNewMacro(vtkRemoveIsolatedVertices);
//------------------------------------------------------------------------------
vtkRemoveIsolatedVertices::vtkRemoveIsolatedVertices() = default;

//------------------------------------------------------------------------------
vtkRemoveIsolatedVertices::~vtkRemoveIsolatedVertices() = default;

//------------------------------------------------------------------------------
int vtkRemoveIsolatedVertices::RequestData(vtkInformation* vtkNotUsed(request),
  vtkInformationVector** inputVector, vtkInformationVector* outputVector)
{
  vtkGraph* input = vtkGraph::GetData(inputVector[0]);

  // Set up our mutable graph helper.
  vtkSmartPointer<vtkMutableGraphHelper> builder = vtkSmartPointer<vtkMutableGraphHelper>::New();
  if (vtkDirectedGraph::SafeDownCast(input))
  {
    vtkSmartPointer<vtkMutableDirectedGraph> dir = vtkSmartPointer<vtkMutableDirectedGraph>::New();
    builder->SetGraph(dir);
  }
  else
  {
    vtkSmartPointer<vtkMutableUndirectedGraph> undir =
      vtkSmartPointer<vtkMutableUndirectedGraph>::New();
    builder->SetGraph(undir);
  }

  // Initialize edge data, vertex data, and points.
  vtkDataSetAttributes* inputEdgeData = input->GetEdgeData();
  vtkDataSetAttributes* builderEdgeData = builder->GetGraph()->GetEdgeData();
  builderEdgeData->CopyAllocate(inputEdgeData);

  vtkDataSetAttributes* inputVertData = input->GetVertexData();
  vtkDataSetAttributes* builderVertData = builder->GetGraph()->GetVertexData();
  builderVertData->CopyAllocate(inputVertData);

  vtkPoints* inputPoints = input->GetPoints();
  vtkSmartPointer<vtkPoints> builderPoints = vtkSmartPointer<vtkPoints>::New();
  builder->GetGraph()->SetPoints(builderPoints);

  // Vector keeps track of mapping of input vertex ids to
  // output vertex ids.
  vtkIdType numVert = input->GetNumberOfVertices();
  std::vector<int> outputVertex(numVert, -1);

  vtkSmartPointer<vtkEdgeListIterator> edgeIter = vtkSmartPointer<vtkEdgeListIterator>::New();
  input->GetEdges(edgeIter);
  while (edgeIter->HasNext())
  {
    vtkEdgeType e = edgeIter->Next();
    vtkIdType source = outputVertex[e.Source];
    if (source < 0)
    {
      source = builder->AddVertex();
      outputVertex[e.Source] = source;
      builderVertData->CopyData(inputVertData, e.Source, source);
      builderPoints->InsertNextPoint(inputPoints->GetPoint(e.Source));
    }
    vtkIdType target = outputVertex[e.Target];
    if (target < 0)
    {
      target = builder->AddVertex();
      outputVertex[e.Target] = target;
      builderVertData->CopyData(inputVertData, e.Target, target);
      builderPoints->InsertNextPoint(inputPoints->GetPoint(e.Target));
    }
    vtkEdgeType outputEdge = builder->AddEdge(source, target);
    builderEdgeData->CopyData(inputEdgeData, e.Id, outputEdge.Id);
  }

  // Pass constructed graph to output.
  vtkGraph* output = vtkGraph::GetData(outputVector);
  output->ShallowCopy(builder->GetGraph());
  output->GetFieldData()->PassData(input->GetFieldData());

  // Clean up
  output->Squeeze();

  return 1;
}

//------------------------------------------------------------------------------
void vtkRemoveIsolatedVertices::PrintSelf(ostream& os, vtkIndent indent)
{
  this->Superclass::PrintSelf(os, indent);
}