# HG changeset patch
# User deba
# Date 1126524294 0
# Node ID 84e43c7ca1e3bb3922ee8cdb1943b75f6a9cf6b1
# Parent  4f8b9cee576b82fe00913d8ba64c6e2b081ca06e
SubGraphAdaptors with edge checking functionality.

Improved grid_graph_demo

diff -r 4f8b9cee576b -r 84e43c7ca1e3 demo/grid_graph_demo.cc
--- a/demo/grid_graph_demo.cc	Mon Sep 12 09:19:52 2005 +0000
+++ b/demo/grid_graph_demo.cc	Mon Sep 12 11:24:54 2005 +0000
@@ -1,6 +1,7 @@
 #include <lemon/grid_graph.h>
 #include <lemon/graph_adaptor.h>
 #include <lemon/graph_to_eps.h>
+#include <lemon/bfs.h>
 #include <lemon/xy.h>
 
 #include <iostream>
@@ -10,20 +11,61 @@
 using namespace std;
 
 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").
     coords(coord).
     enableParallel().
     nodeScale(.45).
     drawArrows().
+    edgeColors(color).
     run();
+  
+  std::cout << "The shortest path is written to grid_graph.eps" << std::endl;
+
   return 0;
 }
diff -r 4f8b9cee576b -r 84e43c7ca1e3 demo/grid_graph_demo.in
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/demo/grid_graph_demo.in	Mon Sep 12 11:24:54 2005 +0000
@@ -0,0 +1,10 @@
+10 8
+1 1 10 8
+..X....X.X
+.XX.X.XX..
+....X..XX.
+XXXXXX.X..
+.........X
+.X.XXXXXXX
+.X...XX...
+.X.X....X.
diff -r 4f8b9cee576b -r 84e43c7ca1e3 lemon/graph_adaptor.h
--- a/lemon/graph_adaptor.h	Mon Sep 12 09:19:52 2005 +0000
+++ b/lemon/graph_adaptor.h	Mon Sep 12 11:24:54 2005 +0000
@@ -206,7 +206,8 @@
   };
 
   
-  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
+  template <typename _Graph, typename NodeFilterMap, 
+	    typename EdgeFilterMap, bool checked = true>
   class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
   public:
     typedef _Graph Graph;
@@ -225,12 +226,6 @@
     }
 
   public:
-//     SubGraphAdaptorBase(Graph& _graph, 
-// 			NodeFilterMap& _node_filter_map, 
-// 			EdgeFilterMap& _edge_filter_map) : 
-//       Parent(&_graph), 
-//       node_filter_map(&node_filter_map), 
-//       edge_filter_map(&edge_filter_map) { }
 
     typedef typename Parent::Node Node;
     typedef typename Parent::Edge Edge;
@@ -239,14 +234,136 @@
       Parent::first(i); 
       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
     }
