COIN-OR::LEMON - Graph Library

source: lemon-0.x/demo/grid_graph_demo.cc @ 1930:92b70deed0c5

Last change on this file since 1930:92b70deed0c5 was 1875:98698b69a902, checked in by Alpar Juttner, 14 years ago

Happy new year to LEMON

File size: 1.9 KB
RevLine 
[1680]1#include <lemon/grid_graph.h>
2#include <lemon/graph_adaptor.h>
3#include <lemon/graph_to_eps.h>
[1681]4#include <lemon/bfs.h>
[1680]5#include <lemon/xy.h>
6
7#include <iostream>
8#include <fstream>
9
[1775]10///\ingroup demos
11///\file
12///\brief Labirinth example with grid graph.
13///
14///  Labirinth example with grid graph.
15///
16/// The input file is:
17///
18/// \include grid_graph_demo.in
19///
20/// The result:
21///
22/// \image html grid_graph_demo.png
23/// \image latex grid_graph_demo.eps "The labirinth" width=\textwidth
24///
25/// The source:
26///
27/// \include grid_graph_demo.cc
28
[1680]29using namespace lemon;
30using namespace std;
31
32int main() {
[1681]33  ifstream in("grid_graph_demo.in");
34  int width, height;
35  in >> width >> height;
36  int start_x, start_y;
37  in >> start_x >> start_y;
38  int stop_x, stop_y;
39  in >> stop_x >> stop_y;
40
41  GridGraph graph(width, height);
42  GridGraph::Node start = graph(start_x - 1, start_y - 1);
43  GridGraph::Node stop = graph(stop_x - 1, stop_y - 1);
44  GridGraph::NodeMap<bool> filter(graph);
45
46  for (int j = 0; j < height; ++j) {
47    in >> ws;
48    for (int i = 0; i < width; ++i) {
49      char c; in >> c;
50      filter[graph(i, j)] = (c == '.');
51    }
52  }
53
54  typedef NodeSubGraphAdaptor<GridGraph,
55    GridGraph::NodeMap<bool> > FilteredGraph;
56
57  FilteredGraph filtered(graph, filter);
58
59  Bfs<FilteredGraph> bfs(filtered);
60  std::cout << "The length of shortest path: " <<
61    bfs.run(start, stop) << std::endl;
62
[1693]63  FilteredGraph::EdgeMap<bool> path(filtered, false);
[1681]64 
65  for (GridGraph::Node node = stop;
66       node != start; node = bfs.predNode(node)) {
[1763]67    path[bfs.predEdge(node)] = true;
[1681]68  }
69 
[1775]70  graphToEps(filtered, "grid_graph_demo.eps").scaleToA4().
[1680]71    title("Grid graph").
[1875]72    copyright("(C) 2006 LEMON Project").
[1693]73    coords(scaleMap(indexMap(graph), 10)).
[1680]74    enableParallel().
[1693]75    nodeScale(0.5).
[1680]76    drawArrows().
[1693]77    edgeColors(composeMap(ColorSet(), path)).
[1680]78    run();
[1681]79 
[1775]80  std::cout << "The shortest path is written to grid_graph_demo.eps"
81            << std::endl;
[1681]82
[1680]83  return 0;
84}
Note: See TracBrowser for help on using the repository browser.