1 #include <lemon/grid_graph.h> |
1 #include <lemon/grid_graph.h> |
2 #include <lemon/graph_adaptor.h> |
2 #include <lemon/graph_adaptor.h> |
3 #include <lemon/graph_to_eps.h> |
3 #include <lemon/graph_to_eps.h> |
|
4 #include <lemon/bfs.h> |
4 #include <lemon/xy.h> |
5 #include <lemon/xy.h> |
5 |
6 |
6 #include <iostream> |
7 #include <iostream> |
7 #include <fstream> |
8 #include <fstream> |
8 |
9 |
9 using namespace lemon; |
10 using namespace lemon; |
10 using namespace std; |
11 using namespace std; |
11 |
12 |
12 int main() { |
13 int main() { |
13 GridGraph graph(5, 7); |
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 |
14 GridGraph::NodeMap<xy<double> > coord(graph); |
44 GridGraph::NodeMap<xy<double> > coord(graph); |
15 for (int i = 0; i < graph.width(); ++i) { |
45 for (int i = 0; i < graph.width(); ++i) { |
16 for (int j = 0; j < graph.height(); ++j) { |
46 for (int j = 0; j < graph.height(); ++j) { |
17 coord[graph(i, j)] = xy<double>(i * 10.0, j * 10.0); |
47 coord[graph(i, j)] = xy<double>( i * 10.0, j * 10.0); |
18 } |
48 } |
19 } |
49 } |
20 graphToEps(graph, "grid_graph.eps").scaleToA4(). |
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(). |
21 title("Grid graph"). |
59 title("Grid graph"). |
22 copyright("(C) 2005 LEMON Project"). |
60 copyright("(C) 2005 LEMON Project"). |
23 coords(coord). |
61 coords(coord). |
24 enableParallel(). |
62 enableParallel(). |
25 nodeScale(.45). |
63 nodeScale(.45). |
26 drawArrows(). |
64 drawArrows(). |
|
65 edgeColors(color). |
27 run(); |
66 run(); |
|
67 |
|
68 std::cout << "The shortest path is written to grid_graph.eps" << std::endl; |
|
69 |
28 return 0; |
70 return 0; |
29 } |
71 } |