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 | } |
---|