/////////////////////////////////////////////////////////////////
// GraphAlgorithms.cpp - Algorithms on graph structures        //
// ver 1.0                                                     //
// ----------------------------------------------------------- //
// 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 "GraphAlgorithms.h"

#include "..\GraphPersistence\GraphIO.h"

using namespace DirectedGraph;

#ifdef TEST_GRAPHALGORITHMS

class TestFunctor : public IFunctor<std::string, std::string>
{
public:
  TestFunctor() { std::cout << "\n  "; }
  ~TestFunctor() { std::cout << "\n"; }
  void operator()(Vertex<std::string, std::string>& v)
  {
    static size_t count = 0;
    if(++count != 1)
      std::cout << ", ";
    std::cout << v.value();
  }
};

int main()
{
  std::cout << "\n  Testing GraphAlgorithms";
  std::cout << "\n =========================";

  std::string SrcFile = "..\\GraphPersistence\\TestGraphIn.xml";
  Graph<std::string, std::string> g;

  GraphIO<std::string, std::string> gio;
  if(!gio.ReadGraph(g, SrcFile))
  {
    std::cout << "\n  can't read " << SrcFile << "\n\n";
  }
  Display<std::string, std::string> display(g);
  foreach(g, display);
  std::cout << "\n";

  std::cout << "\n  Vertices with no Parents:";
  std::cout << "\n ---------------------------";
  std::vector<Vertex<std::string, std::string>> VertsWNP;
  VertsWNP = vertsWithNoParents(g);
  for(size_t i=0; i<VertsWNP.size(); ++i)
  {
    std::cout << "\n  vertex id = " << VertsWNP[i].id();
  }
  std::cout << "\n";
  
  std::cout << "\n  Depth First Search";
  std::cout << "\n --------------------";
  dfs<std::string, std::string>(g, TestFunctor());
  //std::cout << "\n";

  std::cout << "\n  Strong Components, listed by id";
  std::cout << "\n ---------------------------------";
  Algorithms<std::string, std::string> algor;
  Algorithms<std::string, std::string>::Component comp = algor.strongComp(g);
  size_t numComps = comp.size();
  for(size_t i=0; i<numComps; ++i)
  {
    std::cout << "\n  ";
    size_t numElems = comp[i].size();
    for(size_t j=0; j<numElems; ++j)
    {
      size_t vertexIndex = comp[i][j]-1;
      size_t vertexId = g[vertexIndex].id();
      std::cout << LibUtils::toString(vertexId) << " ";
    }
  }
  std::cout << "\n\n";
}

#endif