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

   FilteredGraph::EdgeMap<bool> path(filtered, false);

   for (GridGraph::Node node = stop; 

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

     path[bfs.pred(node)] = true;

   }

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

     title("Grid graph").

     copyright("(C) 2005 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.eps" << std::endl;

   return 0;

 }