[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 | |
---|
[1693] | 44 | FilteredGraph::EdgeMap<bool> path(filtered, false); |
---|
[1681] | 45 | |
---|
| 46 | for (GridGraph::Node node = stop; |
---|
| 47 | node != start; node = bfs.predNode(node)) { |
---|
[1763] | 48 | path[bfs.predEdge(node)] = true; |
---|
[1681] | 49 | } |
---|
| 50 | |
---|
| 51 | graphToEps(filtered, "grid_graph.eps").scaleToA4(). |
---|
[1680] | 52 | title("Grid graph"). |
---|
| 53 | copyright("(C) 2005 LEMON Project"). |
---|
[1693] | 54 | coords(scaleMap(indexMap(graph), 10)). |
---|
[1680] | 55 | enableParallel(). |
---|
[1693] | 56 | nodeScale(0.5). |
---|
[1680] | 57 | drawArrows(). |
---|
[1693] | 58 | edgeColors(composeMap(ColorSet(), path)). |
---|
[1680] | 59 | run(); |
---|
[1681] | 60 | |
---|
| 61 | std::cout << "The shortest path is written to grid_graph.eps" << std::endl; |
---|
| 62 | |
---|
[1680] | 63 | return 0; |
---|
| 64 | } |
---|