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

  Program:   Visualization Toolkit
  Module:    $RCSfile: vtkDIMACSGraphReader.h,v $

  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 (c) Sandia Corporation
 See Copyright.txt or http://www.paraview.org/HTML/Copyright.html for details.
----------------------------------------------------------------------------*/

#include "vtkDIMACSGraphReader.h"

#include "vtkExecutive.h"
#include "vtkCellData.h"
#include "vtkIntArray.h"
#include "vtkGraph.h"
#include "vtkMutableUndirectedGraph.h"
#include "vtkMutableDirectedGraph.h"
#include "vtksys/SystemTools.hxx"
#include "vtkObjectFactory.h"
#include "vtkPointData.h"
#include "vtkSmartPointer.h"
#include "vtkStringArray.h"
#include "vtkIntArray.h"

#include <vtksys/ios/fstream>
#include <vtksys/ios/sstream>
#include <vtksys/ios/iostream>
using vtksys_ios::ifstream;
using vtksys_ios::istringstream;

#define VTK_CREATE(type, name) \
  vtkSmartPointer<type> name = vtkSmartPointer<type>::New()

typedef enum problemTypes { GENERIC, COLORING, MAXFLOW } problemTypes;

vtkStandardNewMacro(vtkDIMACSGraphReader);

vtkDIMACSGraphReader::vtkDIMACSGraphReader()
{
  // Default values for the origin vertex
  this->FileName = 0;
  this->SetNumberOfInputPorts(0);
  this->VertexAttributeArrayName = NULL;
  this->EdgeAttributeArrayName   = NULL;
  this->Directed = false;
  this->fileOk   = false;
  this->numVerts = 0;
  this->numEdges = 0;
}


vtkDIMACSGraphReader::~vtkDIMACSGraphReader()
{
  this->SetFileName(0);
  this->SetVertexAttributeArrayName(0);
  this->SetEdgeAttributeArrayName(0);
}


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

  os << indent << "FileName: "
     << (this->FileName ? this->FileName : "(none)") << endl;
  os << indent << "Vertex Attribute Array Name: "
     << (this->VertexAttributeArrayName ? this->VertexAttributeArrayName : "color")
     << endl;
  os << indent << "Edge Attribute Array Name  : "
     << (this->EdgeAttributeArrayName ? this->EdgeAttributeArrayName : "color")
     << endl;
}



