demo/grid_graph_demo.cc
author deba
Mon, 12 Sep 2005 11:24:54 +0000
changeset 1681 84e43c7ca1e3
parent 1680 4f8b9cee576b
child 1693 269f0cbfbcc8
permissions -rw-r--r--
SubGraphAdaptors with edge checking functionality.

Improved grid_graph_demo
     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 using namespace lemon;
    11 using namespace std;
    12 
    13 int main() {
    14   ifstream in("grid_graph_demo.in");
    15   int width, height;
    16   in >> width >> height;
    17   int start_x, start_y;
    18   in >> start_x >> start_y;
    19   int stop_x, stop_y;
    20   in >> stop_x >> stop_y;
    21 
    22   GridGraph graph(width, height);
    23   GridGraph::Node start = graph(start_x - 1, start_y - 1);
    24   GridGraph::Node stop = graph(stop_x - 1, stop_y - 1);
    25   GridGraph::NodeMap<bool> filter(graph);
    26 
    27   for (int j = 0; j < height; ++j) {
    28     in >> ws;
    29     for (int i = 0; i < width; ++i) {
    30       char c; in >> c;
    31       filter[graph(i, j)] = (c == '.');
    32     }
    33   }
    34 
    35   typedef NodeSubGraphAdaptor<GridGraph,
    36     GridGraph::NodeMap<bool> > FilteredGraph;
    37 
    38   FilteredGraph filtered(graph, filter);
    39 
    40   Bfs<FilteredGraph> bfs(filtered);
    41   std::cout << "The length of shortest path: " << 
    42     bfs.run(start, stop) << std::endl;
    43 
    44   GridGraph::NodeMap<xy<double> > coord(graph);
    45   for (int i = 0; i < graph.width(); ++i) {
    46     for (int j = 0; j < graph.height(); ++j) {
    47       coord[graph(i, j)] = xy<double>( i * 10.0, j * 10.0);
    48     }
    49   }
    50   
    51   FilteredGraph::EdgeMap<Color> color(filtered, Color(0.0, 0.0, 0.0));
    52   
    53   for (GridGraph::Node node = stop; 
    54        node != start; node = bfs.predNode(node)) {
    55     color[bfs.pred(node)] = Color(1.0, 0.0, 0.0);
    56   }
    57   
    58   graphToEps(filtered, "grid_graph.eps").scaleToA4().
    59     title("Grid graph").
    60     copyright("(C) 2005 LEMON Project").
    61     coords(coord).
    62     enableParallel().
    63     nodeScale(.45).
    64     drawArrows().
    65     edgeColors(color).
    66     run();
    67   
    68   std::cout << "The shortest path is written to grid_graph.eps" << std::endl;
    69 
    70   return 0;
    71 }