source: lemon-0.x/demo/grid_ugraph_demo.cc @ 2125:2f2cbe4e78a8

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2006
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#include <lemon/grid_ugraph.h>
#include <lemon/graph_adaptor.h>
#include <lemon/graph_to_eps.h>
#include <lemon/bfs.h>
#include <lemon/xy.h>

#include <iostream>
#include <fstream>

///\ingroup demos
///\file
///\brief Labirinth example with grid ugraph.
///
///  Labirinth example with grid ugraph.
///
/// The input file is:
///
/// \include grid_ugraph_demo.in
///
/// The result:
///
/// \image html grid_ugraph_demo.png
/// \image latex grid_ugraph_demo.eps "The labirinth" width=\textwidth
///
/// The source:
///
/// \include grid_ugraph_demo.cc

using namespace lemon;
using namespace std;

int main() {
  ifstream in("grid_ugraph_demo.in");
  int width, height;
  in >> width >> height;
  int start_x, start_y;
  in >> start_x >> start_y;
  int stop_x, stop_y;
  in >> stop_x >> stop_y;

  GridUGraph ugraph(width, height);
  GridUGraph::Node start = ugraph(start_x - 1, start_y - 1);
  GridUGraph::Node stop = ugraph(stop_x - 1, stop_y - 1);
  GridUGraph::NodeMap<bool> filter(ugraph);

  for (int j = 0; j < height; ++j) {
    in >> ws;
    for (int i = 0; i < width; ++i) {
      char c; in >> c;
      filter[ugraph(i, j)] = (c == '.');
    }
  }

  typedef NodeSubGraphAdaptor<GridUGraph,
    GridUGraph::NodeMap<bool> > FilteredGraph;

  FilteredGraph filtered(ugraph, filter);

  Bfs<FilteredGraph> bfs(filtered);
  std::cout << "The length of shortest path: " << 
    bfs.run(start, stop) << std::endl;

  FilteredGraph::EdgeMap<bool> path(filtered, false);
  
  for (GridUGraph::Node node = stop; 
       node != start; node = bfs.predNode(node)) {
    path[bfs.predEdge(node)] = true;
  }
  
  graphToEps(filtered, "grid_ugraph_demo.eps").scaleToA4().
    title("Grid ugraph").
    copyright("(C) 2006 LEMON Project").
    coords(scaleMap(indexMap(ugraph), 10)).
    enableParallel().
    nodeScale(0.5).
    drawArrows().
    edgeColors(composeMap(ColorSet(), path)).
    run();
  
  std::cout << "The shortest path is written to grid_ugraph_demo.eps" 
            << std::endl;

  return 0;
}