/* -*- C++ -*-

  *

  * This file is a part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2003-2008

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * precise terms see the accompanying LICENSE file.

  *

  * This software is provided "AS IS" with no warranty of any kind,

  * express or implied, and with no claim as to its suitability for any

  * purpose.

  *

  */

 #include <lemon/grid_ugraph.h>

 #include <lemon/graph_adaptor.h>

 #include <lemon/graph_to_eps.h>

 #include <lemon/bfs.h>

 #include <lemon/dim2.h>

 #include <iostream>

 #include <fstream>

 ///\ingroup demos

 ///\file

 ///\brief Labirinth example with grid ugraph.

 ///

 ///  Labirinth example with grid ugraph.

 ///

 /// The input file is:

 ///

 /// \include grid_ugraph_demo.in

 ///

 /// The result:

 ///

 /// \image html grid_ugraph_demo.png

 /// \image latex grid_ugraph_demo.eps "The labirinth" width=\textwidth

 ///

 /// The source:

 ///

 /// \include grid_ugraph_demo.cc

 using namespace lemon;

 using namespace std;

 int main() {

   ifstream in("grid_ugraph_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;

   GridUGraph ugraph(width, height);

   GridUGraph::Node start = ugraph(start_x - 1, start_y - 1);

   GridUGraph::Node stop = ugraph(stop_x - 1, stop_y - 1);

   GridUGraph::NodeMap<bool> filter(ugraph);

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

     in >> ws;

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

       char c; in >> c;

       filter[ugraph(i, j)] = (c == '.');

     }

   }

   typedef NodeSubGraphAdaptor<GridUGraph,

     GridUGraph::NodeMap<bool> > FilteredGraph;

   FilteredGraph filtered(ugraph, 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 (GridUGraph::Node node = stop; 

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

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

   }

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

     title("Grid ugraph").

     copyright("(C) 2003-2007 LEMON Project").

     coords(scaleMap(indexMap(ugraph), 10)).

     enableParallel().

     nodeScale(0.5).

     drawArrows().

     edgeColors(composeMap(Palette(), path)).

     run();

   std::cout << "The shortest path is written to grid_ugraph_demo.eps" 

 	    << std::endl;

   return 0;

 }