COIN-OR::LEMON - Graph Library

Changeset 1991:d7442141d9ef in lemon-0.x for lemon/ugraph_adaptor.h


Ignore:
Timestamp:
03/01/06 11:25:30 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2593
Message:

The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor?, where
we have to proxy the signals from the graph.

The SubBidirGraphAdaptor? is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor?<UndirGraphAdaptor?<Graph>>.

The ResGraphAdaptor? is based on this composition.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/ugraph_adaptor.h

    r1985 r1991  
    4343  /// \brief Base type for the Graph Adaptors
    4444  ///
    45   /// \warning Graph adaptors are in even more experimental state than the
    46   /// other parts of the lib. Use them at you own risk.
    47   ///
    4845  /// This is the base type for most of LEMON graph adaptors.
    4946  /// This class implements a trivial graph adaptor i.e. it only wraps the
     
    9491    void nextInc(UEdge &i, bool &d) const { graph->nextInc(i, d); }
    9592
    96 
    9793    Node source(const UEdge& e) const { return graph->source(e); }
    9894    Node target(const UEdge& e) const { return graph->target(e); }
     
    112108      return graph->findEdge(source, target, prev);
    113109    }
    114 
    115110    UEdge findUEdge(const Node& source, const Node& target,
    116111                    const UEdge& prev = INVALID) {
     
    133128    bool direction(const Edge& e) const { return graph->direction(e); }
    134129    Edge direct(const UEdge& e, bool d) const { return graph->direct(e, d); }
    135     Edge direct(const UEdge& e, const Node& n) const {
    136       return graph->direct(e, n);
    137     }
    138 
    139     Node oppositeNode(const Node& n, const Edge& e) const {
    140       return graph->oppositeNode(n, e);
    141     }
    142 
    143     Edge oppositeEdge(const Edge& e) const {
    144       return graph->oppositeEdge(e);
    145     }
    146 
     130
     131    int maxNodeId() const {
     132      return graph->maxNodeId();
     133    }
     134
     135    int maxEdgeId() const {
     136      return graph->maxEdgeId();
     137    }
     138
     139    int maxUEdgeId() const {
     140      return graph->maxEdgeId();
     141    }
     142
     143    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
     144
     145    NodeNotifier& getNotifier(Node) const {
     146      return graph->getNotifier(Node());
     147    }
     148
     149    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
     150
     151    EdgeNotifier& getNotifier(Edge) const {
     152      return graph->getNotifier(Edge());
     153    }
     154
     155    typedef typename ItemSetTraits<Graph, UEdge>::ItemNotifier UEdgeNotifier;
     156
     157    UEdgeNotifier& getNotifier(UEdge) const {
     158      return graph->getNotifier(UEdge());
     159    }
    147160
    148161    template <typename _Value>
     
    380393    typedef False NodeNumTag;
    381394    typedef False EdgeNumTag;
     395
     396    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
     397    Edge findEdge(const Node& source, const Node& target,
     398                  const Edge& prev = INVALID) {
     399      if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
     400        return INVALID;
     401      }
     402      Edge edge = Parent::findEdge(source, target, prev);
     403      while (edge != INVALID && !(*uedge_filter_map)[edge]) {
     404        edge = Parent::findEdge(source, target, edge);
     405      }
     406      return edge;
     407    }
     408    UEdge findUEdge(const Node& source, const Node& target,
     409                  const UEdge& prev = INVALID) {
     410      if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
     411        return INVALID;
     412      }
     413      UEdge uedge = Parent::findUEdge(source, target, prev);
     414      while (uedge != INVALID && !(*uedge_filter_map)[uedge]) {
     415        uedge = Parent::findUEdge(source, target, uedge);
     416      }
     417      return uedge;
     418    }
    382419  };
    383420
     
    505542    typedef False NodeNumTag;
    506543    typedef False EdgeNumTag;
     544
     545    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
     546    Edge findEdge(const Node& source, const Node& target,
     547                  const Edge& prev = INVALID) {
     548      Edge edge = Parent::findEdge(source, target, prev);
     549      while (edge != INVALID && !(*uedge_filter_map)[edge]) {
     550        edge = Parent::findEdge(source, target, edge);
     551      }
     552      return edge;
     553    }
     554    UEdge findUEdge(const Node& source, const Node& target,
     555                  const UEdge& prev = INVALID) {
     556      UEdge uedge = Parent::findUEdge(source, target, prev);
     557      while (uedge != INVALID && !(*uedge_filter_map)[uedge]) {
     558        uedge = Parent::findUEdge(source, target, uedge);
     559      }
     560      return uedge;
     561    }
    507562  };
    508563
     
    582637  /// \brief An adaptor for hiding nodes from an undirected graph.
    583638  ///
    584   ///
    585639  /// An adaptor for hiding nodes from an undirected graph.
    586640  /// This adaptor specializes SubUGraphAdaptor in the way that only
     
    599653  protected:
    600654    ConstMap<typename _UGraph::UEdge, bool> const_true_map;
     655
     656    NodeSubUGraphAdaptor() : const_true_map(true) {
     657      Parent::setUEdgeFilterMap(const_true_map);
     658    }
     659
    601660  public:
    602661    NodeSubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
     
    640699  protected:
    641700    ConstMap<typename Graph::Node, bool> const_true_map;
     701
     702    EdgeSubUGraphAdaptor() : const_true_map(true) {
     703      Parent::setNodeFilterMap(const_true_map);
     704    }
     705
    642706  public:
    643707    EdgeSubUGraphAdaptor(Graph& _graph, UEdgeFilterMap& _uedge_filter_map) :
     
    671735    typedef typename _UGraph::UEdge Edge;
    672736   
     737    void reverseEdge(const Edge& edge) {
     738      direction->set(edge, !(*direction)[edge]);
     739    }
     740
    673741    void first(Node& i) const { graph->first(i); }
    674742    void first(Edge& i) const { graph->first(i); }
     
    747815    int id(const Edge& e) const { return graph->id(e); }
    748816
    749     void reverseEdge(const Edge& edge) {
    750       direction->set(edge, !(*direction)[edge]);
    751     }
     817    int maxNodeId() const {
     818      return graph->maxNodeId();
     819    }
     820
     821    int maxEdgeId() const {
     822      return graph->maxEdgeId();
     823    }
     824
     825    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
     826
     827    NodeNotifier& getNotifier(Node) const {
     828      return graph->getNotifier(Node());
     829    }
     830
     831    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
     832
     833    EdgeNotifier& getNotifier(Edge) const {
     834      return graph->getNotifier(Edge());
     835    }
    752836
    753837    template <typename _Value>
     
    789873
    790874  /// \ingroup graph_adaptors
    791   /// \brief A directed graph is made from a undirected graph by an adaptor
     875  ///
     876  /// \brief A directed graph is made from an undirected graph by an adaptor
    792877  ///
    793878  /// This adaptor gives a direction for each uedge in the undirected graph.
Note: See TracChangeset for help on using the changeset viewer.