1.1 --- a/demo/grid_graph_demo.cc	Mon Sep 12 09:19:52 2005 +0000
     1.2 +++ b/demo/grid_graph_demo.cc	Mon Sep 12 11:24:54 2005 +0000
     1.3 @@ -1,6 +1,7 @@
     1.4  #include <lemon/grid_graph.h>
     1.5  #include <lemon/graph_adaptor.h>
     1.6  #include <lemon/graph_to_eps.h>
     1.7 +#include <lemon/bfs.h>
     1.8  #include <lemon/xy.h>
     1.9  
    1.10  #include <iostream>
    1.11 @@ -10,20 +11,61 @@
    1.12  using namespace std;
    1.13  
    1.14  int main() {
    1.15 -  GridGraph graph(5, 7);
    1.16 +  ifstream in("grid_graph_demo.in");
    1.17 +  int width, height;
    1.18 +  in >> width >> height;
    1.19 +  int start_x, start_y;
    1.20 +  in >> start_x >> start_y;
    1.21 +  int stop_x, stop_y;
    1.22 +  in >> stop_x >> stop_y;
    1.23 +
    1.24 +  GridGraph graph(width, height);
    1.25 +  GridGraph::Node start = graph(start_x - 1, start_y - 1);
    1.26 +  GridGraph::Node stop = graph(stop_x - 1, stop_y - 1);
    1.27 +  GridGraph::NodeMap<bool> filter(graph);
    1.28 +
    1.29 +  for (int j = 0; j < height; ++j) {
    1.30 +    in >> ws;
    1.31 +    for (int i = 0; i < width; ++i) {
    1.32 +      char c; in >> c;
    1.33 +      filter[graph(i, j)] = (c == '.');
    1.34 +    }
    1.35 +  }
    1.36 +
    1.37 +  typedef NodeSubGraphAdaptor<GridGraph,
    1.38 +    GridGraph::NodeMap<bool> > FilteredGraph;
    1.39 +
    1.40 +  FilteredGraph filtered(graph, filter);
    1.41 +
    1.42 +  Bfs<FilteredGraph> bfs(filtered);
    1.43 +  std::cout << "The length of shortest path: " << 
    1.44 +    bfs.run(start, stop) << std::endl;
    1.45 +
    1.46    GridGraph::NodeMap<xy<double> > coord(graph);
    1.47    for (int i = 0; i < graph.width(); ++i) {
    1.48      for (int j = 0; j < graph.height(); ++j) {
    1.49 -      coord[graph(i, j)] = xy<double>(i * 10.0, j * 10.0);
    1.50 +      coord[graph(i, j)] = xy<double>( i * 10.0, j * 10.0);
    1.51      }
    1.52    }
    1.53 -  graphToEps(graph, "grid_graph.eps").scaleToA4().
    1.54 +  
    1.55 +  FilteredGraph::EdgeMap<Color> color(filtered, Color(0.0, 0.0, 0.0));
    1.56 +  
    1.57 +  for (GridGraph::Node node = stop; 
    1.58 +       node != start; node = bfs.predNode(node)) {
    1.59 +    color[bfs.pred(node)] = Color(1.0, 0.0, 0.0);
    1.60 +  }
    1.61 +  
    1.62 +  graphToEps(filtered, "grid_graph.eps").scaleToA4().
    1.63      title("Grid graph").
    1.64      copyright("(C) 2005 LEMON Project").
    1.65      coords(coord).
    1.66      enableParallel().
    1.67      nodeScale(.45).
    1.68      drawArrows().
    1.69 +    edgeColors(color).
    1.70      run();
    1.71 +  
    1.72 +  std::cout << "The shortest path is written to grid_graph.eps" << std::endl;
    1.73 +
    1.74    return 0;
    1.75  }

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/demo/grid_graph_demo.in	Mon Sep 12 11:24:54 2005 +0000
     2.3 @@ -0,0 +1,10 @@
     2.4 +10 8
     2.5 +1 1 10 8
     2.6 +..X....X.X
     2.7 +.XX.X.XX..
     2.8 +....X..XX.
     2.9 +XXXXXX.X..
    2.10 +.........X
    2.11 +.X.XXXXXXX
    2.12 +.X...XX...
    2.13 +.X.X....X.

     3.1 --- a/lemon/graph_adaptor.h	Mon Sep 12 09:19:52 2005 +0000
     3.2 +++ b/lemon/graph_adaptor.h	Mon Sep 12 11:24:54 2005 +0000
     3.3 @@ -206,7 +206,8 @@
     3.4    };
     3.5  
     3.6    
     3.7 -  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
     3.8 +  template <typename _Graph, typename NodeFilterMap, 
     3.9 +	    typename EdgeFilterMap, bool checked = true>
    3.10    class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
    3.11    public:
    3.12      typedef _Graph Graph;
    3.13 @@ -225,12 +226,6 @@
    3.14      }
    3.15  
    3.16    public:
    3.17 -//     SubGraphAdaptorBase(Graph& _graph, 
    3.18 -// 			NodeFilterMap& _node_filter_map, 
    3.19 -// 			EdgeFilterMap& _edge_filter_map) : 
    3.20 -//       Parent(&_graph), 
    3.21 -//       node_filter_map(&node_filter_map), 
    3.22 -//       edge_filter_map(&edge_filter_map) { }
    3.23  
    3.24      typedef typename Parent::Node Node;
    3.25      typedef typename Parent::Edge Edge;
    3.26 @@ -239,14 +234,136 @@
    3.27        Parent::first(i); 
    3.28        while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
    3.29      }
    3.30 +
    3.31 +    void first(Edge& i) const { 
    3.32 +      Parent::first(i); 
    3.33 +      while (i!=INVALID && (!(*edge_filter_map)[i] 
    3.34 +	     || !(*node_filter_map)[Parent::source(i)]
    3.35 +	     || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 
    3.36 +    }
    3.37 +
    3.38 +    void firstIn(Edge& i, const Node& n) const { 
    3.39 +      Parent::firstIn(i, n); 
    3.40 +      while (i!=INVALID && (!(*edge_filter_map)[i] 
    3.41 +	     || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i); 
    3.42 +    }
    3.43 +
    3.44 +    void firstOut(Edge& i, const Node& n) const { 
    3.45 +      Parent::firstOut(i, n); 
    3.46 +      while (i!=INVALID && (!(*edge_filter_map)[i] 
    3.47 +	     || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i); 
    3.48 +    }
    3.49 +
    3.50 +    void next(Node& i) const { 
    3.51 +      Parent::next(i); 
    3.52 +      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
    3.53 +    }
    3.54 +
    3.55 +    void next(Edge& i) const { 
    3.56 +      Parent::next(i); 
    3.57 +      while (i!=INVALID && (!(*edge_filter_map)[i] 
    3.58 +	     || !(*node_filter_map)[Parent::source(i)]
    3.59 +	     || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 
    3.60 +    }
    3.61 +
    3.62 +    void nextIn(Edge& i) const { 
    3.63 +      Parent::nextIn(i); 
    3.64 +      while (i!=INVALID && (!(*edge_filter_map)[i] 
    3.65 +	     || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i); 
    3.66 +    }
    3.67 +
    3.68 +    void nextOut(Edge& i) const { 
    3.69 +      Parent::nextOut(i); 
    3.70 +      while (i!=INVALID && (!(*edge_filter_map)[i] 
    3.71 +	     || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i); 
    3.72 +    }
    3.73 +
    3.74 +    /// This function hides \c n in the graph, i.e. the iteration 
    3.75 +    /// jumps over it. This is done by simply setting the value of \c n  
    3.76 +    /// to be false in the corresponding node-map.
    3.77 +    void hide(const Node& n) const { node_filter_map->set(n, false); }
    3.78 +
    3.79 +    /// This function hides \c e in the graph, i.e. the iteration 
    3.80 +    /// jumps over it. This is done by simply setting the value of \c e  
    3.81 +    /// to be false in the corresponding edge-map.
    3.82 +    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
    3.83 +
    3.84 +    /// The value of \c n is set to be true in the node-map which stores 
    3.85 +    /// hide information. If \c n was hidden previuosly, then it is shown 
    3.86 +    /// again
    3.87 +     void unHide(const Node& n) const { node_filter_map->set(n, true); }
    3.88 +
    3.89 +    /// The value of \c e is set to be true in the edge-map which stores 
    3.90 +    /// hide information. If \c e was hidden previuosly, then it is shown 
    3.91 +    /// again
    3.92 +    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
    3.93 +
    3.94 +    /// Returns true if \c n is hidden.
    3.95 +    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
    3.96 +
    3.97 +    /// Returns true if \c n is hidden.
    3.98 +    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
    3.99 +
   3.100 +    /// \warning This is a linear time operation and works only if s
   3.101 +    /// \c Graph::NodeIt is defined.
   3.102 +    /// \todo assign tags.
   3.103 +    int nodeNum() const { 
   3.104 +      int i=0;
   3.105 +      Node n;
   3.106 +      for (first(n); n!=INVALID; next(n)) ++i;
   3.107 +      return i; 
   3.108 +    }
   3.109 +
   3.110 +    /// \warning This is a linear time operation and works only if 
   3.111 +    /// \c Graph::EdgeIt is defined.
   3.112 +    /// \todo assign tags.
   3.113 +    int edgeNum() const { 
   3.114 +      int i=0;
   3.115 +      Edge e;
   3.116 +      for (first(e); e!=INVALID; next(e)) ++i;
   3.117 +      return i; 
   3.118 +    }
   3.119 +  };
   3.120 +
   3.121 +  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
   3.122 +  class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false> 
   3.123 +    : public GraphAdaptorBase<_Graph> {
   3.124 +  public:
   3.125 +    typedef _Graph Graph;
   3.126 +    typedef GraphAdaptorBase<_Graph> Parent;
   3.127 +  protected:
   3.128 +    NodeFilterMap* node_filter_map;
   3.129 +    EdgeFilterMap* edge_filter_map;
   3.130 +    SubGraphAdaptorBase() : Parent(), 
   3.131 +			    node_filter_map(0), edge_filter_map(0) { }
   3.132 +
   3.133 +    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
   3.134 +      node_filter_map=&_node_filter_map;
   3.135 +    }
   3.136 +    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
   3.137 +      edge_filter_map=&_edge_filter_map;
   3.138 +    }
   3.139 +
   3.140 +  public:
   3.141 +
   3.142 +    typedef typename Parent::Node Node;
   3.143 +    typedef typename Parent::Edge Edge;
   3.144 +
   3.145 +    void first(Node& i) const { 
   3.146 +      Parent::first(i); 
   3.147 +      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
   3.148 +    }
   3.149 +
   3.150      void first(Edge& i) const { 
   3.151        Parent::first(i); 
   3.152        while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 
   3.153      }
   3.154 +
   3.155      void firstIn(Edge& i, const Node& n) const { 
   3.156        Parent::firstIn(i, n); 
   3.157        while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 
   3.158      }
   3.159 +
   3.160      void firstOut(Edge& i, const Node& n) const { 
   3.161        Parent::firstOut(i, n); 
   3.162        while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 
   3.163 @@ -264,6 +381,7 @@
   3.164        Parent::nextIn(i); 
   3.165        while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 
   3.166      }
   3.167 +
   3.168      void nextOut(Edge& i) const { 
   3.169        Parent::nextOut(i); 
   3.170        while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 
   3.171 @@ -314,8 +432,6 @@
   3.172        for (first(e); e!=INVALID; next(e)) ++i;
   3.173        return i; 
   3.174      }
   3.175 -
   3.176 -
   3.177    };
   3.178  
   3.179    /*! \brief A graph adaptor for hiding nodes and edges from a graph.
   3.180 @@ -375,10 +491,10 @@
   3.181    \author Marton Makai
   3.182    */
   3.183    template<typename _Graph, typename NodeFilterMap, 
   3.184 -	   typename EdgeFilterMap>
   3.185 +	   typename EdgeFilterMap, bool checked = true>
   3.186    class SubGraphAdaptor : 
   3.187      public IterableGraphExtender<
   3.188 -    SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
   3.189 +    SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
   3.190    public:
   3.191      typedef _Graph Graph;
   3.192      typedef IterableGraphExtender<
   3.193 @@ -407,10 +523,10 @@
   3.194    subgraph, the edge-iterators consider the original edge-set.
   3.195    \author Marton Makai
   3.196    */
   3.197 -  template<typename Graph, typename NodeFilterMap>
   3.198 +  template<typename Graph, typename NodeFilterMap, bool checked = true>
   3.199    class NodeSubGraphAdaptor : 
   3.200      public SubGraphAdaptor<Graph, NodeFilterMap, 
   3.201 -			   ConstMap<typename Graph::Edge,bool> > {
   3.202 +			   ConstMap<typename Graph::Edge,bool>, checked> {
   3.203    public:
   3.204      typedef SubGraphAdaptor<Graph, NodeFilterMap, 
   3.205  			    ConstMap<typename Graph::Edge,bool> > Parent;
   3.206 @@ -560,7 +676,7 @@
   3.207    template<typename Graph, typename EdgeFilterMap>
   3.208    class EdgeSubGraphAdaptor : 
   3.209      public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>, 
   3.210 -			   EdgeFilterMap> {
   3.211 +			   EdgeFilterMap, false> {
   3.212    public:
   3.213      typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>, 
   3.214  			    EdgeFilterMap> Parent;