/////////////////////////////////////////////////////////////////
// TestGraph.cpp - Unit tests for Graph, GraphIO, and          //
//                 GraphAlgorithms                             //
// ver 1.1                                                     //
// ----------------------------------------------------------- //
// copyright © Jim Fawcett, 2012                               //
// All rights granted provided that this notice is retained    //
// ----------------------------------------------------------- //
// Jim Fawcett, CST 4-187, Syracuse University, 315 443 3948   //
// Summer Projects, 2012                                       //
// Win7, Visual Studio 2010                                    //
/////////////////////////////////////////////////////////////////

#include <algorithm>
#include "UnitTest.h"
#include "..\Graph\Graph.h"
#include "..\GraphPersistence\GraphIO.h"
#include "..\GraphAlgorithms\GraphAlgorithms.h"

using namespace DirectedGraph;

class TestVertex : public ITest<TestVertex>
{
public:
  typedef Vertex<std::string, std::string> vertex;

  TestVertex() { std::cout << "\n  Testing Vertex class"; }
  bool test()
  {
    // build a Vertex and check that it has the intended properties

    bool t1, t2, t3, t4;
    vertex v(1, "v1");
    vertex::Edge e1 = std::pair<size_t, std::string>(2, "e1");
    vertex::Edge e2 = std::pair<size_t, std::string>(3, "e2");
    v.add(e1);
    v.add(e2);
    t1 = v.size() == 2;
    t2 = v[0].first == 2 && v[0].second == "e1";
    t3 = v[1].first == 3 && v[1].second == "e2";
    t4 = v.id() == 1 && v.value() == "v1";
    return checkResult(t1 && t2 && t3 && t4, "Vertex::test");
  }
private:
};

template <typename V, typename E>
void createGraph(Graph<V,E>& g)
{
  // Defines a test graph used in many tests below.
  // Note that changing test graph will require
  // many changes in the tests below.

  typedef Vertex<std::string, std::string> vertex;
  typedef vertex::Edge edge;
  vertex v1(1, "v1");
  vertex v2(2, "v2");
  vertex v3(3, "v3");
  vertex v4(4, "v4");
  edge e1, e2, e3, e4, e5;
  g.addVertex(v1);
  g.addVertex(v2);
  g.addVertex(v3);
  g.addVertex(v4);
  g.addEdge("e1",v1,v2);
  g.addEdge("e2",v1,v3);
  g.addEdge("e3",v3,v2);
  g.addEdge("e4",v2,v4);
  g.addEdge("e5",v4,v3);     
}

class TestGraph : public ITest<TestGraph>
{
public:
  typedef Vertex<std::string, std::string> vertex;
  typedef Graph<std::string, std::string> graph;
  typedef vertex::Edge edge;

  TestGraph() 
  { 
    std::cout << "\n  testing Graph class"; 
    createGraph(g_);
  }

  bool TestAddVerticesAndEdges()
  {
    // show that the graph created by createGraph
    // has the expected properties

    bool t1, t2, t3, t4, t5, t6, t7, t8, t9, t10;
     
    t1 = g_.size() == 4;
    t2 = g_[0].id() == 1 && g_[0].value() == "v1";
    t3 = g_[1].id() == 2 && g_[1].value() == "v2";
    t4 = g_[2].id() == 3 && g_[2].value() == "v3";
    t5 = g_[3].id() == 4 && g_[3].value() == "v4";
    t6 = g_[0][0].first == 1 && g_[0][0].second == "e1";
    t7 = g_[0][1].first == 2 && g_[0][1].second == "e2";
    t8 = g_[1][0].first == 3 && g_[1][0].second == "e4";
    t9 = g_[2][0].first == 1 && g_[2][0].second == "e3";
    t10 = g_[3][0].first == 2 && g_[3][0].second == "e5";
    return checkResult(
      t1 && t2 && t3 && t4 && t5 && t6 && t7 && t8 && t9 && t10, 
      "TestAddVerticesAndEdges"
    );
  }
  bool TestIteration()
  {
    // compare results of indexing and iterating

    std::vector<bool> tst;

    graph::iterator iter = g_.begin();
    for(size_t i=0; i<g_.size(); ++i)
    {
      tst.push_back(g_[i].id() == (*iter++).id()); 
    }
    bool t = std::find(tst.begin(), tst.end(), false) == tst.end();
    return checkResult(t, "TestIteration");
  }
  bool TestFindById()
  {
    // show that correct index for each vertex is returned by
    // findVertexById

    std::vector<bool> tst;
    for(size_t i=0; i<g_.size(); ++i)
    {
      tst.push_back(g_.findVertexById(g_[i].id()) == i);
    }
    bool t1 = std::find(tst.begin(), tst.end(), false) == tst.end();
    bool t2 = g_.findVertexById(99) == g_.size();
    return checkResult(t1 && t2, "TestFindById");
  }
  bool TestFindByValue()
  {
    // show that correct value for each vertex is returned by
    // findVertexByValue

    std::vector<bool> tst;
    for(size_t i=0; i<g_.size(); ++i)
    {
      tst.push_back(g_.findVertexByValue(g_[i].value()) == i);
    }
    bool t1 = std::find(tst.begin(), tst.end(), false) == tst.end();
    bool t2 = g_.findVertexByValue("foobar") == g_.size();
    return checkResult(t1 && t2, "TestFindByValue");
  }
  bool test()
  {
    // show whether all tests pass

    bool t1, t2, t3, t4;
    t1 = doTest(&TestGraph::TestAddVerticesAndEdges);
    t2 = doTest(&TestGraph::TestIteration);
    t3 = doTest(&TestGraph::TestFindById);
    t4 = doTest(&TestGraph::TestFindByValue);
    return t1 && t2 && t3 && t4;
  }
private:
  graph g_;
};

