/* -*- C++ -*- * * This file is a part of LEMON, a generic C++ optimization library * * Copyright (C) 2003-2006 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * * Permission to use, modify and distribute this software is granted * provided that this copyright notice appears in all copies. For * precise terms see the accompanying LICENSE file. * * This software is provided "AS IS" with no warranty of any kind, * express or implied, and with no claim as to its suitability for any * purpose. * */ #include #include #include #include #include #include #include ///\ingroup demos ///\file ///\brief Labirinth example with grid ugraph. /// /// Labirinth example with grid ugraph. /// /// The input file is: /// /// \include grid_ugraph_demo.in /// /// The result: /// /// \image html grid_ugraph_demo.png /// \image latex grid_ugraph_demo.eps "The labirinth" width=\textwidth /// /// The source: /// /// \include grid_ugraph_demo.cc using namespace lemon; using namespace std; int main() { ifstream in("grid_ugraph_demo.in"); int width, height; in >> width >> height; int start_x, start_y; in >> start_x >> start_y; int stop_x, stop_y; in >> stop_x >> stop_y; GridUGraph ugraph(width, height); GridUGraph::Node start = ugraph(start_x - 1, start_y - 1); GridUGraph::Node stop = ugraph(stop_x - 1, stop_y - 1); GridUGraph::NodeMap filter(ugraph); for (int j = 0; j < height; ++j) { in >> ws; for (int i = 0; i < width; ++i) { char c; in >> c; filter[ugraph(i, j)] = (c == '.'); } } typedef NodeSubGraphAdaptor > FilteredGraph; FilteredGraph filtered(ugraph, filter); Bfs bfs(filtered); std::cout << "The length of shortest path: " << bfs.run(start, stop) << std::endl; FilteredGraph::EdgeMap path(filtered, false); for (GridUGraph::Node node = stop; node != start; node = bfs.predNode(node)) { path[bfs.predEdge(node)] = true; } graphToEps(filtered, "grid_ugraph_demo.eps").scaleToA4(). title("Grid ugraph"). copyright("(C) 2006 LEMON Project"). coords(scaleMap(indexMap(ugraph), 10)). enableParallel(). nodeScale(0.5). drawArrows(). edgeColors(composeMap(ColorSet(), path)). run(); std::cout << "The shortest path is written to grid_ugraph_demo.eps" << std::endl; return 0; }