Added SimplePath::front().
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #include <lemon/grid_ugraph.h>
20 #include <lemon/graph_adaptor.h>
21 #include <lemon/graph_to_eps.h>
22 #include <lemon/bfs.h>
23 #include <lemon/dim2.h>
30 ///\brief Labirinth example with grid ugraph.
32 /// Labirinth example with grid ugraph.
34 /// The input file is:
36 /// \include grid_ugraph_demo.in
40 /// \image html grid_ugraph_demo.png
41 /// \image latex grid_ugraph_demo.eps "The labirinth" width=\textwidth
45 /// \include grid_ugraph_demo.cc
47 using namespace lemon;
51 ifstream in("grid_ugraph_demo.in");
53 in >> width >> height;
55 in >> start_x >> start_y;
57 in >> stop_x >> stop_y;
59 GridUGraph ugraph(width, height);
60 GridUGraph::Node start = ugraph(start_x - 1, start_y - 1);
61 GridUGraph::Node stop = ugraph(stop_x - 1, stop_y - 1);
62 GridUGraph::NodeMap<bool> filter(ugraph);
64 for (int j = 0; j < height; ++j) {
66 for (int i = 0; i < width; ++i) {
68 filter[ugraph(i, j)] = (c == '.');
72 typedef NodeSubGraphAdaptor<GridUGraph,
73 GridUGraph::NodeMap<bool> > FilteredGraph;
75 FilteredGraph filtered(ugraph, filter);
77 Bfs<FilteredGraph> bfs(filtered);
78 std::cout << "The length of shortest path: " <<
79 bfs.run(start, stop) << std::endl;
81 FilteredGraph::EdgeMap<bool> path(filtered, false);
83 for (GridUGraph::Node node = stop;
84 node != start; node = bfs.predNode(node)) {
85 path[bfs.predEdge(node)] = true;
88 graphToEps(filtered, "grid_ugraph_demo.eps").scaleToA4().
90 copyright("(C) 2003-2007 LEMON Project").
91 coords(scaleMap(indexMap(ugraph), 10)).
95 edgeColors(composeMap(Palette(), path)).
98 std::cout << "The shortest path is written to grid_ugraph_demo.eps"