demo/grid_graph_demo.cc
author alpar
Mon, 24 Oct 2005 08:12:26 +0000
changeset 1736 35f667e7dd7e
parent 1681 84e43c7ca1e3
child 1763 49045f2d28d4
permissions -rw-r--r--
Doxyfile for documenting glemon's architecture.
deba@1680
     1
#include <lemon/grid_graph.h>
deba@1680
     2
#include <lemon/graph_adaptor.h>
deba@1680
     3
#include <lemon/graph_to_eps.h>
deba@1681
     4
#include <lemon/bfs.h>
deba@1680
     5
#include <lemon/xy.h>
deba@1680
     6
deba@1680
     7
#include <iostream>
deba@1680
     8
#include <fstream>
deba@1680
     9
deba@1680
    10
using namespace lemon;
deba@1680
    11
using namespace std;
deba@1680
    12
deba@1680
    13
int main() {
deba@1681
    14
  ifstream in("grid_graph_demo.in");
deba@1681
    15
  int width, height;
deba@1681
    16
  in >> width >> height;
deba@1681
    17
  int start_x, start_y;
deba@1681
    18
  in >> start_x >> start_y;
deba@1681
    19
  int stop_x, stop_y;
deba@1681
    20
  in >> stop_x >> stop_y;
deba@1681
    21
deba@1681
    22
  GridGraph graph(width, height);
deba@1681
    23
  GridGraph::Node start = graph(start_x - 1, start_y - 1);
deba@1681
    24
  GridGraph::Node stop = graph(stop_x - 1, stop_y - 1);
deba@1681
    25
  GridGraph::NodeMap<bool> filter(graph);
deba@1681
    26
deba@1681
    27
  for (int j = 0; j < height; ++j) {
deba@1681
    28
    in >> ws;
deba@1681
    29
    for (int i = 0; i < width; ++i) {
deba@1681
    30
      char c; in >> c;
deba@1681
    31
      filter[graph(i, j)] = (c == '.');
deba@1681
    32
    }
deba@1681
    33
  }
deba@1681
    34
deba@1681
    35
  typedef NodeSubGraphAdaptor<GridGraph,
deba@1681
    36
    GridGraph::NodeMap<bool> > FilteredGraph;
deba@1681
    37
deba@1681
    38
  FilteredGraph filtered(graph, filter);
deba@1681
    39
deba@1681
    40
  Bfs<FilteredGraph> bfs(filtered);
deba@1681
    41
  std::cout << "The length of shortest path: " << 
deba@1681
    42
    bfs.run(start, stop) << std::endl;
deba@1681
    43
deba@1693
    44
  FilteredGraph::EdgeMap<bool> path(filtered, false);
deba@1681
    45
  
deba@1681
    46
  for (GridGraph::Node node = stop; 
deba@1681
    47
       node != start; node = bfs.predNode(node)) {
deba@1693
    48
    path[bfs.pred(node)] = true;
deba@1681
    49
  }
deba@1681
    50
  
deba@1681
    51
  graphToEps(filtered, "grid_graph.eps").scaleToA4().
deba@1680
    52
    title("Grid graph").
deba@1680
    53
    copyright("(C) 2005 LEMON Project").
deba@1693
    54
    coords(scaleMap(indexMap(graph), 10)).
deba@1680
    55
    enableParallel().
deba@1693
    56
    nodeScale(0.5).
deba@1680
    57
    drawArrows().
deba@1693
    58
    edgeColors(composeMap(ColorSet(), path)).
deba@1680
    59
    run();
deba@1681
    60
  
deba@1681
    61
  std::cout << "The shortest path is written to grid_graph.eps" << std::endl;
deba@1681
    62
deba@1680
    63
  return 0;
deba@1680
    64
}