class TestGraphIO : public ITest<TestGraphIO>
{
public:
  typedef Vertex<std::string, std::string> vertex;
  typedef Graph<std::string, std::string> graph;
  typedef vertex::Edge edge;

  TestGraphIO() 
  { 
    std::cout << "\n  Testing GraphIO class"; 
    createGraph(g_);
  }
  bool TestGraphReadAndWrite()
  {
    // show that a graph that is written then read
    // suffers no change

    GraphIO<std::string, std::string> gio;
    gio.WriteGraph(g_, "testWriteGraph.xml");
    graph gRead;
    gio.ReadGraph(gRead, "testWriteGraph.xml");
    return checkResult(gRead == g_, "TestGraphReadAndWrite");
  }
  bool test()
  {
    return doTest(&TestGraphIO::TestGraphReadAndWrite);
  }
private:
  graph g_;
};

class TestGraphAlgorithms : public ITest<TestGraphAlgorithms>
{
public:
  typedef Vertex<std::string, std::string> vertex;
  typedef Graph<std::string, std::string> graph;
  typedef vertex::Edge edge;

  TestGraphAlgorithms() 
  { 
    std::cout << "\n  Testing GraphAlgorithms class"; 
    createGraph(g_);
  }
  bool TestVertsWithNoParents()
  {
    // show that top level vertices are correctly identified

    std::vector<vertex> noParents = vertsWithNoParents(g_);
    return checkResult(noParents.size() == 1 && noParents[0].id() == 1, "TestVertsWithNoParents");
  }
  bool TestStrongComponents()
  {
    // Show that strong component algorithm returns strong components of the
    // correct size.

    Algorithms<std::string, std::string> ga;
    Components comp = ga.strongComp(g_);
    bool t1, t2, t3;
    t1 = comp.size() == 2;
    if(t1)
    {
      t2 = comp[0].size() == 1 || comp[0].size() == 3;
      t3 = comp[1].size() == 1 || comp[1].size() == 3;
    }
    else
      t2 = t3 = false;
    return checkResult(t1 && t2 && t3, "TestStrongComponents");
  }
  bool test()
  {
    // Show whether all tests pass.

    bool t1, t2;
    t1 = doTest(&TestGraphAlgorithms::TestVertsWithNoParents);
    t2 = doTest(&TestGraphAlgorithms::TestStrongComponents);
    return t1 && t2;
  }
private:
  graph g_;
};

bool GraphTest()
{
  bool t1, t2, t3, t4;
  TestVertex tv;
  t1 = tv.test();
  std::cout << "\n";
  TestGraph tg;
  t2 = tg.test();
  std::cout << "\n";
  TestGraphIO tgio;
  t3 = tgio.test();
  std::cout << "\n";
  TestGraphAlgorithms tga;
  t4 = tga.test();
  std::cout << "\n";

  ////////////////////////////////////////////////////////////
  // This will display the test graph if uncommented
  //
  //Graph<std::string, std::string> g;
  //createGraph(g);
  //foreach(g, Display<std::string, std::string>(g));

  return t1 && t2 && t3 && t4;
}
void DemoGraph()
{
  GraphIO<std::string, std::string> gio;
  Graph<std::string, std::string> g;
  gio.ReadGraph(g, "DemoGraph.xml");
  
  std::cout << "\n  Demonstrating Graph " << g.name();
  std::cout << "\n ---------------------" 
            << std::string(g.name().size()+1, '-');
  foreach(g, Display<std::string, std::string>(g));
  std::cout << "\n";

  std::cout << "\n  ids of vertices with no parents:";
  std::cout << "\n ----------------------------------";
  std::vector<Vertex<std::string, std::string>> noParents 
    = vertsWithNoParents(g);
  std::cout << "\n  ";
  for(size_t i=0; i<noParents.size(); ++i)
    std::cout << noParents[i].id() << " ";
  std::cout << "\n";

  std::cout << "\n  Strong Components:";
  std::cout << "\n --------------------";
  Algorithms<std::string, std::string> algo;
  Components comp = algo.strongComp(g);
  for(size_t i=0; i<comp.size(); ++i)
  {
    std::cout << "\n  ";
    for(size_t j=0; j<comp[i].size(); ++j)
    {
      size_t vertexIndex = comp[i][j];
      std::cout << g[vertexIndex].id() << " ";
    }
  }
  std::cout << "\n";
  std::cout << "\n  Strong Component number for each vertex:";
  std::cout << "\n ------------------------------------------";
  for(size_t i=0; i<g.size(); ++i)
  {
    size_t index = comp.component(i);
    if(index < g.size())
      std::cout << "\n  vertex with id " << g[i].id() << " belongs to strong component #" << index;
  }
  std::cout << "\n";
}
int main()
{
  std::cout << "\n  Testing DirectedGraph namespace";
  std::cout << "\n =================================";

  if(GraphTest())
    std::cout << "\n  all tests passed";
  else
    std::cout << "\n  at least one test failed";
  std::cout << "\n";
  DemoGraph();
  std::cout << "\n\n";
}