#include <lemon/grid_graph.h>
#include <lemon/graph_adaptor.h>
#include <lemon/graph_to_eps.h>
#include <lemon/bfs.h>
#include <lemon/xy.h>

#include <iostream>
#include <fstream>

///\ingroup demos
///\file
///\brief Labirinth example with grid graph.
///
///  Labirinth example with grid graph.
///
/// The input file is:
///
/// \include grid_graph_demo.in
///
/// The result:
///
/// \image html grid_graph_demo.png
/// \image latex grid_graph_demo.eps "The labirinth" width=\textwidth
///
/// The source:
///
/// \include grid_graph_demo.cc

using namespace lemon;
using namespace std;

int main() {
  ifstream in("grid_graph_demo.in");
  int width, height;
  in >> width >> height;
  int start_x, start_y;
  in >> start_x >> start_y;
  int stop_x, stop_y;
  in >> stop_x >> stop_y;

  GridGraph graph(width, height);
  GridGraph::Node start = graph(start_x - 1, start_y - 1);
  GridGraph::Node stop = graph(stop_x - 1, stop_y - 1);
  GridGraph::NodeMap<bool> filter(graph);

  for (int j = 0; j < height; ++j) {
    in >> ws;
    for (int i = 0; i < width; ++i) {
      char c; in >> c;
      filter[graph(i, j)] = (c == '.');
    }
  }

  typedef NodeSubGraphAdaptor<GridGraph,
    GridGraph::NodeMap<bool> > FilteredGraph;

  FilteredGraph filtered(graph, filter);

  Bfs<FilteredGraph> bfs(filtered);
  std::cout << "The length of shortest path: " << 
    bfs.run(start, stop) << std::endl;

  FilteredGraph::EdgeMap<bool> path(filtered, false);
  
  for (GridGraph::Node node = stop; 
       node != start; node = bfs.predNode(node)) {
    path[bfs.predEdge(node)] = true;
  }
  
  graphToEps(filtered, "grid_graph_demo.eps").scaleToA4().
    title("Grid graph").
    copyright("(C) 2006 LEMON Project").
    coords(scaleMap(indexMap(graph), 10)).
    enableParallel().
    nodeScale(0.5).
    drawArrows().
    edgeColors(composeMap(ColorSet(), path)).
    run();
  
  std::cout << "The shortest path is written to grid_graph_demo.eps" 
	    << std::endl;

  return 0;
}