[1680] | 1 | #include <lemon/grid_graph.h> |
---|
| 2 | #include <lemon/graph_adaptor.h> |
---|
| 3 | #include <lemon/graph_to_eps.h> |
---|
[1681] | 4 | #include <lemon/bfs.h> |
---|
[1680] | 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() { |
---|
[1681] | 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 | |
---|
[1680] | 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) { |
---|
[1681] | 47 | coord[graph(i, j)] = xy<double>( i * 10.0, j * 10.0); |
---|
[1680] | 48 | } |
---|
| 49 | } |
---|
[1681] | 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(). |
---|
[1680] | 59 | title("Grid graph"). |
---|
| 60 | copyright("(C) 2005 LEMON Project"). |
---|
| 61 | coords(coord). |
---|
| 62 | enableParallel(). |
---|
| 63 | nodeScale(.45). |
---|
| 64 | drawArrows(). |
---|
[1681] | 65 | edgeColors(color). |
---|
[1680] | 66 | run(); |
---|
[1681] | 67 | |
---|
| 68 | std::cout << "The shortest path is written to grid_graph.eps" << std::endl; |
---|
| 69 | |
---|
[1680] | 70 | return 0; |
---|
| 71 | } |
---|