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 | FilteredGraph::EdgeMap<bool> path(filtered, false); |
---|

45 | |
---|

46 | for (GridGraph::Node node = stop; |
---|

47 | node != start; node = bfs.predNode(node)) { |
---|

48 | path[bfs.pred(node)] = true; |
---|

49 | } |
---|

50 | |
---|

51 | graphToEps(filtered, "grid_graph.eps").scaleToA4(). |
---|

52 | title("Grid graph"). |
---|

53 | copyright("(C) 2005 LEMON Project"). |
---|

54 | coords(scaleMap(indexMap(graph), 10)). |
---|

55 | enableParallel(). |
---|

56 | nodeScale(0.5). |
---|

57 | drawArrows(). |
---|

58 | edgeColors(composeMap(ColorSet(), path)). |
---|

59 | run(); |
---|

60 | |
---|

61 | std::cout << "The shortest path is written to grid_graph.eps" << std::endl; |
---|

62 | |
---|

63 | return 0; |
---|

64 | } |
---|