#include <iostream>
#include <vector>
#include <string>

#include <list_graph.hh>
#include <bfs_iterator.hh>
#include <graph_wrapper.h>

using namespace hugo;

int main (int, char*[])
{
  typedef ListGraph::NodeIt NodeIt;
  typedef ListGraph::EdgeIt EdgeIt;
  typedef ListGraph::EachNodeIt EachNodeIt;
  typedef ListGraph::EachEdgeIt EachEdgeIt;
  typedef ListGraph::OutEdgeIt OutEdgeIt;
  typedef ListGraph::InEdgeIt InEdgeIt;
  typedef ListGraph::SymEdgeIt SymEdgeIt;
 
  ListGraph G;

  NodeIt s=G.addNode();
  NodeIt v1=G.addNode();
  NodeIt v2=G.addNode();
  NodeIt v3=G.addNode();
  NodeIt v4=G.addNode();
  NodeIt t=G.addNode();
  
  G.addEdge(s, v1);
  G.addEdge(s, v2);
  G.addEdge(v1, v2);
  G.addEdge(v2, v1);
  G.addEdge(v1, v3);
  G.addEdge(v3, v2);
  G.addEdge(v2, v4);
  G.addEdge(v4, v3);
  G.addEdge(v3, t);
  G.addEdge(v4, t);

  std::cout << "bfs and dfs demo on the directed graph" << std::endl;
  for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) { 
    std::cout << i << ": ";
    std::cout << "out edges: ";
    for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) 
      std::cout << j << " ";
    std::cout << "in edges: ";
    for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) 
      std::cout << j << " ";
    std::cout << std::endl;
  }
  
  {
    std::cout << "iterator bfs demo 4 ..." << std::endl;
    BfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G);
    bfs.pushAndSetReached(s);
    while (!bfs.finished()) {
      if (OutEdgeIt(bfs).valid()) {
	std::cout << "OutEdgeIt: " << bfs; 
	std::cout << " aNode: " << G.aNode(bfs); 
	std::cout << " bNode: " << G.bNode(bfs) << " ";
      } else { 
	std::cout << "OutEdgeIt: " << "invalid"; 
	std::cout << " aNode: " << bfs.aNode(); 
	std::cout << " bNode: " << "invalid" << " ";
      }
      if (bfs.isBNodeNewlyReached()) { 
	std::cout << "bNodeIsNewlyReached ";
      } else { 
	std::cout << "bNodeIsNotNewlyReached ";
      } 
      if (bfs.isANodeExamined()) { 
	std::cout << "aNodeIsExamined ";
      } else { 
	std::cout << "aNodeIsNotExamined ";
      } 
      std::cout<<std::endl;
      ++bfs;
    }
  }

  {
    std::cout << "iterator dfs demo 4 ..." << std::endl;
    DfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > dfs(G);
    dfs.pushAndSetReached(s);
    while (!dfs.finished()) {
      ++dfs;
      if (OutEdgeIt(dfs).valid()) {
	std::cout << "OutEdgeIt: " << dfs; 
	std::cout << " aNode: " << G.aNode(dfs); 
	std::cout << " bNode: " << G.bNode(dfs) << " ";
      } else { 
	std::cout << "OutEdgeIt: " << "invalid"; 
	std::cout << " aNode: " << dfs.aNode(); 
	std::cout << " bNode: " << "invalid" << " ";
      }
      if (dfs.isBNodeNewlyReached()) { 
	std::cout << "bNodeIsNewlyReached ";
      } else { 
	std::cout << "bNodeIsNotNewlyReached ";
      } 
      if (dfs.isANodeExamined()) { 
	std::cout << "aNodeIsExamined ";
      } else { 
	std::cout << "aNodeIsNotExamined ";
      } 
      std::cout<<std::endl;
      //++dfs;
    }
  }


  typedef ConstTrivGraphWrapper<ListGraph> CTGW;
  CTGW wG(G);

  std::cout << "bfs and dfs demo on the directed graph" << std::endl;
  for(CTGW::EachNodeIt i=wG.first<CTGW::EachNodeIt>(); i.valid(); ++i) { 
    std::cout << i << ": ";
    std::cout << "out edges: ";
    for(CTGW::OutEdgeIt j=wG.first<CTGW::OutEdgeIt>(i); j.valid(); ++j) 
      std::cout << j << " ";
    std::cout << "in edges: ";
    for(CTGW::InEdgeIt j=wG.first<CTGW::InEdgeIt>(i); j.valid(); ++j) 
      std::cout << j << " ";
    std::cout << std::endl;
  }


  {
    std::cout << "iterator bfs demo 5 ..." << std::endl;
    BfsIterator5< CTGW, CTGW::NodeMap<bool> > bfs(wG);
    bfs.pushAndSetReached(s);
    while (!bfs.finished()) {
      if (OutEdgeIt(bfs).valid()) {
	std::cout << "OutEdgeIt: " << bfs; 
	std::cout << " aNode: " << wG.aNode(bfs); 
	std::cout << " bNode: " << wG.bNode(bfs) << " ";
      } else { 
	std::cout << "OutEdgeIt: " << "invalid"; 
	std::cout << " aNode: " << bfs.aNode(); 
	std::cout << " bNode: " << "invalid" << " ";
      }
      if (bfs.isBNodeNewlyReached()) { 
	std::cout << "bNodeIsNewlyReached ";
      } else { 
	std::cout << "bNodeIsNotNewlyReached ";
      } 
      if (bfs.isANodeExamined()) { 
	std::cout << "aNodeIsExamined ";
      } else { 
	std::cout << "aNodeIsNotExamined ";
      } 
      std::cout<<std::endl;
      ++bfs;
    }
  }


  return 0;
}