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