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