// ============================================================================
// Generic DIMACS file format, which covers many 'DIMACS' style input files.
// This is the default reader if we don't have a special case file.
// * Graphs are undirected.
// * node lines (optional) have a weight value and are formatted as:
//         n id wt
//   Though, technically, some DIMACS formats (i.e., shortest paths) don't
//   specify node-attributes, we'll include them for the generic reader
//   for maximum compatibility.
// * edges, u->v, are formatted as:
//         a u v wt
//   alternatively, edges can also be:
//         e u v wt
int vtkDIMACSGraphReader::buildGenericGraph(vtkGraph     * output,
                                            vtkStdString & defaultVertexAttrArrayName,
                                            vtkStdString & defaultEdgeAttrArrayName)
{
  vtkStdString S;
  int iEdgeU, iEdgeV, iVertexID;
  int currentEdgeId = 0;

  VTK_CREATE(vtkMutableUndirectedGraph, builder);
  VTK_CREATE(vtkIntArray, ArrayVertexAttributes);
  VTK_CREATE(vtkIntArray, ArrayEdgeAttributes);

  VTK_CREATE(vtkIntArray, vertexPedigreeIds);
  VTK_CREATE(vtkIntArray, edgePedigreeIds);

  // Set up vertex attribute array for vertex-weights.
  if(this->VertexAttributeArrayName)
    {
    ArrayVertexAttributes->SetName(this->VertexAttributeArrayName);
    }
  else
    {
    ArrayVertexAttributes->SetName(defaultVertexAttrArrayName);
    }
  ArrayVertexAttributes->SetNumberOfTuples(this->numVerts);

  // Set up Edge attribute array for edge-weights.
  if(this->EdgeAttributeArrayName)
    {
    ArrayEdgeAttributes->SetName(this->EdgeAttributeArrayName);
    }
  else
    {
    ArrayEdgeAttributes->SetName(defaultEdgeAttrArrayName);
    }
  ArrayEdgeAttributes->SetNumberOfTuples(this->numEdges);

  // Set up Pedigree-IDs arrays.
  vertexPedigreeIds->SetName("vertex id");
  vertexPedigreeIds->SetNumberOfTuples(this->numVerts);
  edgePedigreeIds->SetName("edge id");
  edgePedigreeIds->SetNumberOfTuples(this->numEdges);

  // Allocate Vertices in the graph builder
  for(int i=0; i<this->numVerts; i++)
    {
    builder->AddVertex();
    vertexPedigreeIds->SetValue(i, i+1);
    }

  // set starting edge id number.
  int baseEdgeId = 1;

  ifstream IFP(this->FileName);
  if(IFP.is_open())
    {
    while( vtksys::SystemTools::GetLineFromStream(IFP,S) )
      {
      int value;
      istringstream iss(S);
      char lineType;
      iss >> lineType;
      switch(lineType)
        {
        case 'n':  /* vertex (node) definition */
            iss >> iVertexID >> value;
            ArrayVertexAttributes->SetValue(iVertexID-1, value);
            vertexPedigreeIds->SetValue(iVertexID-1, iVertexID);
            break;
        case 'a':  /* edge arc */
        case 'e':
            {
            iss >> iEdgeU >> iEdgeV >> value;

            if(iEdgeU==0 || iEdgeV==0)
              {
              vtkErrorMacro(<<"DIMACS graph vertices are numbered 1..n; 0 is not allowed");
              return 0;
              }

            vtkEdgeType edgeObj = builder->AddEdge(iEdgeU-1, iEdgeV-1);
            ArrayEdgeAttributes->SetValue(edgeObj.Id, value);
            edgePedigreeIds->SetValue(currentEdgeId, currentEdgeId+baseEdgeId);
            currentEdgeId++;
            }
            break;
        case 'c': /* Comment line, ignore it! */
            break;
        default:
            break;
        };
      }
    }

  // Add the pedigree ids to the graph
  builder->GetVertexData()->SetPedigreeIds( vertexPedigreeIds );
  builder->GetEdgeData()->SetPedigreeIds( edgePedigreeIds );

  // Add the attribute arrays to the graph
  builder->GetVertexData()->AddArray(ArrayVertexAttributes);
  builder->GetEdgeData()->AddArray(ArrayEdgeAttributes);

  if (!output->CheckedShallowCopy(builder))
    {
    vtkErrorMacro(<<"Invalid graph structure");
    return 0;
    }
  return 1;
}



