[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 | |
---|
[1775] | 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 | |
---|
[1680] | 29 | using namespace lemon; |
---|
| 30 | using namespace std; |
---|
| 31 | |
---|
| 32 | int main() { |
---|
[1681] | 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 | |
---|
[1693] | 63 | FilteredGraph::EdgeMap<bool> path(filtered, false); |
---|
[1681] | 64 | |
---|
| 65 | for (GridGraph::Node node = stop; |
---|
| 66 | node != start; node = bfs.predNode(node)) { |
---|
[1763] | 67 | path[bfs.predEdge(node)] = true; |
---|
[1681] | 68 | } |
---|
| 69 | |
---|
[1775] | 70 | graphToEps(filtered, "grid_graph_demo.eps").scaleToA4(). |
---|
[1680] | 71 | title("Grid graph"). |
---|
| 72 | copyright("(C) 2005 LEMON Project"). |
---|
[1693] | 73 | coords(scaleMap(indexMap(graph), 10)). |
---|
[1680] | 74 | enableParallel(). |
---|
[1693] | 75 | nodeScale(0.5). |
---|
[1680] | 76 | drawArrows(). |
---|
[1693] | 77 | edgeColors(composeMap(ColorSet(), path)). |
---|
[1680] | 78 | run(); |
---|
[1681] | 79 | |
---|
[1775] | 80 | std::cout << "The shortest path is written to grid_graph_demo.eps" |
---|
| 81 | << std::endl; |
---|
[1681] | 82 | |
---|
[1680] | 83 | return 0; |
---|
| 84 | } |
---|