demo/grid_ugraph_demo.cc
author kpeter
Tue, 05 Feb 2008 11:03:55 +0000
changeset 2560 635e7985be46
parent 2391 14a343be7a5a
permissions -rw-r--r--
Fix the rename script.
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #include <lemon/grid_ugraph.h>
    20 #include <lemon/graph_adaptor.h>
    21 #include <lemon/graph_to_eps.h>
    22 #include <lemon/bfs.h>
    23 #include <lemon/dim2.h>
    24 
    25 #include <iostream>
    26 #include <fstream>
    27 
    28 ///\ingroup demos
    29 ///\file
    30 ///\brief Labirinth example with grid ugraph.
    31 ///
    32 ///  Labirinth example with grid ugraph.
    33 ///
    34 /// The input file is:
    35 ///
    36 /// \include grid_ugraph_demo.in
    37 ///
    38 /// The result:
    39 ///
    40 /// \image html grid_ugraph_demo.png
    41 /// \image latex grid_ugraph_demo.eps "The labirinth" width=\textwidth
    42 ///
    43 /// The source:
    44 ///
    45 /// \include grid_ugraph_demo.cc
    46 
    47 using namespace lemon;
    48 using namespace std;
    49 
    50 int main() {
    51   ifstream in("grid_ugraph_demo.in");
    52   int width, height;
    53   in >> width >> height;
    54   int start_x, start_y;
    55   in >> start_x >> start_y;
    56   int stop_x, stop_y;
    57   in >> stop_x >> stop_y;
    58 
    59   GridUGraph ugraph(width, height);
    60   GridUGraph::Node start = ugraph(start_x - 1, start_y - 1);
    61   GridUGraph::Node stop = ugraph(stop_x - 1, stop_y - 1);
    62   GridUGraph::NodeMap<bool> filter(ugraph);
    63 
    64   for (int j = 0; j < height; ++j) {
    65     in >> ws;
    66     for (int i = 0; i < width; ++i) {
    67       char c; in >> c;
    68       filter[ugraph(i, j)] = (c == '.');
    69     }
    70   }
    71 
    72   typedef NodeSubGraphAdaptor<GridUGraph,
    73     GridUGraph::NodeMap<bool> > FilteredGraph;
    74 
    75   FilteredGraph filtered(ugraph, filter);
    76 
    77   Bfs<FilteredGraph> bfs(filtered);
    78   std::cout << "The length of shortest path: " << 
    79     bfs.run(start, stop) << std::endl;
    80 
    81   FilteredGraph::EdgeMap<bool> path(filtered, false);
    82   
    83   for (GridUGraph::Node node = stop; 
    84        node != start; node = bfs.predNode(node)) {
    85     path[bfs.predEdge(node)] = true;
    86   }
    87   
    88   graphToEps(filtered, "grid_ugraph_demo.eps").scaleToA4().
    89     title("Grid ugraph").
    90     copyright("(C) 2003-2007 LEMON Project").
    91     coords(scaleMap(indexMap(ugraph), 10)).
    92     enableParallel().
    93     nodeScale(0.5).
    94     drawArrows().
    95     edgeColors(composeMap(Palette(), path)).
    96     run();
    97   
    98   std::cout << "The shortest path is written to grid_ugraph_demo.eps" 
    99 	    << std::endl;
   100 
   101   return 0;
   102 }