Changeset 1681:84e43c7ca1e3 in lemon-0.x for demo

Timestamp:

09/12/05 13:24:54 (19 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2201

Message:

SubGraphAdaptors? with edge checking functionality.

Improved grid_graph_demo

Location:

demo

Files:

• grid_graph_demo.cc (modified) (3 diffs)
• grid_graph_demo.in (added)

demo/grid_graph_demo.cc

@@ -2 +2 @@
 #include <lemon/graph_adaptor.h>
 #include <lemon/graph_to_eps.h>
+#include <lemon/bfs.h>
 #include <lemon/xy.h>
 
@@ -11 +12 @@
 
 int main() {
-  GridGraph graph(5, 7);
+  ifstream in("grid_graph_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;
+
+  GridGraph graph(width, height);
+  GridGraph::Node start = graph(start_x - 1, start_y - 1);
+  GridGraph::Node stop = graph(stop_x - 1, stop_y - 1);
+  GridGraph::NodeMap<bool> filter(graph);
+
+  for (int j = 0; j < height; ++j) {
+    in >> ws;
+    for (int i = 0; i < width; ++i) {
+      char c; in >> c;
+      filter[graph(i, j)] = (c == '.');
+    }
+  }
+
+  typedef NodeSubGraphAdaptor<GridGraph,
+    GridGraph::NodeMap<bool> > FilteredGraph;
+
+  FilteredGraph filtered(graph, filter);
+
+  Bfs<FilteredGraph> bfs(filtered);
+  std::cout << "The length of shortest path: " << 
+    bfs.run(start, stop) << std::endl;
+
   GridGraph::NodeMap<xy<double> > coord(graph);
   for (int i = 0; i < graph.width(); ++i) {
     for (int j = 0; j < graph.height(); ++j) {
-      coord[graph(i, j)] = xy<double>(i * 10.0, j * 10.0);
+      coord[graph(i, j)] = xy<double>( i * 10.0, j * 10.0);
     }
   }
-  graphToEps(graph, "grid_graph.eps").scaleToA4().
+  
+  FilteredGraph::EdgeMap<Color> color(filtered, Color(0.0, 0.0, 0.0));
+  
+  for (GridGraph::Node node = stop; 
+       node != start; node = bfs.predNode(node)) {
+    color[bfs.pred(node)] = Color(1.0, 0.0, 0.0);
+  }
+  
+  graphToEps(filtered, "grid_graph.eps").scaleToA4().
     title("Grid graph").
     copyright("(C) 2005 LEMON Project").
@@ -25 +63 @@
     nodeScale(.45).
     drawArrows().
+    edgeColors(color).
     run();
+  
+  std::cout << "The shortest path is written to grid_graph.eps" << std::endl;
+
   return 0;
 }