// -*- c++ -*-

#include <iostream>

#include <vector>

#include <string>

#include <list_graph.h>

//#include <smart_graph.h>

#include <bfs_dfs.h>

#include <hugo/graph_wrapper.h>

using namespace hugo;

using std::cout; 

using std::endl;

using std::string;

template <typename Graph, typename NodeNameMap>

class EdgeNameMap {

  Graph& graph;

  NodeNameMap& node_name_map;

public:

  EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) : 

    graph(_graph), node_name_map(_node_name_map) { }

  string operator[](typename Graph::Edge e) const { 

    return 

      (node_name_map[graph.tail(e)]+"->"+node_name_map[graph.head(e)]);

  }

};

int main (int, char*[])

{

  //typedef SmartGraph Graph;

  typedef ListGraph Graph;

  typedef Graph::Node Node;

  typedef Graph::Edge Edge;

  Graph G;

  Node s=G.addNode();

  Node v1=G.addNode();

  Node v2=G.addNode();

  Node v3=G.addNode();

  Node v4=G.addNode();

  Node t=G.addNode();

  Graph::NodeMap<string> node_name(G);

  node_name.set(s, "s");

  node_name.set(v1, "v1");

  node_name.set(v2, "v2");

  node_name.set(v3, "v3");

  node_name.set(v4, "v4");

  node_name.set(t, "t");

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

  cout << "    /-->    ------------->            "<< endl;

  cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;

  cout << "  / |          |    /  /->     \\     "<< endl;

  cout << " /  |          |   /  |    ^    \\  "<< endl;

  cout << "s   |          |  /   |    |     \\->  t "<< endl;

  cout << " \\  |          | /    |    |     /->  "<< endl;

  cout << "  \\ |       --/ /     |    |    /     "<< endl;

  cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;

  cout << "    \\-->    ------------->         "<< endl;

//   typedef TrivGraphWrapper<const Graph> CGW;

//   CGW gw(G);

//   cout << "bfs and dfs demo on the directed graph" << endl;

//   for(CGW::NodeIt n=gw.first<CGW::NodeIt>(); n.valid(); ++n) { 

//     cout << n << ": ";

//     cout << "out edges: ";

//     for(CGW::OutEdgeIt e=gw.first<CGW::OutEdgeIt>(n); e.valid(); ++e) 

//       cout << e << " ";

//     cout << "in edges: ";

//     for(CGW::InEdgeIt e=gw.first<CGW::InEdgeIt>(n); e.valid(); ++e) 

//       cout << e << " ";

//     cout << endl;

//   }

  {

    EdgeNameMap< Graph, Graph::NodeMap<string> > edge_name(G, node_name);

    cout << "bfs and dfs iterator demo on the directed graph" << endl;

    for(Graph::NodeIt n(G); G.valid(n); G.next(n)) { 

      cout << node_name[n] << ": ";

      cout << "out edges: ";

      for(Graph::OutEdgeIt e(G, n); G.valid(e); G.next(e)) 

	cout << edge_name[e] << " ";

      cout << "in edges: ";

      for(Graph::InEdgeIt e(G, n); G.valid(e); G.next(e)) 

	cout << edge_name[e] << " ";

      cout << endl;

    }

    cout << "bfs from s ..." << endl;

    BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G);

    bfs.pushAndSetReached(s);

    while (!bfs.finished()) {

      //cout << "edge: ";

      if (G.valid(bfs)) {

	cout << edge_name[bfs] << /*endl*/", " << 

	  node_name[G.aNode(bfs)] << 

	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 

	  node_name[G.bNode(bfs)] << 

	  (bfs.isBNodeNewlyReached() ? ": is newly reached." : 

	   ": is not newly reached.");

      } else { 

	cout << "invalid" << /*endl*/", " << 

	  node_name[bfs.aNode()] << 

	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 

	  "invalid.";

      }

      cout << endl;

      ++bfs;

    }

    cout << "    /-->    ------------->            "<< endl;

    cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;

    cout << "  / |          |    /  /->     \\     "<< endl;

    cout << " /  |          |   /  |    ^    \\  "<< endl;

    cout << "s   |          |  /   |    |     \\->  t "<< endl;

    cout << " \\  |          | /    |    |     /->  "<< endl;

    cout << "  \\ |       --/ /     |    |    /     "<< endl;

    cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;

    cout << "    \\-->    ------------->         "<< endl;

    cout << "dfs from s ..." << endl;

    DfsIterator< Graph, Graph::NodeMap<bool> > dfs(G);

    dfs.pushAndSetReached(s);

    while (!dfs.finished()) {

      ++dfs;

      //cout << "edge: ";

      if (G.valid(dfs)) {

	cout << edge_name[dfs] << /*endl*/", " << 

	  node_name[G.aNode(dfs)] << 

	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 

	  node_name[G.bNode(dfs)] << 

	  (dfs.isBNodeNewlyReached() ? ": is newly reached." : 

	   ": is not newly reached.");

      } else { 

	cout << "invalid" << /*endl*/", " << 

	  node_name[dfs.aNode()] << 

	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 

	  "invalid.";

      }

      cout << endl;

    }

  }

  {

    typedef RevGraphWrapper<const Graph> GW;

    GW gw(G);

    EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);

    cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;

    for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { 

      cout << node_name[GW::Node(n)] << ": ";

      cout << "out edges: ";

      for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) 

	cout << edge_name[e] << " ";

      cout << "in edges: ";

      for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) 

	cout << edge_name[e] << " ";

      cout << endl;

    }

    cout << "bfs from t ..." << endl;

    BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);

    bfs.pushAndSetReached(t);

    while (!bfs.finished()) {

      //cout << "edge: ";

      if (gw.valid(GW::OutEdgeIt(bfs))) {

	cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " << 

	  node_name[gw.aNode(bfs)] << 

	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 

	  node_name[gw.bNode(bfs)] << 

	  (bfs.isBNodeNewlyReached() ? ": is newly reached." : 

	   ": is not newly reached.");

      } else { 

	cout << "invalid" << /*endl*/", " << 

	  node_name[bfs.aNode()] << 

	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 

	  "invalid.";

      }

      cout << endl;

      ++bfs;

    }

    cout << "    /-->    ------------->            "<< endl;

    cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;

    cout << "  / |          |    /  /->     \\     "<< endl;

    cout << " /  |          |   /  |    ^    \\  "<< endl;

    cout << "s   |          |  /   |    |     \\->  t "<< endl;

    cout << " \\  |          | /    |    |     /->  "<< endl;

    cout << "  \\ |       --/ /     |    |    /     "<< endl;

    cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;

    cout << "    \\-->    ------------->         "<< endl;

    cout << "dfs from t ..." << endl;

    DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);

    dfs.pushAndSetReached(t);

    while (!dfs.finished()) {

      ++dfs;

      //cout << "edge: ";

      if (gw.valid(GW::OutEdgeIt(dfs))) {

	cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " << 

	  node_name[gw.aNode(dfs)] << 

	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 

	  node_name[gw.bNode(dfs)] << 

	  (dfs.isBNodeNewlyReached() ? ": is newly reached." : 

	   ": is not newly reached.");

      } else { 

	cout << "invalid" << /*endl*/", " << 

	  node_name[dfs.aNode()] << 

	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 

	  "invalid.";

      }

      cout << endl;

    }

  }

  {

    typedef UndirGraphWrapper<const Graph> GW;

    GW gw(G);

    EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);

    cout << "bfs and dfs iterator demo on the undirected graph" << endl;

    for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { 

      cout << node_name[GW::Node(n)] << ": ";

      cout << "out edges: ";

      for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) 

	cout << edge_name[e] << " ";

      cout << "in edges: ";

      for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) 

	cout << edge_name[e] << " ";

      cout << endl;

    }

