The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor, where
we have to proxy the signals from the graph.
The SubBidirGraphAdaptor is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor<UndirGraphAdaptor<Graph>>.
The ResGraphAdaptor is based on this composition.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
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>
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) 2006 LEMON Project").
91 coords(scaleMap(indexMap(ugraph), 10)).
95 edgeColors(composeMap(ColorSet(), path)).
98 std::cout << "The shortest path is written to grid_ugraph_demo.eps"