deba@1680: #include deba@1680: #include deba@1680: #include deba@1681: #include deba@1680: #include deba@1680: deba@1680: #include deba@1680: #include deba@1680: deba@1680: using namespace lemon; deba@1680: using namespace std; deba@1680: deba@1680: int main() { deba@1681: ifstream in("grid_graph_demo.in"); deba@1681: int width, height; deba@1681: in >> width >> height; deba@1681: int start_x, start_y; deba@1681: in >> start_x >> start_y; deba@1681: int stop_x, stop_y; deba@1681: in >> stop_x >> stop_y; deba@1681: deba@1681: GridGraph graph(width, height); deba@1681: GridGraph::Node start = graph(start_x - 1, start_y - 1); deba@1681: GridGraph::Node stop = graph(stop_x - 1, stop_y - 1); deba@1681: GridGraph::NodeMap filter(graph); deba@1681: deba@1681: for (int j = 0; j < height; ++j) { deba@1681: in >> ws; deba@1681: for (int i = 0; i < width; ++i) { deba@1681: char c; in >> c; deba@1681: filter[graph(i, j)] = (c == '.'); deba@1681: } deba@1681: } deba@1681: deba@1681: typedef NodeSubGraphAdaptor > FilteredGraph; deba@1681: deba@1681: FilteredGraph filtered(graph, filter); deba@1681: deba@1681: Bfs bfs(filtered); deba@1681: std::cout << "The length of shortest path: " << deba@1681: bfs.run(start, stop) << std::endl; deba@1681: deba@1680: GridGraph::NodeMap > coord(graph); deba@1680: for (int i = 0; i < graph.width(); ++i) { deba@1680: for (int j = 0; j < graph.height(); ++j) { deba@1681: coord[graph(i, j)] = xy( i * 10.0, j * 10.0); deba@1680: } deba@1680: } deba@1681: deba@1681: FilteredGraph::EdgeMap color(filtered, Color(0.0, 0.0, 0.0)); deba@1681: deba@1681: for (GridGraph::Node node = stop; deba@1681: node != start; node = bfs.predNode(node)) { deba@1681: color[bfs.pred(node)] = Color(1.0, 0.0, 0.0); deba@1681: } deba@1681: deba@1681: graphToEps(filtered, "grid_graph.eps").scaleToA4(). deba@1680: title("Grid graph"). deba@1680: copyright("(C) 2005 LEMON Project"). deba@1680: coords(coord). deba@1680: enableParallel(). deba@1680: nodeScale(.45). deba@1680: drawArrows(). deba@1681: edgeColors(color). deba@1680: run(); deba@1681: deba@1681: std::cout << "The shortest path is written to grid_graph.eps" << std::endl; deba@1681: deba@1680: return 0; deba@1680: }