demo/grid_graph_demo.cc
author alpar
Wed, 04 Jan 2006 13:31:59 +0000
changeset 1875 98698b69a902
parent 1775 f19e108cb286
child 1956 a055123339d5
permissions -rw-r--r--
Happy new year to LEMON
     1 #include <lemon/grid_graph.h>
     2 #include <lemon/graph_adaptor.h>
     3 #include <lemon/graph_to_eps.h>
     4 #include <lemon/bfs.h>
     5 #include <lemon/xy.h>
     6 
     7 #include <iostream>
     8 #include <fstream>
     9 
    10 ///\ingroup demos
    11 ///\file
    12 ///\brief Labirinth example with grid graph.
    13 ///
    14 ///  Labirinth example with grid graph.
    15 ///
    16 /// The input file is:
    17 ///
    18 /// \include grid_graph_demo.in
    19 ///
    20 /// The result:
    21 ///
    22 /// \image html grid_graph_demo.png
    23 /// \image latex grid_graph_demo.eps "The labirinth" width=\textwidth
    24 ///
    25 /// The source:
    26 ///
    27 /// \include grid_graph_demo.cc
    28 
    29 using namespace lemon;
    30 using namespace std;
    31 
    32 int main() {
    33   ifstream in("grid_graph_demo.in");
    34   int width, height;
    35   in >> width >> height;
    36   int start_x, start_y;
    37   in >> start_x >> start_y;
    38   int stop_x, stop_y;
    39   in >> stop_x >> stop_y;
    40 
    41   GridGraph graph(width, height);
    42   GridGraph::Node start = graph(start_x - 1, start_y - 1);
    43   GridGraph::Node stop = graph(stop_x - 1, stop_y - 1);
    44   GridGraph::NodeMap<bool> filter(graph);
    45 
    46   for (int j = 0; j < height; ++j) {
    47     in >> ws;
    48     for (int i = 0; i < width; ++i) {
    49       char c; in >> c;
    50       filter[graph(i, j)] = (c == '.');
    51     }
    52   }
    53 
    54   typedef NodeSubGraphAdaptor<GridGraph,
    55     GridGraph::NodeMap<bool> > FilteredGraph;
    56 
    57   FilteredGraph filtered(graph, filter);
    58 
    59   Bfs<FilteredGraph> bfs(filtered);
    60   std::cout << "The length of shortest path: " << 
    61     bfs.run(start, stop) << std::endl;
    62 
    63   FilteredGraph::EdgeMap<bool> path(filtered, false);
    64   
    65   for (GridGraph::Node node = stop; 
    66        node != start; node = bfs.predNode(node)) {
    67     path[bfs.predEdge(node)] = true;
    68   }
    69   
    70   graphToEps(filtered, "grid_graph_demo.eps").scaleToA4().
    71     title("Grid graph").
    72     copyright("(C) 2006 LEMON Project").
    73     coords(scaleMap(indexMap(graph), 10)).
    74     enableParallel().
    75     nodeScale(0.5).
    76     drawArrows().
    77     edgeColors(composeMap(ColorSet(), path)).
    78     run();
    79   
    80   std::cout << "The shortest path is written to grid_graph_demo.eps" 
    81 	    << std::endl;
    82 
    83   return 0;
    84 }