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

 }