+
+    void first(Edge& i) const { 
+      Parent::first(i); 
+      while (i!=INVALID && (!(*edge_filter_map)[i] 
+	     || !(*node_filter_map)[Parent::source(i)]
+	     || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 
+    }
+
+    void firstIn(Edge& i, const Node& n) const { 
+      Parent::firstIn(i, n); 
+      while (i!=INVALID && (!(*edge_filter_map)[i] 
+	     || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i); 
+    }
+
+    void firstOut(Edge& i, const Node& n) const { 
+      Parent::firstOut(i, n); 
+      while (i!=INVALID && (!(*edge_filter_map)[i] 
+	     || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i); 
+    }
+
+    void next(Node& i) const { 
+      Parent::next(i); 
+      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
+    }
+
+    void next(Edge& i) const { 
+      Parent::next(i); 
+      while (i!=INVALID && (!(*edge_filter_map)[i] 
+	     || !(*node_filter_map)[Parent::source(i)]
+	     || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 
+    }
+
+    void nextIn(Edge& i) const { 
+      Parent::nextIn(i); 
+      while (i!=INVALID && (!(*edge_filter_map)[i] 
+	     || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i); 
+    }
+
+    void nextOut(Edge& i) const { 
+      Parent::nextOut(i); 
+      while (i!=INVALID && (!(*edge_filter_map)[i] 
+	     || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i); 
+    }
+
+    /// This function hides \c n in the graph, i.e. the iteration 
+    /// jumps over it. This is done by simply setting the value of \c n  
+    /// to be false in the corresponding node-map.
+    void hide(const Node& n) const { node_filter_map->set(n, false); }
+
+    /// This function hides \c e in the graph, i.e. the iteration 
+    /// jumps over it. This is done by simply setting the value of \c e  
+    /// to be false in the corresponding edge-map.
+    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
+
+    /// The value of \c n is set to be true in the node-map which stores 
+    /// hide information. If \c n was hidden previuosly, then it is shown 
+    /// again
+     void unHide(const Node& n) const { node_filter_map->set(n, true); }
+
+    /// The value of \c e is set to be true in the edge-map which stores 
+    /// hide information. If \c e was hidden previuosly, then it is shown 
+    /// again
+    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
+
+    /// Returns true if \c n is hidden.
+    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
+
+    /// Returns true if \c n is hidden.
+    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
+
+    /// \warning This is a linear time operation and works only if s
+    /// \c Graph::NodeIt is defined.
+    /// \todo assign tags.
+    int nodeNum() const { 
+      int i=0;
+      Node n;
+      for (first(n); n!=INVALID; next(n)) ++i;
+      return i; 
+    }
+
+    /// \warning This is a linear time operation and works only if 
+    /// \c Graph::EdgeIt is defined.
+    /// \todo assign tags.
+    int edgeNum() const { 
+      int i=0;
+      Edge e;
+      for (first(e); e!=INVALID; next(e)) ++i;
+      return i; 
+    }
+  };
+
+  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
+  class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false> 
+    : public GraphAdaptorBase<_Graph> {
+  public:
+    typedef _Graph Graph;
+    typedef GraphAdaptorBase<_Graph> Parent;
+  protected:
+    NodeFilterMap* node_filter_map;
+    EdgeFilterMap* edge_filter_map;
+    SubGraphAdaptorBase() : Parent(), 
+			    node_filter_map(0), edge_filter_map(0) { }
+
+    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
+      node_filter_map=&_node_filter_map;
+    }
+    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
+      edge_filter_map=&_edge_filter_map;
+    }
+
+  public:
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge Edge;
+
+    void first(Node& i) const { 
+      Parent::first(i); 
+      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
+    }
+
     void first(Edge& i) const { 
       Parent::first(i); 
       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 
     }
+
     void firstIn(Edge& i, const Node& n) const { 
       Parent::firstIn(i, n); 
       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 
     }
+
     void firstOut(Edge& i, const Node& n) const { 
       Parent::firstOut(i, n); 
       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 
@@ -264,6 +381,7 @@
       Parent::nextIn(i); 
       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 
     }
+
     void nextOut(Edge& i) const { 
       Parent::nextOut(i); 
       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 
@@ -314,8 +432,6 @@
       for (first(e); e!=INVALID; next(e)) ++i;
       return i; 
     }
-
-
   };
 
   /*! \brief A graph adaptor for hiding nodes and edges from a graph.
@@ -375,10 +491,10 @@
   \author Marton Makai
   */
   template<typename _Graph, typename NodeFilterMap, 
-	   typename EdgeFilterMap>
+	   typename EdgeFilterMap, bool checked = true>
   class SubGraphAdaptor : 
     public IterableGraphExtender<
-    SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
+    SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
   public:
     typedef _Graph Graph;
     typedef IterableGraphExtender<
@@ -407,10 +523,10 @@
   subgraph, the edge-iterators consider the original edge-set.
   \author Marton Makai
   */
-  template<typename Graph, typename NodeFilterMap>
+  template<typename Graph, typename NodeFilterMap, bool checked = true>
   class NodeSubGraphAdaptor : 
     public SubGraphAdaptor<Graph, NodeFilterMap, 
-			   ConstMap<typename Graph::Edge,bool> > {
+			   ConstMap<typename Graph::Edge,bool>, checked> {
   public:
     typedef SubGraphAdaptor<Graph, NodeFilterMap, 
 			    ConstMap<typename Graph::Edge,bool> > Parent;
@@ -560,7 +676,7 @@
   template<typename Graph, typename EdgeFilterMap>
   class EdgeSubGraphAdaptor : 
     public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>, 
-			   EdgeFilterMap> {
+			   EdgeFilterMap, false> {
   public:
     typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>, 
 			    EdgeFilterMap> Parent;