alpar@1956: /* -*- C++ -*-
alpar@1956:  *
alpar@1956:  * This file is a part of LEMON, a generic C++ optimization library
alpar@1956:  *
alpar@1956:  * Copyright (C) 2003-2006
alpar@1956:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1956:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@1956:  *
alpar@1956:  * Permission to use, modify and distribute this software is granted
alpar@1956:  * provided that this copyright notice appears in all copies. For
alpar@1956:  * precise terms see the accompanying LICENSE file.
alpar@1956:  *
alpar@1956:  * This software is provided "AS IS" with no warranty of any kind,
alpar@1956:  * express or implied, and with no claim as to its suitability for any
alpar@1956:  * purpose.
alpar@1956:  *
alpar@1956:  */
alpar@1956: 
deba@1680: #include <lemon/grid_graph.h>
deba@1680: #include <lemon/graph_adaptor.h>
deba@1680: #include <lemon/graph_to_eps.h>
deba@1681: #include <lemon/bfs.h>
deba@1680: #include <lemon/xy.h>
deba@1680: 
deba@1680: #include <iostream>
deba@1680: #include <fstream>
deba@1680: 
deba@1775: ///\ingroup demos
deba@1775: ///\file
deba@1775: ///\brief Labirinth example with grid graph.
deba@1775: ///
deba@1775: ///  Labirinth example with grid graph.
deba@1775: ///
deba@1775: /// The input file is:
deba@1775: ///
deba@1775: /// \include grid_graph_demo.in
deba@1775: ///
deba@1775: /// The result:
deba@1775: ///
deba@1775: /// \image html grid_graph_demo.png
deba@1775: /// \image latex grid_graph_demo.eps "The labirinth" width=\textwidth
deba@1775: ///
deba@1775: /// The source:
deba@1775: ///
deba@1775: /// \include grid_graph_demo.cc
deba@1775: 
deba@1680: using namespace lemon;
deba@1680: using namespace std;
deba@1680: 
deba@1680: int main() {
deba@1681:   ifstream in("grid_graph_demo.in");
deba@1681:   int width, height;
deba@1681:   in >> width >> height;
deba@1681:   int start_x, start_y;
deba@1681:   in >> start_x >> start_y;
deba@1681:   int stop_x, stop_y;
deba@1681:   in >> stop_x >> stop_y;
deba@1681: 
deba@1681:   GridGraph graph(width, height);
deba@1681:   GridGraph::Node start = graph(start_x - 1, start_y - 1);
deba@1681:   GridGraph::Node stop = graph(stop_x - 1, stop_y - 1);
deba@1681:   GridGraph::NodeMap<bool> filter(graph);
deba@1681: 
deba@1681:   for (int j = 0; j < height; ++j) {
deba@1681:     in >> ws;
deba@1681:     for (int i = 0; i < width; ++i) {
deba@1681:       char c; in >> c;
deba@1681:       filter[graph(i, j)] = (c == '.');
deba@1681:     }
deba@1681:   }
deba@1681: 
deba@1681:   typedef NodeSubGraphAdaptor<GridGraph,
deba@1681:     GridGraph::NodeMap<bool> > FilteredGraph;
deba@1681: 
deba@1681:   FilteredGraph filtered(graph, filter);
deba@1681: 
deba@1681:   Bfs<FilteredGraph> bfs(filtered);
deba@1681:   std::cout << "The length of shortest path: " << 
deba@1681:     bfs.run(start, stop) << std::endl;
deba@1681: 
deba@1693:   FilteredGraph::EdgeMap<bool> path(filtered, false);
deba@1681:   
deba@1681:   for (GridGraph::Node node = stop; 
deba@1681:        node != start; node = bfs.predNode(node)) {
deba@1763:     path[bfs.predEdge(node)] = true;
deba@1681:   }
deba@1681:   
deba@1775:   graphToEps(filtered, "grid_graph_demo.eps").scaleToA4().
deba@1680:     title("Grid graph").
alpar@1875:     copyright("(C) 2006 LEMON Project").
deba@1693:     coords(scaleMap(indexMap(graph), 10)).
deba@1680:     enableParallel().
deba@1693:     nodeScale(0.5).
deba@1680:     drawArrows().
deba@1693:     edgeColors(composeMap(ColorSet(), path)).
deba@1680:     run();
deba@1681:   
deba@1775:   std::cout << "The shortest path is written to grid_graph_demo.eps" 
deba@1775: 	    << std::endl;
deba@1681: 
deba@1680:   return 0;
deba@1680: }