/* -*- C++ -*-

 *

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

 *

 * Copyright (C) 2003-2006

 * 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) 2006 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;

}