COIN-OR::LEMON - Graph Library

source: lemon-0.x/demo/grid_graph_demo.cc @ 1681:84e43c7ca1e3

Last change on this file since 1681:84e43c7ca1e3 was 1681:84e43c7ca1e3, checked in by Balazs Dezso, 17 years ago

SubGraphAdaptors? with edge checking functionality.

Improved grid_graph_demo

File size: 1.8 KB
Line 
1#include <lemon/grid_graph.h>
2#include <lemon/graph_adaptor.h>
3#include <lemon/graph_to_eps.h>
4#include <lemon/bfs.h>
5#include <lemon/xy.h>
6
7#include <iostream>
8#include <fstream>
9
10using namespace lemon;
11using namespace std;
12
13int main() {
14  ifstream in("grid_graph_demo.in");
15  int width, height;
16  in >> width >> height;
17  int start_x, start_y;
18  in >> start_x >> start_y;
19  int stop_x, stop_y;
20  in >> stop_x >> stop_y;
21
22  GridGraph graph(width, height);
23  GridGraph::Node start = graph(start_x - 1, start_y - 1);
24  GridGraph::Node stop = graph(stop_x - 1, stop_y - 1);
25  GridGraph::NodeMap<bool> filter(graph);
26
27  for (int j = 0; j < height; ++j) {
28    in >> ws;
29    for (int i = 0; i < width; ++i) {
30      char c; in >> c;
31      filter[graph(i, j)] = (c == '.');
32    }
33  }
34
35  typedef NodeSubGraphAdaptor<GridGraph,
36    GridGraph::NodeMap<bool> > FilteredGraph;
37
38  FilteredGraph filtered(graph, filter);
39
40  Bfs<FilteredGraph> bfs(filtered);
41  std::cout << "The length of shortest path: " <<
42    bfs.run(start, stop) << std::endl;
43
44  GridGraph::NodeMap<xy<double> > coord(graph);
45  for (int i = 0; i < graph.width(); ++i) {
46    for (int j = 0; j < graph.height(); ++j) {
47      coord[graph(i, j)] = xy<double>( i * 10.0, j * 10.0);
48    }
49  }
50 
51  FilteredGraph::EdgeMap<Color> color(filtered, Color(0.0, 0.0, 0.0));
52 
53  for (GridGraph::Node node = stop;
54       node != start; node = bfs.predNode(node)) {
55    color[bfs.pred(node)] = Color(1.0, 0.0, 0.0);
56  }
57 
58  graphToEps(filtered, "grid_graph.eps").scaleToA4().
59    title("Grid graph").
60    copyright("(C) 2005 LEMON Project").
61    coords(coord).
62    enableParallel().
63    nodeScale(.45).
64    drawArrows().
65    edgeColors(color).
66    run();
67 
68  std::cout << "The shortest path is written to grid_graph.eps" << std::endl;
69
70  return 0;
71}
Note: See TracBrowser for help on using the repository browser.