//     for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) { 

//       cout << edge_name.get(e) << " ";

//     }

//     cout << endl;

    cout << "bfs from t ..." << endl;

    BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);

    bfs.pushAndSetReached(t);

    while (!bfs.finished()) {

      //cout << "edge: ";

      if (gw.valid(GW::OutEdgeIt(bfs))) {

	cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " << 

	  node_name[gw.aNode(bfs)] << 

	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 

	  node_name[gw.bNode(bfs)] << 

	  (bfs.isBNodeNewlyReached() ? ": is newly reached." : 

	   ": is not newly reached.");

      } else { 

	cout << "invalid" << /*endl*/", " << 

	  node_name[bfs.aNode()] << 

	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 

	  "invalid.";

      }

      cout << endl;

      ++bfs;

    }

    cout << "    /-->    ------------->            "<< endl;

    cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;

    cout << "  / |          |    /  /->     \\     "<< endl;

    cout << " /  |          |   /  |    ^    \\  "<< endl;

    cout << "s   |          |  /   |    |     \\->  t "<< endl;

    cout << " \\  |          | /    |    |     /->  "<< endl;

    cout << "  \\ |       --/ /     |    |    /     "<< endl;

    cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;

    cout << "    \\-->    ------------->         "<< endl;

    cout << "dfs from t ..." << endl;

    DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);

    dfs.pushAndSetReached(t);

    while (!dfs.finished()) {

      ++dfs;

      //cout << "edge: ";

      if (gw.valid(GW::OutEdgeIt(dfs))) {

	cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " << 

	  node_name[gw.aNode(dfs)] << 

	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 

	  node_name[gw.bNode(dfs)] << 

	  (dfs.isBNodeNewlyReached() ? ": is newly reached." : 

	   ": is not newly reached.");

      } else { 

	cout << "invalid" << /*endl*/", " << 

	  node_name[dfs.aNode()] << 

	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 

	  "invalid.";

      }

      cout << endl;

    }

  }

  {

    typedef BidirGraphWrapper<const Graph> GW;

    GW gw(G);

    EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);

    cout << "bfs and dfs iterator demo on the undirected graph" << endl;

    for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { 

      cout << node_name[GW::Node(n)] << ": ";

      cout << "out edges: ";

      for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) 

	cout << edge_name[e] << " ";

      cout << "in edges: ";

      for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) 

	cout << edge_name[e] << " ";

      cout << endl;

    }

