COIN-OR::LEMON - Graph Library

Changeset 1681:84e43c7ca1e3 in lemon-0.x


Ignore:
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

Files:
1 added
2 edited

Legend:

Unmodified
Added
Removed
  • demo/grid_graph_demo.cc

    r1680 r1681  
    22#include <lemon/graph_adaptor.h>
    33#include <lemon/graph_to_eps.h>
     4#include <lemon/bfs.h>
    45#include <lemon/xy.h>
    56
     
    1112
    1213int main() {
    13   GridGraph graph(5, 7);
     14  ifstream in("grid_graph_demo.in");
     15  int width, height;
     16  in >> width >> height;
     17  int start_x, start_y;
     18  in >> start_x >> start_y;
     19  int stop_x, stop_y;
     20  in >> stop_x >> stop_y;
     21
     22  GridGraph graph(width, height);
     23  GridGraph::Node start = graph(start_x - 1, start_y - 1);
     24  GridGraph::Node stop = graph(stop_x - 1, stop_y - 1);
     25  GridGraph::NodeMap<bool> filter(graph);
     26
     27  for (int j = 0; j < height; ++j) {
     28    in >> ws;
     29    for (int i = 0; i < width; ++i) {
     30      char c; in >> c;
     31      filter[graph(i, j)] = (c == '.');
     32    }
     33  }
     34
     35  typedef NodeSubGraphAdaptor<GridGraph,
     36    GridGraph::NodeMap<bool> > FilteredGraph;
     37
     38  FilteredGraph filtered(graph, filter);
     39
     40  Bfs<FilteredGraph> bfs(filtered);
     41  std::cout << "The length of shortest path: " <<
     42    bfs.run(start, stop) << std::endl;
     43
    1444  GridGraph::NodeMap<xy<double> > coord(graph);
    1545  for (int i = 0; i < graph.width(); ++i) {
    1646    for (int j = 0; j < graph.height(); ++j) {
    17       coord[graph(i, j)] = xy<double>(i * 10.0, j * 10.0);
     47      coord[graph(i, j)] = xy<double>( i * 10.0, j * 10.0);
    1848    }
    1949  }
    20   graphToEps(graph, "grid_graph.eps").scaleToA4().
     50 
     51  FilteredGraph::EdgeMap<Color> color(filtered, Color(0.0, 0.0, 0.0));
     52 
     53  for (GridGraph::Node node = stop;
     54       node != start; node = bfs.predNode(node)) {
     55    color[bfs.pred(node)] = Color(1.0, 0.0, 0.0);
     56  }
     57 
     58  graphToEps(filtered, "grid_graph.eps").scaleToA4().
    2159    title("Grid graph").
    2260    copyright("(C) 2005 LEMON Project").
     
    2563    nodeScale(.45).
    2664    drawArrows().
     65    edgeColors(color).
    2766    run();
     67 
     68  std::cout << "The shortest path is written to grid_graph.eps" << std::endl;
     69
    2870  return 0;
    2971}
  • lemon/graph_adaptor.h

    r1669 r1681  
    207207
    208208 
    209   template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
     209  template <typename _Graph, typename NodeFilterMap,
     210            typename EdgeFilterMap, bool checked = true>
    210211  class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
    211212  public:
     
    226227
    227228  public:
    228 //     SubGraphAdaptorBase(Graph& _graph,
    229 //                      NodeFilterMap& _node_filter_map,
    230 //                      EdgeFilterMap& _edge_filter_map) :
    231 //       Parent(&_graph),
    232 //       node_filter_map(&node_filter_map),
    233 //       edge_filter_map(&edge_filter_map) { }
    234229
    235230    typedef typename Parent::Node Node;
     
    240235      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
    241236    }
     237
    242238    void first(Edge& i) const {
    243239      Parent::first(i);
    244       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
    245     }
     240      while (i!=INVALID && (!(*edge_filter_map)[i]
     241             || !(*node_filter_map)[Parent::source(i)]
     242             || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
     243    }
     244
    246245    void firstIn(Edge& i, const Node& n) const {
    247246      Parent::firstIn(i, n);
    248       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
    249     }
     247      while (i!=INVALID && (!(*edge_filter_map)[i]
     248             || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
     249    }
     250
    250251    void firstOut(Edge& i, const Node& n) const {
    251252      Parent::firstOut(i, n);
    252       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
     253      while (i!=INVALID && (!(*edge_filter_map)[i]
     254             || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
    253255    }
    254256
     
    257259      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
    258260    }
     261
    259262    void next(Edge& i) const {
    260263      Parent::next(i);
    261       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
    262     }
     264      while (i!=INVALID && (!(*edge_filter_map)[i]
     265             || !(*node_filter_map)[Parent::source(i)]
     266             || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
     267    }
     268
    263269    void nextIn(Edge& i) const {
    264270      Parent::nextIn(i);
    265       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
    266     }
     271      while (i!=INVALID && (!(*edge_filter_map)[i]
     272             || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
     273    }
     274
    267275    void nextOut(Edge& i) const {
    268276      Parent::nextOut(i);
    269       while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
     277      while (i!=INVALID && (!(*edge_filter_map)[i]
     278             || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
    270279    }
    271280
     
    315324      return i;
    316325    }
    317 
    318 
     326  };
     327
     328  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
     329  class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
     330    : public GraphAdaptorBase<_Graph> {
     331  public:
     332    typedef _Graph Graph;
     333    typedef GraphAdaptorBase<_Graph> Parent;
     334  protected:
     335    NodeFilterMap* node_filter_map;
     336    EdgeFilterMap* edge_filter_map;
     337    SubGraphAdaptorBase() : Parent(),
     338                            node_filter_map(0), edge_filter_map(0) { }
     339
     340    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
     341      node_filter_map=&_node_filter_map;
     342    }
     343    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
     344      edge_filter_map=&_edge_filter_map;
     345    }
     346
     347  public:
     348
     349    typedef typename Parent::Node Node;
     350    typedef typename Parent::Edge Edge;
     351
     352    void first(Node& i) const {
     353      Parent::first(i);
     354      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
     355    }
     356
     357    void first(Edge& i) const {
     358      Parent::first(i);
     359      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
     360    }
     361
     362    void firstIn(Edge& i, const Node& n) const {
     363      Parent::firstIn(i, n);
     364      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
     365    }
     366
     367    void firstOut(Edge& i, const Node& n) const {
     368      Parent::firstOut(i, n);
     369      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
     370    }
     371
     372    void next(Node& i) const {
     373      Parent::next(i);
     374      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
     375    }
     376    void next(Edge& i) const {
     377      Parent::next(i);
     378      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
     379    }
     380    void nextIn(Edge& i) const {
     381      Parent::nextIn(i);
     382      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
     383    }
     384
     385    void nextOut(Edge& i) const {
     386      Parent::nextOut(i);
     387      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
     388    }
     389
     390    /// This function hides \c n in the graph, i.e. the iteration
     391    /// jumps over it. This is done by simply setting the value of \c n 
     392    /// to be false in the corresponding node-map.
     393    void hide(const Node& n) const { node_filter_map->set(n, false); }
     394
     395    /// This function hides \c e in the graph, i.e. the iteration
     396    /// jumps over it. This is done by simply setting the value of \c e 
     397    /// to be false in the corresponding edge-map.
     398    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
     399
     400    /// The value of \c n is set to be true in the node-map which stores
     401    /// hide information. If \c n was hidden previuosly, then it is shown
     402    /// again
     403     void unHide(const Node& n) const { node_filter_map->set(n, true); }
     404
     405    /// The value of \c e is set to be true in the edge-map which stores
     406    /// hide information. If \c e was hidden previuosly, then it is shown
     407    /// again
     408    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
     409
     410    /// Returns true if \c n is hidden.
     411    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
     412
     413    /// Returns true if \c n is hidden.
     414    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
     415
     416    /// \warning This is a linear time operation and works only if s
     417    /// \c Graph::NodeIt is defined.
     418    /// \todo assign tags.
     419    int nodeNum() const {
     420      int i=0;
     421      Node n;
     422      for (first(n); n!=INVALID; next(n)) ++i;
     423      return i;
     424    }
     425
     426    /// \warning This is a linear time operation and works only if
     427    /// \c Graph::EdgeIt is defined.
     428    /// \todo assign tags.
     429    int edgeNum() const {
     430      int i=0;
     431      Edge e;
     432      for (first(e); e!=INVALID; next(e)) ++i;
     433      return i;
     434    }
    319435  };
    320436
     
    376492  */
    377493  template<typename _Graph, typename NodeFilterMap,
    378            typename EdgeFilterMap>
     494           typename EdgeFilterMap, bool checked = true>
    379495  class SubGraphAdaptor :
    380496    public IterableGraphExtender<
    381     SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
     497    SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
    382498  public:
    383499    typedef _Graph Graph;
     
    408524  \author Marton Makai
    409525  */
    410   template<typename Graph, typename NodeFilterMap>
     526  template<typename Graph, typename NodeFilterMap, bool checked = true>
    411527  class NodeSubGraphAdaptor :
    412528    public SubGraphAdaptor<Graph, NodeFilterMap,
    413                            ConstMap<typename Graph::Edge,bool> > {
     529                           ConstMap<typename Graph::Edge,bool>, checked> {
    414530  public:
    415531    typedef SubGraphAdaptor<Graph, NodeFilterMap,
     
    561677  class EdgeSubGraphAdaptor :
    562678    public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
    563                            EdgeFilterMap> {
     679                           EdgeFilterMap, false> {
    564680  public:
    565681    typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
Note: See TracChangeset for help on using the changeset viewer.