COIN-OR::LEMON - Graph Library

source: lemon-0.x/demo/grid_ugraph_demo.cc @ 2067:cd414bfbe38b

Last change on this file since 2067:cd414bfbe38b was 1979:c2992fd74dad, checked in by Balazs Dezso, 18 years ago

Mergeing extendermerge branch
Changes:

the extender system
resize for static size graph
UGraphExtender => UndirectGraphExtender?

UGraphExtenders with changed meaning

Some UGraphExtender /SubUGraphExtenders, DirectUGraphExtender/
GridGraph? => GridUGraph
radix sort to ansi compatible

File size: 2.5 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
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/xy.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
47using namespace lemon;
48using namespace std;
49
50int 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) 2006 LEMON Project").
91    coords(scaleMap(indexMap(ugraph), 10)).
92    enableParallel().
93    nodeScale(0.5).
94    drawArrows().
95    edgeColors(composeMap(ColorSet(), 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}
Note: See TracBrowser for help on using the repository browser.