COIN-OR::LEMON - Graph Library

Changeset 1681:84e43c7ca1e3 in lemon-0.x for lemon/graph_adaptor.h


Ignore:
Timestamp:
09/12/05 13:24:54 (14 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

File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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.