//     for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) { 

//       cout << edge_name.get(e) << " ";

//     }

//     cout << endl;

    cout << "bfs from t ..." << endl;

    BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);

    bfs.pushAndSetReached(t);

    while (!bfs.finished()) {

      //cout << "edge: ";

      if (gw.valid(GW::OutEdgeIt(bfs))) {

	cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " << 

	  node_name[gw.aNode(bfs)] << 

	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 

	  node_name[gw.bNode(bfs)] << 

	  (bfs.isBNodeNewlyReached() ? ": is newly reached." : 

	   ": is not newly reached.");

      } else { 

	cout << "invalid" << /*endl*/", " << 

	  node_name[bfs.aNode()] << 

	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 

	  "invalid.";

      }

      cout << endl;

      ++bfs;

    }

    cout << "    /-->    ------------->            "<< endl;

    cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;

    cout << "  / |          |    /  /->     \\     "<< endl;

    cout << " /  |          |   /  |    ^    \\  "<< endl;

    cout << "s   |          |  /   |    |     \\->  t "<< endl;

    cout << " \\  |          | /    |    |     /->  "<< endl;

    cout << "  \\ |       --/ /     |    |    /     "<< endl;

    cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;

    cout << "    \\-->    ------------->         "<< endl;

    cout << "dfs from t ..." << endl;

    DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);

    dfs.pushAndSetReached(t);

    while (!dfs.finished()) {

      ++dfs;

      //cout << "edge: ";

      if (gw.valid(GW::OutEdgeIt(dfs))) {

	cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " << 

	  node_name[gw.aNode(dfs)] << 

	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 

	  node_name[gw.bNode(dfs)] << 

	  (dfs.isBNodeNewlyReached() ? ": is newly reached." : 

	   ": is not newly reached.");

      } else { 

	cout << "invalid" << /*endl*/", " << 

	  node_name[dfs.aNode()] << 

	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 

	  "invalid.";

      }

      cout << endl;

    }

  }

  return 0;

}