#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>

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;

  GridGraph::NodeMap<xy<double> > coord(graph);

  for (int i = 0; i < graph.width(); ++i) {

    for (int j = 0; j < graph.height(); ++j) {

      coord[graph(i, j)] = xy<double>( i * 10.0, j * 10.0);

    }

  }

  FilteredGraph::EdgeMap<Color> color(filtered, Color(0.0, 0.0, 0.0));

  for (GridGraph::Node node = stop; 

       node != start; node = bfs.predNode(node)) {

    color[bfs.pred(node)] = Color(1.0, 0.0, 0.0);

  }

  graphToEps(filtered, "grid_graph.eps").scaleToA4().

    title("Grid graph").

    copyright("(C) 2005 LEMON Project").

    coords(coord).

    enableParallel().

    nodeScale(.45).

    drawArrows().

    edgeColors(color).

    run();

  std::cout << "The shortest path is written to grid_graph.eps" << std::endl;

  return 0;

}