// ============================================================================
// Build a graph from a max-flow problem.
// * These are directed.
// * These should have TWO node descriptor lines of the format:
//         n  ID  <char>
//   where <char> is either an 's' or a 't', for the source and sink,
//   respectively.
// * Format of edge lines is:
//         a u v cap
//   to create an edge u->v, and cap gives the edge capacity.
int vtkDIMACSGraphReader::buildMaxflowGraph(vtkGraph * output)
{
  vtkStdString S;
  int iEdgeU, iEdgeV, iVertexID;
  int currentEdgeId = 0;
  int numSrcs = 0;
  int numSinks = 0;

  vtkStdString sAttribute;
  VTK_CREATE(vtkMutableDirectedGraph, builder);

  VTK_CREATE(vtkIntArray, vertexSourceArray);
  VTK_CREATE(vtkIntArray, vertexSinkArray);
  VTK_CREATE(vtkIntArray, edgeCapacityArray);

  VTK_CREATE(vtkIntArray, vertexPedigreeIds);
  VTK_CREATE(vtkIntArray, edgePedigreeIds);

  vertexSourceArray->SetName("sources");
  vertexSinkArray->SetName("sinks");
  edgeCapacityArray->SetName("capacity");

  vertexSourceArray->SetNumberOfTuples(this->numVerts);
  vertexSinkArray->SetNumberOfTuples(this->numVerts);
  edgeCapacityArray->SetNumberOfTuples(this->numEdges);

  for(int i=0; i<this->numVerts; i++)
    {
    vertexSourceArray->SetValue(i,0);
    vertexSinkArray->SetValue(i,0);
    }

  for(int i=0; i<this->numEdges; i++)
    {
    edgeCapacityArray->SetValue(i,0);
    }

  // Set up Pedigree-IDs arrays.
  vertexPedigreeIds->SetName("vertex id");
  vertexPedigreeIds->SetNumberOfTuples(this->numVerts);
  edgePedigreeIds->SetName("edge id");
  edgePedigreeIds->SetNumberOfTuples(this->numEdges);

  // Allocate Vertices in the graph builder
  for(int i=0; i<this->numVerts; i++)
    {
    builder->AddVertex();
    vertexPedigreeIds->SetValue(i, i+1);
    }

  // set starting edge id number.
  int baseEdgeId = 1;

  ifstream IFP(this->FileName);
  if(IFP.is_open())
    {
    while( vtksys::SystemTools::GetLineFromStream(IFP,S) )
      {
      istringstream iss(S);
      char lineType;
      iss >> lineType;
      switch(lineType)
        {
        case 'n':  /* vertex (node) definition */
            iss >> iVertexID >> sAttribute;
            vertexPedigreeIds->SetValue(iVertexID-1, iVertexID);

            if(sAttribute == "s" && numSrcs==0)
              {
              numSrcs++;
              vertexSourceArray->SetValue(iVertexID-1, 1);
              }
            else if(sAttribute == "t" && numSinks==0)
              {
              numSinks++;
              vertexSinkArray->SetValue(iVertexID-1, 1);
              }
            else
              {
              vtkWarningMacro(<< "In DIMACS Max-Flow file: "
                              << this->FileName
                              << "  multiple sources or sinks specified!"
                              << endl
                              << "  Ignoring all but first source/sink found.");
              }
            break;
        case 'a':  /* edge arc */
            {
            int edgeCapacity;
            iss >> iEdgeU >> iEdgeV >> edgeCapacity;

            if(iEdgeU==0 || iEdgeV==0)
              {
              vtkErrorMacro(<<"DIMACS graph vertices are numbered 1..n; 0 is not allowed");
              return 0;
              }

            vtkEdgeType edgeObj = builder->AddEdge(iEdgeU-1, iEdgeV-1);
            edgeCapacityArray->SetValue(edgeObj.Id, edgeCapacity);
            edgePedigreeIds->SetValue(currentEdgeId, currentEdgeId+baseEdgeId);
            currentEdgeId++;
            }
            break;
        case 'c': /* Comment line, ignore it! */
            break;
        default:
            break;
        };
      }
    }

  // Add the pedigree ids to the graph
  builder->GetVertexData()->SetPedigreeIds( vertexPedigreeIds );
  builder->GetEdgeData()->SetPedigreeIds( edgePedigreeIds );

  // Add the attribute arrays to the graph
  builder->GetVertexData()->AddArray(vertexSourceArray);
  builder->GetVertexData()->AddArray(vertexSinkArray);
  builder->GetEdgeData()->AddArray(edgeCapacityArray);


  if (!output->CheckedShallowCopy(builder))
    {
    vtkErrorMacro(<<"Invalid graph structure");
    return 0;
    }
  return 1;
}



// ============================================================================
// Builder method for creating coloring problem graphs.
// * These are undirected.
// * nodes and edges have no weights associated with them.
// * edges (u->v) are formatted as:
//         e u v
int vtkDIMACSGraphReader::buildColoringGraph(vtkGraph * output)
{
  vtkStdString S;
  int iEdgeU, iEdgeV;
  int currentEdgeId = 0;

  VTK_CREATE(vtkMutableUndirectedGraph, builder);
  VTK_CREATE(vtkIntArray, vertexPedigreeIds);
  VTK_CREATE(vtkIntArray, edgePedigreeIds);

  // Set up Pedigree-IDs arrays.
  vertexPedigreeIds->SetName("vertex id");
  vertexPedigreeIds->SetNumberOfTuples(this->numVerts);
  edgePedigreeIds->SetName("edge id");
  edgePedigreeIds->SetNumberOfTuples(this->numEdges);

  // Allocate Vertices in the graph builder
  for(int i=0; i<this->numVerts; i++)
    {
    builder->AddVertex();
    vertexPedigreeIds->SetValue(i, i+1);
    }

  // set starting edge id number.
  int baseEdgeId = 1;

  ifstream IFP(this->FileName);
  if(IFP.is_open())
    {
    while( vtksys::SystemTools::GetLineFromStream(IFP,S) )
      {
      istringstream iss(S);
      char lineType;
      iss >> lineType;
      switch(lineType)
        {
        case 'e':  /* edge arc */
            {
            iss >> iEdgeU >> iEdgeV;

            if(iEdgeU==0 || iEdgeV==0)
              {
              vtkErrorMacro(<<"DIMACS graph vertices are numbered 1..n; 0 is not allowed");
              return 0;
              }

            builder->AddEdge(iEdgeU-1, iEdgeV-1);
            edgePedigreeIds->SetValue(currentEdgeId, currentEdgeId+baseEdgeId);
            currentEdgeId++;
            }
            break;
        default:
            break;
        };
      }
    }

  // Add the pedigree ids to the graph
  builder->GetVertexData()->SetPedigreeIds( vertexPedigreeIds );
  builder->GetEdgeData()->SetPedigreeIds( edgePedigreeIds );

  if (!output->CheckedShallowCopy(builder))
    {
    vtkErrorMacro(<<"Invalid graph structure");
    return 0;
    }

  return 1;
}



