/////////////////////////////////////////////////////////////////
// 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();
  }
};

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;
  Graph<std::string, std::string> cond;
  Components comp = algo.createCondensedGraph(g, cond);

  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";
  std::cout << "\n  Condensed Graph:";
  std::cout << "\n ------------------";
  foreach(cond, Display<std::string, std::string>(cond));
  std::cout << "\n";
  std::cout << "\n  Topologically sorted condensed graph vertices:";
  std::cout << "\n ------------------------------------------------";
  std::vector<size_t> orderedVertices = algo.topoSort(cond);
  std::cout << "\n  ";
  for(size_t i=0; i<orderedVertices.size(); ++i)
    std::cout << cond[orderedVertices[i]].id() << " ";
  std::cout << "\n";
  std::cout << "\n  Best ascending order of original graph vertices:";
  std::cout << "\n --------------------------------------------------";
  for(size_t i=0; i<orderedVertices.size(); ++i)
  {
    std::cout << "\n  ";
    size_t sortedComponentIndex = orderedVertices[i];
    for(size_t j=0; j<comp[sortedComponentIndex].size(); ++j)
      std::cout << g[comp[sortedComponentIndex][j]].id() << " ";
  }
  std::cout << "\n";
}

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";

  DemoGraph();

  std::cout << "\n\n";
}

#endif