1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/demo/grid_ugraph_demo.cc	Wed Feb 22 18:26:56 2006 +0000
     1.3 @@ -0,0 +1,102 @@
     1.4 +/* -*- C++ -*-
     1.5 + *
     1.6 + * This file is a part of LEMON, a generic C++ optimization library
     1.7 + *
     1.8 + * Copyright (C) 2003-2006
     1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.11 + *
    1.12 + * Permission to use, modify and distribute this software is granted
    1.13 + * provided that this copyright notice appears in all copies. For
    1.14 + * precise terms see the accompanying LICENSE file.
    1.15 + *
    1.16 + * This software is provided "AS IS" with no warranty of any kind,
    1.17 + * express or implied, and with no claim as to its suitability for any
    1.18 + * purpose.
    1.19 + *
    1.20 + */
    1.21 +
    1.22 +#include <lemon/grid_ugraph.h>
    1.23 +#include <lemon/graph_adaptor.h>
    1.24 +#include <lemon/graph_to_eps.h>
    1.25 +#include <lemon/bfs.h>
    1.26 +#include <lemon/xy.h>
    1.27 +
    1.28 +#include <iostream>
    1.29 +#include <fstream>
    1.30 +
    1.31 +///\ingroup demos
    1.32 +///\file
    1.33 +///\brief Labirinth example with grid ugraph.
    1.34 +///
    1.35 +///  Labirinth example with grid ugraph.
    1.36 +///
    1.37 +/// The input file is:
    1.38 +///
    1.39 +/// \include grid_ugraph_demo.in
    1.40 +///
    1.41 +/// The result:
    1.42 +///
    1.43 +/// \image html grid_ugraph_demo.png
    1.44 +/// \image latex grid_ugraph_demo.eps "The labirinth" width=\textwidth
    1.45 +///
    1.46 +/// The source:
    1.47 +///
    1.48 +/// \include grid_ugraph_demo.cc
    1.49 +
    1.50 +using namespace lemon;
    1.51 +using namespace std;
    1.52 +
    1.53 +int main() {
    1.54 +  ifstream in("grid_ugraph_demo.in");
    1.55 +  int width, height;
    1.56 +  in >> width >> height;
    1.57 +  int start_x, start_y;
    1.58 +  in >> start_x >> start_y;
    1.59 +  int stop_x, stop_y;
    1.60 +  in >> stop_x >> stop_y;
    1.61 +
    1.62 +  GridUGraph ugraph(width, height);
    1.63 +  GridUGraph::Node start = ugraph(start_x - 1, start_y - 1);
    1.64 +  GridUGraph::Node stop = ugraph(stop_x - 1, stop_y - 1);
    1.65 +  GridUGraph::NodeMap<bool> filter(ugraph);
    1.66 +
    1.67 +  for (int j = 0; j < height; ++j) {
    1.68 +    in >> ws;
    1.69 +    for (int i = 0; i < width; ++i) {
    1.70 +      char c; in >> c;
    1.71 +      filter[ugraph(i, j)] = (c == '.');
    1.72 +    }
    1.73 +  }
    1.74 +
    1.75 +  typedef NodeSubGraphAdaptor<GridUGraph,
    1.76 +    GridUGraph::NodeMap<bool> > FilteredGraph;
    1.77 +
    1.78 +  FilteredGraph filtered(ugraph, filter);
    1.79 +
    1.80 +  Bfs<FilteredGraph> bfs(filtered);
    1.81 +  std::cout << "The length of shortest path: " << 
    1.82 +    bfs.run(start, stop) << std::endl;
    1.83 +
    1.84 +  FilteredGraph::EdgeMap<bool> path(filtered, false);
    1.85 +  
    1.86 +  for (GridUGraph::Node node = stop; 
    1.87 +       node != start; node = bfs.predNode(node)) {
    1.88 +    path[bfs.predEdge(node)] = true;
    1.89 +  }
    1.90 +  
    1.91 +  graphToEps(filtered, "grid_ugraph_demo.eps").scaleToA4().
    1.92 +    title("Grid ugraph").
    1.93 +    copyright("(C) 2006 LEMON Project").
    1.94 +    coords(scaleMap(indexMap(ugraph), 10)).
    1.95 +    enableParallel().
    1.96 +    nodeScale(0.5).
    1.97 +    drawArrows().
    1.98 +    edgeColors(composeMap(ColorSet(), path)).
    1.99 +    run();
   1.100 +  
   1.101 +  std::cout << "The shortest path is written to grid_ugraph_demo.eps" 
   1.102 +	    << std::endl;
   1.103 +
   1.104 +  return 0;
   1.105 +}