#include <iostream>

 #include <vector>

 #include <string>

 #include <list_graph.hh>

 #include <bfs_iterator.hh>

 #include <graph_wrapper.h>

 using namespace marci;

 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;

     }

   }

   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;

 }