alpar@1956: /* -*- C++ -*- alpar@1956: * alpar@1956: * This file is a part of LEMON, a generic C++ optimization library alpar@1956: * alpar@1956: * Copyright (C) 2003-2006 alpar@1956: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@1956: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@1956: * alpar@1956: * Permission to use, modify and distribute this software is granted alpar@1956: * provided that this copyright notice appears in all copies. For alpar@1956: * precise terms see the accompanying LICENSE file. alpar@1956: * alpar@1956: * This software is provided "AS IS" with no warranty of any kind, alpar@1956: * express or implied, and with no claim as to its suitability for any alpar@1956: * purpose. alpar@1956: * alpar@1956: */ alpar@1956: 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@1775: ///\ingroup demos deba@1775: ///\file deba@1775: ///\brief Labirinth example with grid graph. deba@1775: /// deba@1775: /// Labirinth example with grid graph. deba@1775: /// deba@1775: /// The input file is: deba@1775: /// deba@1775: /// \include grid_graph_demo.in deba@1775: /// deba@1775: /// The result: deba@1775: /// deba@1775: /// \image html grid_graph_demo.png deba@1775: /// \image latex grid_graph_demo.eps "The labirinth" width=\textwidth deba@1775: /// deba@1775: /// The source: deba@1775: /// deba@1775: /// \include grid_graph_demo.cc deba@1775: 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@1693: FilteredGraph::EdgeMap path(filtered, false); deba@1681: deba@1681: for (GridGraph::Node node = stop; deba@1681: node != start; node = bfs.predNode(node)) { deba@1763: path[bfs.predEdge(node)] = true; deba@1681: } deba@1681: deba@1775: graphToEps(filtered, "grid_graph_demo.eps").scaleToA4(). deba@1680: title("Grid graph"). alpar@1875: copyright("(C) 2006 LEMON Project"). deba@1693: coords(scaleMap(indexMap(graph), 10)). deba@1680: enableParallel(). deba@1693: nodeScale(0.5). deba@1680: drawArrows(). deba@1693: edgeColors(composeMap(ColorSet(), path)). deba@1680: run(); deba@1681: deba@1775: std::cout << "The shortest path is written to grid_graph_demo.eps" deba@1775: << std::endl; deba@1681: deba@1680: return 0; deba@1680: }