// -*- c++ -*-
#include <iostream>
#include <vector>
#include <string>

#include <LEDA/graph.h>

#include <list_graph.h>
#include <smart_graph.h>
#include <bfs_iterator.h>
#include <graph_wrapper.h>
#include <leda_graph_wrapper.h>

using namespace lemon;
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 get(typename Graph::Edge e) const { 
    return 
      (node_name_map.get(graph.source(e))+"->"+node_name_map.get(graph.target(e)));
  }
};

int main (int, char*[])
{
  

  //typedef SmartGraph Graph;
  //typedef ListGraph Graph;
  typedef LedaGraphWrapper<leda::graph> Graph;

  typedef Graph::Node Node;
  typedef Graph::NodeIt NodeIt;  
  typedef Graph::Edge Edge;
  typedef Graph::EdgeIt EdgeIt;
  typedef Graph::OutEdgeIt OutEdgeIt;
  typedef Graph::InEdgeIt InEdgeIt;

 
  leda::graph g;
  Graph G(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 wG(G);

//   cout << "bfs and dfs demo on the directed graph" << endl;
//   for(CGW::NodeIt n=wG.first<CGW::NodeIt>(); n.valid(); ++n) { 
//     cout << n << ": ";
//     cout << "out edges: ";
//     for(CGW::OutEdgeIt e=wG.first<CGW::OutEdgeIt>(n); e.valid(); ++e) 
//       cout << e << " ";
//     cout << "in edges: ";
//     for(CGW::InEdgeIt e=wG.first<CGW::InEdgeIt>(n); e.valid(); ++e) 
//       cout << e << " ";
//     cout << endl;
//   }

  {
    typedef TrivGraphWrapper<const Graph> GW;
    GW wG(G);

    EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name);
    
    cout << "bfs and dfs iterator demo on the directed graph" << endl;
    for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) { 
      cout << node_name.get(n) << ": ";
      cout << "out edges: ";
      for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e)) 
	cout << edge_name.get(e) << " ";
      cout << "in edges: ";
      for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e)) 
	cout << edge_name.get(e) << " ";
      cout << endl;
    }

    cout << "bfs from s ..." << endl;
    BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG);
    bfs.pushAndSetReached(s);
    while (!bfs.finished()) {
      //cout << "edge: ";
      if (wG.valid(bfs)) {
	cout << edge_name.get(bfs) << /*endl*/", " << 
	  /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) << 
	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
	  /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) << 
	  (bfs.isBNodeNewlyReached() ? ": is newly reached." : 
	   ": is not newly reached.");
      } else { 
	cout << "invalid" << /*endl*/", " << 
	  /*" aNode: " <<*/ node_name.get(bfs.aNode()) << 
	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
	  /*" bNode: " <<*/ 
	  "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;
    DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG);
    dfs.pushAndSetReached(s);
    while (!dfs.finished()) {
      ++dfs;
      //cout << "edge: ";
      if (wG.valid(dfs)) {
	cout << edge_name.get(dfs) << /*endl*/", " << 
	  /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) << 
	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
	  /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) << 
	  (dfs.isBNodeNewlyReached() ? ": is newly reached." : 
	   ": is not newly reached.");
      } else { 
	cout << "invalid" << /*endl*/", " << 
	  /*" aNode: " <<*/ node_name.get(dfs.aNode()) << 
	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
	  /*" bNode: " <<*/ 
	  "invalid.";
      }
      cout << endl;
    }
  }


  {
    typedef RevGraphWrapper<const Graph> GW;
    GW wG(G);
    
    EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name);
    
    cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;
    for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) { 
      cout << node_name.get(n) << ": ";
      cout << "out edges: ";
      for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e)) 
	cout << edge_name.get(e) << " ";
      cout << "in edges: ";
      for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e)) 
	cout << edge_name.get(e) << " ";
      cout << endl;
    }

    cout << "bfs from t ..." << endl;
    BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG);
    bfs.pushAndSetReached(t);
    while (!bfs.finished()) {
      //cout << "edge: ";
      if (wG.valid(bfs)) {
	cout << edge_name.get(bfs) << /*endl*/", " << 
	  /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) << 
	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
	  /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) << 
	  (bfs.isBNodeNewlyReached() ? ": is newly reached." : 
	   ": is not newly reached.");
      } else { 
	cout << "invalid" << /*endl*/", " << 
	  /*" aNode: " <<*/ node_name.get(bfs.aNode()) << 
	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
	  /*" bNode: " <<*/ 
	  "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;
    DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG);
    dfs.pushAndSetReached(t);
    while (!dfs.finished()) {
      ++dfs;
      //cout << "edge: ";
      if (wG.valid(dfs)) {
	cout << edge_name.get(dfs) << /*endl*/", " << 
	  /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) << 
	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
	  /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) << 
	  (dfs.isBNodeNewlyReached() ? ": is newly reached." : 
	   ": is not newly reached.");
      } else { 
	cout << "invalid" << /*endl*/", " << 
	  /*" aNode: " <<*/ node_name.get(dfs.aNode()) << 
	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
	  /*" bNode: " <<*/ 
	  "invalid.";
      }
      cout << endl;
    }
  }

  {
    typedef UndirGraphWrapper<const Graph> GW;
    GW wG(G);
    
    EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name);
    
    cout << "bfs and dfs iterator demo on the undirected graph" << endl;
    for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) { 
      cout << node_name.get(n) << ": ";
      cout << "out edges: ";
      for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e)) 
	cout << edge_name.get(e) << " ";
      cout << "in edges: ";
      for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e)) 
	cout << edge_name.get(e) << " ";
      cout << endl;
    }

    cout << "bfs from t ..." << endl;
    BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG);
    bfs.pushAndSetReached(t);
    while (!bfs.finished()) {
      //cout << "edge: ";
      if (wG.valid(GW::OutEdgeIt(bfs))) {
	cout << edge_name.get(GW::OutEdgeIt(bfs)) << /*endl*/", " << 
	  /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) << 
	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
	  /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) << 
	  (bfs.isBNodeNewlyReached() ? ": is newly reached." : 
	   ": is not newly reached.");
      } else { 
	cout << "invalid" << /*endl*/", " << 
	  /*" aNode: " <<*/ node_name.get(bfs.aNode()) << 
	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
	  /*" bNode: " <<*/ 
	  "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;
    DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG);
    dfs.pushAndSetReached(t);
    while (!dfs.finished()) {
      ++dfs;
      //cout << "edge: ";
      if (wG.valid(GW::OutEdgeIt(dfs))) {
	cout << edge_name.get(GW::OutEdgeIt(dfs)) << /*endl*/", " << 
	  /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) << 
	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
	  /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) << 
	  (dfs.isBNodeNewlyReached() ? ": is newly reached." : 
	   ": is not newly reached.");
      } else { 
	cout << "invalid" << /*endl*/", " << 
	  /*" aNode: " <<*/ node_name.get(dfs.aNode()) << 
	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
	  /*" bNode: " <<*/ 
	  "invalid.";
      }
      cout << endl;
    }
  }

  return 0;
}