// ============================================================================
// Searches for the problem line in a dimacs graph (starts with 'p')
// and gets the problem type and the number of vertices and edges.
// Sets the directedness of the graph as well based on what the problem
// definition is (i.e, max-flow problems are directed, but coloring is not).
int vtkDIMACSGraphReader::ReadGraphMetaData()
{
  if (this->FileName == NULL)
    {
    vtkErrorMacro("File name undefined");
    return 0;
    }

  ifstream IFP(this->FileName);
  if(!IFP.is_open())
    {
    vtkErrorMacro("Could not open file " << this->FileName << ".");
    return(0);
    }
  vtkStdString S;
  bool foundProblemLine = false;
  bool foundMultipleProblemLines = false;

  // Look at lines until we find the problem line (this should always
  // be one of the first lines in a DIMACS graph)
  while(!foundProblemLine && vtksys::SystemTools::GetLineFromStream(IFP,S))
    {
    istringstream iss(S);
    char lineType;
    iss >> lineType;
    switch(lineType)
      {
      case 'p':
        if( !foundProblemLine )
          {
          foundProblemLine = true;
          iss >> this->dimacsProblemStr
              >> this->numVerts
              >> this->numEdges;
          }
        else
          {
          foundMultipleProblemLines = true;
          }
      };
    }
  IFP.close();

  if(!foundProblemLine)
    {
    vtkErrorMacro(<< "Error in DIMACS file: " << this->FileName
                  << ", could not find a problem description line.");
    return 0;
    }

  if(foundMultipleProblemLines)
    {
    vtkWarningMacro(<< "Found multiple problem lines in DIMACS file: "
                    << this->FileName << "; using the first one found.");
    }

  // Set directed if necessary
  if(this->dimacsProblemStr == "max")
    {
    this->Directed = true;
    }

  this->fileOk = true;

  return 1;
}



// ============================================================================
int vtkDIMACSGraphReader::RequestData(vtkInformation       *  vtkNotUsed(request),
                                      vtkInformationVector ** vtkNotUsed(inputVector),
                                      vtkInformationVector *  outputVector)
{
  int rval=0;
  if( !this->fileOk )
    {
    return 0;
    }

  vtkGraph * output = vtkGraph::GetData(outputVector);

  if(this->dimacsProblemStr == "edge")
    {
    vtkDebugMacro("Loading DIMACS coloring problem graph.");
    rval = buildColoringGraph(output);
    }
  else if(this->dimacsProblemStr == "max")
    {
    vtkDebugMacro("Loading DIMACS max-flow problem graph.");
    rval = buildMaxflowGraph(output);
    }
  else
    {
    vtkDebugMacro("Loading DIMACS default graph.");
    vtkStdString vWeightName = "weight";
    vtkStdString eWeightName = "weight";
    rval = buildGenericGraph(output, vWeightName, eWeightName);
    }
  return rval;
}



//----------------------------------------------------------------------------
int vtkDIMACSGraphReader::RequestDataObject(vtkInformation*,
                                            vtkInformationVector**,
                                            vtkInformationVector* )
{
  ReadGraphMetaData();

  vtkDataObject *current = this->GetExecutive()->GetOutputData(0);
  if (!current || (this->Directed && !vtkDirectedGraph::SafeDownCast(current))
               || (!this->Directed && vtkDirectedGraph::SafeDownCast(current)))
    {
    vtkGraph *output = 0;
    if (this->Directed)
      {
      output = vtkDirectedGraph::New();
      }
    else
      {
      output = vtkUndirectedGraph::New();
      }
    this->GetExecutive()->SetOutputData(0, output);
    output->Delete();
    }
  return 1;
}