COIN-OR::LEMON - Graph Library

Changeset 1991:d7442141d9ef in lemon-0.x for lemon


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.

Location:
lemon
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • lemon/bits/edge_set_extender.h

    r1979 r1991  
    6969  public:
    7070
     71    using Parent::getNotifier;
     72
    7173    /// \brief Gives back the edge alteration notifier.
    7274    ///
     
    323325
    324326  public:
     327
     328    using Parent::getNotifier;
    325329   
    326330    EdgeNotifier& getNotifier(Edge) const {
  • lemon/bits/graph_extender.h

    r1983 r1991  
    15691569
    15701570    template <typename _Value>
    1571     class NodeMapBase : public NodeNotifier::ObserverBase {
     1571    class NodeMapBase {
    15721572    public:
    15731573      typedef BpUGraphExtender Graph;
     
    15911591
    15921592      NodeMapBase(const Graph& _g)
    1593         : graph(&_g), bNodeMap(_g), aNodeMap(_g) {
    1594         NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
    1595       }
     1593        : aNodeMap(_g), bNodeMap(_g) {}
    15961594      NodeMapBase(const Graph& _g, const _Value& _v)
    1597         : graph(&_g), bNodeMap(_g, _v),
    1598           aNodeMap(_g, _v) {
    1599         NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
    1600       }
    1601 
    1602       virtual ~NodeMapBase() {     
    1603         if (NodeNotifier::ObserverBase::attached()) {
    1604           NodeNotifier::ObserverBase::detach();
    1605         }
    1606       }
    1607    
     1595        : aNodeMap(_g, _v), bNodeMap(_g, _v) {}
     1596
    16081597      ConstReference operator[](const Key& node) const {
    16091598        if (Parent::aNode(node)) {
     
    16301619      }
    16311620
    1632     protected:
    1633      
    1634       virtual void add(const Node&) {}
    1635       virtual void add(const std::vector<Node>&) {}
    1636       virtual void erase(const Node&) {}
    1637       virtual void erase(const std::vector<Node>&) {}
    1638       virtual void clear() {}
    1639       virtual void build() {}
    1640 
    1641       const Graph* getGraph() const { return graph; }
    1642      
     1621      const Graph* getGraph() const {
     1622        return aNodeMap.getGraph();
     1623      }
     1624
    16431625    private:
    1644       const Graph* graph;
     1626      ANodeMap<_Value> aNodeMap;
    16451627      BNodeMap<_Value> bNodeMap;
    1646       ANodeMap<_Value> aNodeMap;
    16471628    };
    16481629   
  • lemon/graph_adaptor.h

    r1989 r1991  
    114114    int id(const Node& v) const { return graph->id(v); }
    115115    int id(const Edge& e) const { return graph->id(e); }
     116
     117    int maxNodeId() const {
     118      return graph->maxNodeId();
     119    }
     120
     121    int maxEdgeId() const {
     122      return graph->maxEdgeId();
     123    }
     124
     125    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
     126
     127    NodeNotifier& getNotifier(Node) const {
     128      return graph->getNotifier(Node());
     129    }
     130
     131    typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
     132
     133    EdgeNotifier& getNotifier(Edge) const {
     134      return graph->getNotifier(Edge());
     135    }
    116136   
    117137    template <typename _Value>
     
    119139    public:
    120140      typedef typename _Graph::template NodeMap<_Value> Parent;
    121       explicit NodeMap(const GraphAdaptorBase<_Graph>& gw)
    122         : Parent(*gw.graph) { }
    123       NodeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
    124         : Parent(*gw.graph, value) { }
     141      explicit NodeMap(const GraphAdaptorBase<_Graph>& ga)
     142        : Parent(*ga.graph) { }
     143      NodeMap(const GraphAdaptorBase<_Graph>& ga, const _Value& value)
     144        : Parent(*ga.graph, value) { }
    125145    };
    126146
     
    129149    public:
    130150      typedef typename _Graph::template EdgeMap<_Value> Parent;
    131       explicit EdgeMap(const GraphAdaptorBase<_Graph>& gw)
    132         : Parent(*gw.graph) { }
    133       EdgeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
    134         : Parent(*gw.graph, value) { }
     151      explicit EdgeMap(const GraphAdaptorBase<_Graph>& ga)
     152        : Parent(*ga.graph) { }
     153      EdgeMap(const GraphAdaptorBase<_Graph>& ga, const _Value& value)
     154        : Parent(*ga.graph, value) { }
    135155    };
    136156
     
    150170  };
    151171
     172  /// \brief Just gives back a graph adaptor
     173  ///
     174  /// Just gives back a graph adaptor which
     175  /// should be provide original graph
     176  template<typename Graph>
     177  GraphAdaptor<const Graph>
     178  graphAdaptor(const Graph& graph) {
     179    return GraphAdaptor<const Graph>(graph);
     180  }
     181
     182
    152183  template <typename _Graph>
    153184  class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
     
    169200    Node source(const Edge& e) const { return Parent::target(e); }
    170201    Node target(const Edge& e) const { return Parent::source(e); }
     202
     203    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
     204    Edge findEdge(const Node& source, const Node& target,
     205                  const Edge& prev = INVALID) {
     206      return Parent::findEdge(target, source, prev);
     207    }
     208
    171209  };
    172210   
     
    185223  /// then
    186224  ///\code
    187   /// RevGraphAdaptor<ListGraph> gw(g);
     225  /// RevGraphAdaptor<ListGraph> ga(g);
    188226  ///\endcode
    189227  ///implements the graph obtained from \c g by
     
    203241  };
    204242
    205  
     243  /// \brief Just gives back a reverse graph adaptor
     244  ///
     245  /// Just gives back a reverse graph adaptor
     246  template<typename Graph>
     247  RevGraphAdaptor<const Graph>
     248  revGraphAdaptor(const Graph& graph) {
     249    return RevGraphAdaptor<const Graph>(graph);
     250  }
     251
    206252  template <typename _Graph, typename NodeFilterMap,
    207253            typename EdgeFilterMap, bool checked = true>
     
    316362    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
    317363
    318     typedef False FindEdgeTag;
    319364    typedef False NodeNumTag;
    320365    typedef False EdgeNumTag;
     366
     367    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
     368    Edge findEdge(const Node& source, const Node& target,
     369                  const Edge& prev = INVALID) {
     370      if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
     371        return INVALID;
     372      }
     373      Edge edge = Parent::findEdge(source, target, prev);
     374      while (edge != INVALID && !(*edge_filter_map)[edge]) {
     375        edge = Parent::findEdge(source, target, edge);
     376      }
     377      return edge;
     378    }
    321379  };
    322380
     
    423481    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
    424482
    425     typedef False FindEdgeTag;
    426483    typedef False NodeNumTag;
    427484    typedef False EdgeNumTag;
     485
     486    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
     487    Edge findEdge(const Node& source, const Node& target,
     488                  const Edge& prev = INVALID) {
     489      if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {
     490        return INVALID;
     491      }
     492      Edge edge = Parent::findEdge(source, target, prev);
     493      while (edge != INVALID && !(*edge_filter_map)[edge]) {
     494        edge = Parent::findEdge(source, target, edge);
     495      }
     496      return edge;
     497    }
    428498  };
    429499
     
    469539  /// Graph::EdgeMap<bool> em(g, true);
    470540  /// em.set(e, false);
    471   /// typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
    472   /// SubGW gw(g, nm, em);
    473   /// for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
     541  /// typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGA;
     542  /// SubGA ga(g, nm, em);
     543  /// for (SubGA::NodeIt n(ga); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
    474544  /// std::cout << ":-)" << std::endl;
    475   /// for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
     545  /// for (SubGA::EdgeIt e(ga); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
    476546  ///\endcode
    477547  /// The output of the above code is the following.
     
    481551  /// 1
    482552  ///\endcode
    483   /// Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
     553  /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to
    484554  /// \c Graph::Node that is why \c g.id(n) can be applied.
    485555  ///
     
    508578    }
    509579  };
     580
     581  /// \brief Just gives back a sub graph adaptor
     582  ///
     583  /// Just gives back a sub graph adaptor
     584  template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
     585  SubGraphAdaptor<const Graph, NodeFilterMap, EdgeFilterMap>
     586  subGraphAdaptor(const Graph& graph,
     587                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
     588    return SubGraphAdaptor<const Graph, NodeFilterMap, EdgeFilterMap>
     589      (graph, nfm, efm);
     590  }
     591
     592  template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
     593  SubGraphAdaptor<const Graph, const NodeFilterMap, EdgeFilterMap>
     594  subGraphAdaptor(const Graph& graph,
     595                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
     596    return SubGraphAdaptor<const Graph, const NodeFilterMap, EdgeFilterMap>
     597      (graph, nfm, efm);
     598  }
     599
     600  template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
     601  SubGraphAdaptor<const Graph, NodeFilterMap, const EdgeFilterMap>
     602  subGraphAdaptor(const Graph& graph,
     603                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
     604    return SubGraphAdaptor<const Graph, NodeFilterMap, const EdgeFilterMap>
     605      (graph, nfm, efm);
     606  }
     607
     608  template<typename Graph, typename NodeFilterMap, typename EdgeFilterMap>
     609  SubGraphAdaptor<const Graph, const NodeFilterMap, const EdgeFilterMap>
     610  subGraphAdaptor(const Graph& graph,
     611                   NodeFilterMap& nfm, EdgeFilterMap& efm) {
     612    return SubGraphAdaptor<const Graph, const NodeFilterMap,
     613      const EdgeFilterMap>(graph, nfm, efm);
     614  }
    510615
    511616
     
    534639  protected:
    535640    ConstMap<typename Graph::Edge, bool> const_true_map;
     641
     642    NodeSubGraphAdaptor() : const_true_map(true) {
     643      Parent::setEdgeFilterMap(const_true_map);
     644    }
     645
    536646  public:
    537647    NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
     
    543653  };
    544654
     655
     656  /// \brief Just gives back a node sub graph adaptor
     657  ///
     658  /// Just gives back a node sub graph adaptor
     659  template<typename Graph, typename NodeFilterMap>
     660  NodeSubGraphAdaptor<const Graph, NodeFilterMap>
     661  nodeSubGraphAdaptor(const Graph& graph, NodeFilterMap& nfm) {
     662    return NodeSubGraphAdaptor<const Graph, NodeFilterMap>(graph, nfm);
     663  }
     664
     665  template<typename Graph, typename NodeFilterMap>
     666  NodeSubGraphAdaptor<const Graph, const NodeFilterMap>
     667  nodeSubGraphAdaptor(const Graph& graph, const NodeFilterMap& nfm) {
     668    return NodeSubGraphAdaptor<const Graph, const NodeFilterMap>(graph, nfm);
     669  }
    545670
    546671  ///\brief An adaptor for hiding edges from a graph.
     
    631756  ///TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
    632757  ///
    633   ///typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
    634   ///SubGW gw(g, tight_edge_filter);
     758  ///typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGA;
     759  ///SubGA ga(g, tight_edge_filter);
    635760  ///\endcode
    636761  ///Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
     
    640765  ///Graph::EdgeMap<int> flow(g, 0);
    641766  ///
    642   ///Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
    643   ///  preflow(gw, s, t, const_1_map, flow);
     767  ///Preflow<SubGA, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
     768  ///  preflow(ga, s, t, const_1_map, flow);
    644769  ///preflow.run();
    645770  ///\endcode
     
    689814  protected:
    690815    ConstMap<typename Graph::Node, bool> const_true_map;
     816
     817    EdgeSubGraphAdaptor() : const_true_map(true) {
     818      Parent::setNodeFilterMap(const_true_map);
     819    }
     820
    691821  public:
    692822    EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
     
    698828  };
    699829
    700   template <typename _Graph>
     830  /// \brief Just gives back an edge sub graph adaptor
     831  ///
     832  /// Just gives back an edge sub graph adaptor
     833  template<typename Graph, typename EdgeFilterMap>
     834  EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>
     835  edgeSubGraphAdaptor(const Graph& graph, EdgeFilterMap& efm) {
     836    return EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>(graph, efm);
     837  }
     838
     839  template<typename Graph, typename EdgeFilterMap>
     840  EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>
     841  edgeSubGraphAdaptor(const Graph& graph, const EdgeFilterMap& efm) {
     842    return EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>(graph, efm);
     843  }
     844
     845  template <typename _Graph, typename Enable = void>
    701846  class UndirGraphAdaptorBase :
    702847    public UGraphBaseExtender<GraphAdaptorBase<_Graph> > {
     
    704849    typedef _Graph Graph;
    705850    typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;
     851
    706852  protected:
    707     UndirGraphAdaptorBase() : Parent() { }
    708   public:
     853
     854    UndirGraphAdaptorBase() : Parent() {}
     855
     856  public:
     857
    709858    typedef typename Parent::UEdge UEdge;
    710859    typedef typename Parent::Edge Edge;
     860
    711861   
    712     template <typename T>
     862    template <typename _Value>
    713863    class EdgeMap {
     864    private:
     865     
     866      typedef typename _Graph::template EdgeMap<_Value> MapImpl;
     867     
     868    public:
     869
     870      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
     871
     872      typedef _Value Value;
     873      typedef Edge Key;
     874     
     875      EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) :
     876        forward_map(*(_g.graph)), backward_map(*(_g.graph)) {}
     877
     878      EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, const Value& a)
     879        : forward_map(*(_g.graph), a), backward_map(*(_g.graph), a) {}
     880     
     881      void set(const Edge& e, const Value& a) {
     882        if (Parent::direction(e)) {
     883          forward_map.set(e, a);
     884        } else {
     885          backward_map.set(e, a);
     886        }
     887      }
     888
     889      typename MapTraits<MapImpl>::ConstReturnValue operator[](Edge e) const {
     890        if (Parent::direction(e)) {
     891          return forward_map[e];
     892        } else {
     893          return backward_map[e];
     894        }
     895      }
     896
     897      typename MapTraits<MapImpl>::ReturnValue operator[](Edge e) {
     898        if (Parent::direction(e)) {
     899          return forward_map[e];
     900        } else {
     901          return backward_map[e];
     902        }
     903      }
     904
    714905    protected:
    715       const UndirGraphAdaptorBase<_Graph>* g;
    716       template <typename TT> friend class EdgeMap;
    717       typename _Graph::template EdgeMap<T> forward_map, backward_map;
    718     public:
    719       typedef T Value;
    720       typedef Edge Key;
    721      
    722       EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) : g(&_g),
    723         forward_map(*(g->graph)), backward_map(*(g->graph)) { }
    724 
    725       EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, T a) : g(&_g),
    726         forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
    727      
    728       void set(Edge e, T a) {
    729         if (g->direction(e))
    730           forward_map.set(e, a);
    731         else
    732           backward_map.set(e, a);
    733       }
    734 
    735       T operator[](Edge e) const {
    736         if (g->direction(e))
    737           return forward_map[e];
    738         else
    739           return backward_map[e];
    740       }
     906
     907      MapImpl forward_map, backward_map;
     908
    741909    };
    742910       
    743     template <typename T>
    744     class UEdgeMap {
    745       template <typename TT> friend class UEdgeMap;
    746       typename _Graph::template EdgeMap<T> map;
     911    template <typename _Value>
     912    class UEdgeMap : public _Graph::template EdgeMap<_Value> {
    747913    public:
    748       typedef T Value;
    749       typedef UEdge Key;
    750      
    751       UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) :
    752         map(*(g.graph)) { }
    753 
    754       UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, T a) :
    755         map(*(g.graph), a) { }
    756      
    757       void set(UEdge e, T a) {
    758         map.set(e, a);
    759       }
    760 
    761       T operator[](UEdge e) const {
    762         return map[e];
    763       }
     914
     915      typedef typename _Graph::template EdgeMap<_Value> Parent;
     916
     917      UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g)
     918        : Parent(*(g.graph)) {}
     919
     920      UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, const _Value& a)
     921        : Parent(*(g.graph), a) {}
     922     
     923    };
     924     
     925  };
     926
     927  template <typename _Graph>
     928  class UndirGraphAdaptorBase<
     929    _Graph, typename enable_if<
     930    typename _Graph::EdgeNotifier::Notifier>::type >
     931      : public UGraphBaseExtender<GraphAdaptorBase<_Graph> > {
     932  public:
     933
     934    typedef _Graph Graph;
     935    typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;
     936
     937  protected:
     938
     939    UndirGraphAdaptorBase()
     940      : Parent(), edge_notifier(), edge_notifier_proxy(edge_notifier) {}
     941
     942    void setGraph(_Graph& graph) {
     943      Parent::setGraph(graph);
     944      edge_notifier_proxy.setUEdgeNotifier(graph.getNotifier(UEdge()));
     945    }
     946
     947  public:
     948
     949    ~UndirGraphAdaptorBase() {
     950      getNotifier(Edge()).clear();
     951    }
     952
     953
     954    typedef typename Parent::UEdge UEdge;
     955    typedef typename Parent::Edge Edge;
     956
     957    typedef typename Parent::EdgeNotifier UEdgeNotifier;
     958
     959    using Parent::getNotifier;
     960
     961    typedef AlterationNotifier<Edge> EdgeNotifier;
     962    EdgeNotifier& getNotifier(Edge) const { return edge_notifier; }
     963
     964  protected:
     965
     966    class NotifierProxy : public UEdgeNotifier::ObserverBase {
     967    public:
     968
     969      typedef typename UEdgeNotifier::ObserverBase Parent;
     970      typedef UndirGraphAdaptorBase AdaptorBase;
     971     
     972      NotifierProxy(EdgeNotifier& _edge_notifier)
     973        : Parent(), edge_notifier(_edge_notifier) {
     974      }
     975
     976      virtual ~NotifierProxy() {
     977        if (Parent::attached()) {
     978          Parent::detach();
     979        }
     980      }
     981
     982      void setUEdgeNotifier(UEdgeNotifier& _uedge_notifier) {
     983        Parent::attach(_uedge_notifier);
     984      }
     985
     986     
     987    protected:
     988
     989      virtual void add(const UEdge& uedge) {
     990        std::vector<Edge> edges;
     991        edges.push_back(AdaptorBase::Parent::direct(uedge, true));
     992        edges.push_back(AdaptorBase::Parent::direct(uedge, false));
     993        edge_notifier.add(edges);
     994      }
     995      virtual void add(const std::vector<UEdge>& uedges) {
     996        std::vector<Edge> edges;
     997        for (int i = 0; i < (int)uedges.size(); ++i) {
     998          edges.push_back(AdaptorBase::Parent::direct(uedges[i], true));
     999          edges.push_back(AdaptorBase::Parent::direct(uedges[i], false));
     1000        }
     1001        edge_notifier.add(edges);
     1002      }
     1003      virtual void erase(const UEdge& uedge) {
     1004        std::vector<Edge> edges;
     1005        edges.push_back(AdaptorBase::Parent::direct(uedge, true));
     1006        edges.push_back(AdaptorBase::Parent::direct(uedge, false));
     1007        edge_notifier.erase(edges);
     1008      }
     1009      virtual void erase(const std::vector<UEdge>& uedges) {
     1010        std::vector<Edge> edges;
     1011        for (int i = 0; i < (int)uedges.size(); ++i) {
     1012          edges.push_back(AdaptorBase::Parent::direct(uedges[i], true));
     1013          edges.push_back(AdaptorBase::Parent::direct(uedges[i], false));
     1014        }
     1015        edge_notifier.erase(edges);
     1016      }
     1017      virtual void build() {
     1018        edge_notifier.build();
     1019      }
     1020      virtual void clear() {
     1021        edge_notifier.clear();
     1022      }
     1023
     1024      EdgeNotifier& edge_notifier;
     1025    };
     1026
     1027
     1028    mutable EdgeNotifier edge_notifier;
     1029    NotifierProxy edge_notifier_proxy;
     1030
     1031  public:
     1032   
     1033   
     1034    template <typename _Value>
     1035    class EdgeMap {
     1036    private:
     1037     
     1038      typedef typename _Graph::template EdgeMap<_Value> MapImpl;
     1039     
     1040    public:
     1041
     1042      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
     1043
     1044      typedef _Value Value;
     1045      typedef Edge Key;
     1046     
     1047      EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) :
     1048        forward_map(*(_g.graph)), backward_map(*(_g.graph)) {}
     1049
     1050      EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, const Value& a)
     1051        : forward_map(*(_g.graph), a), backward_map(*(_g.graph), a) {}
     1052     
     1053      void set(const Edge& e, const Value& a) {
     1054        if (Parent::direction(e)) {
     1055          forward_map.set(e, a);
     1056        } else {
     1057          backward_map.set(e, a);
     1058        }
     1059      }
     1060
     1061      typename MapTraits<MapImpl>::ConstReturnValue
     1062      operator[](const Edge& e) const {
     1063        if (Parent::direction(e)) {
     1064          return forward_map[e];
     1065        } else {
     1066          return backward_map[e];
     1067        }
     1068      }
     1069
     1070      typename MapTraits<MapImpl>::ReturnValue
     1071      operator[](const Edge& e) {
     1072        if (Parent::direction(e)) {
     1073          return forward_map[e];
     1074        } else {
     1075          return backward_map[e];
     1076        }
     1077      }
     1078
     1079    protected:
     1080
     1081      MapImpl forward_map, backward_map;
     1082
     1083    };
     1084       
     1085    template <typename _Value>
     1086    class UEdgeMap : public _Graph::template EdgeMap<_Value> {
     1087    public:
     1088
     1089      typedef typename _Graph::template EdgeMap<_Value> Parent;
     1090
     1091      UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g)
     1092        : Parent(*(g.graph)) {}
     1093
     1094      UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, const _Value& a)
     1095        : Parent(*(g.graph), a) {}
     1096     
    7641097    };
    7651098     
     
    7871120      setGraph(_graph);
    7881121    }
     1122
     1123    template <typename _ForwardMap, typename _BackwardMap>
     1124    class CombinedEdgeMap {
     1125    public:
     1126     
     1127      typedef _ForwardMap ForwardMap;
     1128      typedef _BackwardMap BackwardMap;
     1129
     1130      typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
     1131
     1132      typedef typename ForwardMap::Value Value;
     1133      typedef typename Parent::Edge Key;
     1134     
     1135      CombinedEdgeMap() : forward_map(0), backward_map(0) {}
     1136
     1137      CombinedEdgeMap(ForwardMap& _forward_map, BackwardMap& _backward_map)
     1138        : forward_map(&_forward_map), backward_map(&_backward_map) {}
     1139     
     1140      void set(const Key& e, const Value& a) {
     1141        if (Parent::direction(e)) {
     1142          forward_map->set(e, a);
     1143        } else {
     1144          backward_map->set(e, a);
     1145        }
     1146      }
     1147
     1148      typename MapTraits<ForwardMap>::ConstReturnValue
     1149      operator[](const Key& e) const {
     1150        if (Parent::direction(e)) {
     1151          return (*forward_map)[e];
     1152        } else {
     1153          return (*backward_map)[e];
     1154        }
     1155      }
     1156
     1157      typename MapTraits<ForwardMap>::ReturnValue
     1158      operator[](const Key& e) {
     1159        if (Parent::direction(e)) {
     1160          return (*forward_map)[e];
     1161        } else {
     1162          return (*backward_map)[e];
     1163        }
     1164      }
     1165
     1166      void setForwardMap(ForwardMap& _forward_map) {
     1167        forward_map = &_forward_map;
     1168      }
     1169
     1170      void setBackwardMap(BackwardMap& _backward_map) {
     1171        backward_map = &_backward_map;
     1172      }
     1173
     1174    protected:
     1175
     1176      ForwardMap* forward_map;
     1177      BackwardMap* backward_map;
     1178
     1179    };
     1180
    7891181  };
    7901182
    791  
    792   template <typename _Graph,
    793             typename ForwardFilterMap, typename BackwardFilterMap>
    794   class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
    795   public:
    796     typedef _Graph Graph;
    797     typedef GraphAdaptorBase<_Graph> Parent;
    798   protected:
    799     ForwardFilterMap* forward_filter;
    800     BackwardFilterMap* backward_filter;
    801     SubBidirGraphAdaptorBase() : Parent(),
    802                                  forward_filter(0), backward_filter(0) { }
    803 
    804     void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
    805       forward_filter=&_forward_filter;
    806     }
    807     void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
    808       backward_filter=&_backward_filter;
    809     }
    810 
    811   public:
    812 //     SubGraphAdaptorBase(Graph& _graph,
    813 //                      NodeFilterMap& _node_filter_map,
    814 //                      EdgeFilterMap& _edge_filter_map) :
    815 //       Parent(&_graph),
    816 //       node_filter_map(&node_filter_map),
    817 //       edge_filter_map(&edge_filter_map) { }
    818 
    819     typedef typename Parent::Node Node;
    820     typedef typename _Graph::Edge GraphEdge;
    821     template <typename T> class EdgeMap;
    822     // SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from
    823     // _Graph::Edge. It contains an extra bool flag which is true
    824     // if and only if the
    825     // edge is the backward version of the original edge.
    826     class Edge : public _Graph::Edge {
    827       friend class SubBidirGraphAdaptorBase<
    828         Graph, ForwardFilterMap, BackwardFilterMap>;
    829       template<typename T> friend class EdgeMap;
    830     protected:
    831       bool backward; //true, iff backward
    832     public:
    833       Edge() { }
    834       // \todo =false is needed, or causes problems?
    835       // If \c _backward is false, then we get an edge corresponding to the
    836       // original one, otherwise its oppositely directed pair is obtained.
    837       Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
    838         _Graph::Edge(e), backward(_backward) { }
    839       Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
    840       bool operator==(const Edge& v) const {
    841         return (this->backward==v.backward &&
    842                 static_cast<typename _Graph::Edge>(*this)==
    843                 static_cast<typename _Graph::Edge>(v));
    844       }
    845       bool operator!=(const Edge& v) const {
    846         return (this->backward!=v.backward ||
    847                 static_cast<typename _Graph::Edge>(*this)!=
    848                 static_cast<typename _Graph::Edge>(v));
    849       }
    850     };
    851 
    852     void first(Node& i) const {
    853       Parent::first(i);
    854     }
    855 
    856     void first(Edge& i) const {
    857       Parent::first(i);
    858       i.backward=false;
    859       while (*static_cast<GraphEdge*>(&i)!=INVALID &&
    860              !(*forward_filter)[i]) Parent::next(i);
    861       if (*static_cast<GraphEdge*>(&i)==INVALID) {
    862         Parent::first(i);
    863         i.backward=true;
    864         while (*static_cast<GraphEdge*>(&i)!=INVALID &&
    865                !(*backward_filter)[i]) Parent::next(i);
    866       }
    867     }
    868 
    869     void firstIn(Edge& i, const Node& n) const {
    870       Parent::firstIn(i, n);
    871       i.backward=false;
    872       while (*static_cast<GraphEdge*>(&i)!=INVALID &&
    873              !(*forward_filter)[i]) Parent::nextIn(i);
    874       if (*static_cast<GraphEdge*>(&i)==INVALID) {
    875         Parent::firstOut(i, n);
    876         i.backward=true;
    877         while (*static_cast<GraphEdge*>(&i)!=INVALID &&
    878                !(*backward_filter)[i]) Parent::nextOut(i);
    879       }
    880     }
    881 
    882     void firstOut(Edge& i, const Node& n) const {
    883       Parent::firstOut(i, n);
    884       i.backward=false;
    885       while (*static_cast<GraphEdge*>(&i)!=INVALID &&
    886              !(*forward_filter)[i]) Parent::nextOut(i);
    887       if (*static_cast<GraphEdge*>(&i)==INVALID) {
    888         Parent::firstIn(i, n);
    889         i.backward=true;
    890         while (*static_cast<GraphEdge*>(&i)!=INVALID &&
    891                !(*backward_filter)[i]) Parent::nextIn(i);
    892       }
    893     }
    894 
    895     void next(Node& i) const {
    896       Parent::next(i);
    897     }
    898 
    899     void next(Edge& i) const {
    900       if (!(i.backward)) {
    901         Parent::next(i);
    902         while (*static_cast<GraphEdge*>(&i)!=INVALID &&
    903                !(*forward_filter)[i]) Parent::next(i);
    904         if (*static_cast<GraphEdge*>(&i)==INVALID) {
    905           Parent::first(i);
    906           i.backward=true;
    907           while (*static_cast<GraphEdge*>(&i)!=INVALID &&
    908                  !(*backward_filter)[i]) Parent::next(i);
    909         }
    910       } else {
    911         Parent::next(i);
    912         while (*static_cast<GraphEdge*>(&i)!=INVALID &&
    913                !(*backward_filter)[i]) Parent::next(i);
    914       }
    915     }
    916 
    917     void nextIn(Edge& i) const {
    918       if (!(i.backward)) {
    919         Node n=Parent::target(i);
    920         Parent::nextIn(i);
    921         while (*static_cast<GraphEdge*>(&i)!=INVALID &&
    922                !(*forward_filter)[i]) Parent::nextIn(i);
    923         if (*static_cast<GraphEdge*>(&i)==INVALID) {
    924           Parent::firstOut(i, n);
    925           i.backward=true;
    926           while (*static_cast<GraphEdge*>(&i)!=INVALID &&
    927                  !(*backward_filter)[i]) Parent::nextOut(i);
    928         }
    929       } else {
    930         Parent::nextOut(i);
    931         while (*static_cast<GraphEdge*>(&i)!=INVALID &&
    932                !(*backward_filter)[i]) Parent::nextOut(i);
    933       }
    934     }
    935 
    936     void nextOut(Edge& i) const {
    937       if (!(i.backward)) {
    938         Node n=Parent::source(i);
    939         Parent::nextOut(i);
    940         while (*static_cast<GraphEdge*>(&i)!=INVALID &&
    941                !(*forward_filter)[i]) Parent::nextOut(i);
    942         if (*static_cast<GraphEdge*>(&i)==INVALID) {
    943           Parent::firstIn(i, n);
    944           i.backward=true;
    945           while (*static_cast<GraphEdge*>(&i)!=INVALID &&
    946                  !(*backward_filter)[i]) Parent::nextIn(i);
    947         }
    948       } else {
    949         Parent::nextIn(i);
    950         while (*static_cast<GraphEdge*>(&i)!=INVALID &&
    951                !(*backward_filter)[i]) Parent::nextIn(i);
    952       }
    953     }
    954 
    955     Node source(Edge e) const {
    956       return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
    957     Node target(Edge e) const {
    958       return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
    959 
    960     /// Gives back the opposite edge.
    961 
    962     ///\e
    963     ///
    964     Edge opposite(const Edge& e) const {
    965       Edge f=e;
    966       f.backward=!f.backward;
    967       return f;
    968     }
    969 
    970     ///\e
    971 
    972     /// \warning This is a linear time operation and works only if
    973     /// \c Graph::EdgeIt is defined.
    974     /// \todo hmm
    975     int edgeNum() const {
    976       int i=0;
    977       Edge e;
    978       for (first(e); e!=INVALID; next(e)) ++i;
    979       return i;
    980     }
    981 
    982     bool forward(const Edge& e) const { return !e.backward; }
    983     bool backward(const Edge& e) const { return e.backward; }
    984 
    985     ///\e
    986 
    987     /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two
    988     /// _Graph::EdgeMap one for the forward edges and
    989     /// one for the backward edges.
    990     template <typename T>
    991     class EdgeMap {
    992       template <typename TT> friend class EdgeMap;
    993       typename _Graph::template EdgeMap<T> forward_map, backward_map;
    994     public:
    995       typedef T Value;
    996       typedef Edge Key;
    997 
    998       EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
    999               ForwardFilterMap, BackwardFilterMap>& g) :
    1000         forward_map(*(g.graph)), backward_map(*(g.graph)) { }
    1001 
    1002       EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
    1003               ForwardFilterMap, BackwardFilterMap>& g, T a) :
    1004         forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
    1005      
    1006       void set(Edge e, T a) {
    1007         if (!e.backward)
    1008           forward_map.set(e, a);
    1009         else
    1010           backward_map.set(e, a);
    1011       }
    1012 
    1013 //       typename _Graph::template EdgeMap<T>::ConstReference
    1014 //       operator[](Edge e) const {
    1015 //      if (!e.backward)
    1016 //        return forward_map[e];
    1017 //      else
    1018 //        return backward_map[e];
    1019 //       }
    1020 
    1021 //      typename _Graph::template EdgeMap<T>::Reference
    1022       T operator[](Edge e) const {
    1023         if (!e.backward)
    1024           return forward_map[e];
    1025         else
    1026           return backward_map[e];
    1027       }
    1028 
    1029       void update() {
    1030         forward_map.update();
    1031         backward_map.update();
    1032       }
    1033     };
    1034 
    1035   };
    1036 
    1037 
    1038   ///\brief An adaptor for composing a subgraph of a
    1039   /// bidirected graph made from a directed one.
    1040   ///\ingroup graph_adaptors
    1041   ///
    1042   /// An adaptor for composing a subgraph of a
    1043   /// bidirected graph made from a directed one.
    1044   ///
    1045   ///\warning Graph adaptors are in even more experimental state
    1046   ///than the other
    1047   ///parts of the lib. Use them at you own risk.
    1048   ///
    1049   /// Let \f$ G=(V, A) \f$ be a directed graph and for each directed edge
    1050   ///\f$ e\in A \f$, let \f$ \bar e \f$ denote the edge obtained by
    1051   /// reversing its orientation. We are given moreover two bool valued
    1052   /// maps on the edge-set,
    1053   ///\f$ forward\_filter \f$, and \f$ backward\_filter \f$.
    1054   /// SubBidirGraphAdaptor implements the graph structure with node-set
    1055   ///\f$ V \f$ and edge-set
    1056   ///\f$ \{e : e\in A \mbox{ and } forward\_filter(e) \mbox{ is true}\}+\{\bar e : e\in A \mbox{ and } backward\_filter(e) \mbox{ is true}\} \f$.
    1057   /// The purpose of writing + instead of union is because parallel
    1058   /// edges can arise. (Similarly, antiparallel edges also can arise).
    1059   /// In other words, a subgraph of the bidirected graph obtained, which
    1060   /// is given by orienting the edges of the original graph in both directions.
    1061   /// As the oppositely directed edges are logically different,
    1062   /// the maps are able to attach different values for them.
    1063   ///
    1064   /// An example for such a construction is \c RevGraphAdaptor where the
    1065   /// forward_filter is everywhere false and the backward_filter is
    1066   /// everywhere true. We note that for sake of efficiency,
    1067   /// \c RevGraphAdaptor is implemented in a different way.
    1068   /// But BidirGraphAdaptor is obtained from
    1069   /// SubBidirGraphAdaptor by considering everywhere true
    1070   /// valued maps both for forward_filter and backward_filter.
    1071   ///
    1072   /// The most important application of SubBidirGraphAdaptor
    1073   /// is ResGraphAdaptor, which stands for the residual graph in directed
    1074   /// flow and circulation problems.
    1075   /// As adaptors usually, the SubBidirGraphAdaptor implements the
    1076   /// above mentioned graph structure without its physical storage,
    1077   /// that is the whole stuff is stored in constant memory.
    1078   template<typename _Graph,
    1079            typename ForwardFilterMap, typename BackwardFilterMap>
    1080   class SubBidirGraphAdaptor :
    1081     public GraphAdaptorExtender<
    1082     SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
    1083   public:
    1084     typedef _Graph Graph;
    1085     typedef GraphAdaptorExtender<
    1086       SubBidirGraphAdaptorBase<
    1087       _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
    1088   protected:
    1089     SubBidirGraphAdaptor() { }
    1090   public:
    1091     SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter,
    1092                          BackwardFilterMap& _backward_filter) {
    1093       setGraph(_graph);
    1094       setForwardFilterMap(_forward_filter);
    1095       setBackwardFilterMap(_backward_filter);
    1096     }
    1097   };
    1098 
    1099 
    1100 
    1101   ///\brief An adaptor for composing bidirected graph from a directed one.
    1102   ///\ingroup graph_adaptors
    1103   ///
    1104   ///\warning Graph adaptors are in even more experimental state
    1105   ///than the other
    1106   ///parts of the lib. Use them at you own risk.
    1107   ///
    1108   /// An adaptor for composing bidirected graph from a directed one.
    1109   /// A bidirected graph is composed over the directed one without physical
    1110   /// storage. As the oppositely directed edges are logically different ones
    1111   /// the maps are able to attach different values for them.
     1183  /// \brief Just gives back an undir graph adaptor
     1184  ///
     1185  /// Just gives back an undir graph adaptor
    11121186  template<typename Graph>
    1113   class BidirGraphAdaptor :
    1114     public SubBidirGraphAdaptor<
    1115     Graph,
    1116     ConstMap<typename Graph::Edge, bool>,
    1117     ConstMap<typename Graph::Edge, bool> > {
    1118   public:
    1119     typedef  SubBidirGraphAdaptor<
    1120       Graph,
    1121       ConstMap<typename Graph::Edge, bool>,
    1122       ConstMap<typename Graph::Edge, bool> > Parent;
    1123   protected:
    1124     ConstMap<typename Graph::Edge, bool> cm;
    1125 
    1126     BidirGraphAdaptor() : Parent(), cm(true) {
    1127       Parent::setForwardFilterMap(cm);
    1128       Parent::setBackwardFilterMap(cm);
    1129     }
    1130   public:
    1131     BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) {
    1132       Parent::setGraph(_graph);
    1133       Parent::setForwardFilterMap(cm);
    1134       Parent::setBackwardFilterMap(cm);
    1135     }
    1136 
    1137     int edgeNum() const {
    1138       return 2*this->graph->edgeNum();
    1139     }
    1140   };
    1141 
     1187  UndirGraphAdaptor<const Graph>
     1188  undirGraphAdaptor(const Graph& graph) {
     1189    return UndirGraphAdaptor<const Graph>(graph);
     1190  }
    11421191
    11431192  template<typename Graph, typename Number,
    11441193           typename CapacityMap, typename FlowMap>
    11451194  class ResForwardFilter {
    1146     //    const Graph* graph;
    11471195    const CapacityMap* capacity;
    11481196    const FlowMap* flow;
    11491197  public:
    1150     ResForwardFilter(/*const Graph& _graph, */
    1151                      const CapacityMap& _capacity, const FlowMap& _flow) :
    1152       /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
    1153     ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
    1154     void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
    1155     void setFlow(const FlowMap& _flow) { flow=&_flow; }
     1198    typedef typename Graph::Edge Key;
     1199    typedef bool Value;
     1200
     1201    ResForwardFilter(const CapacityMap& _capacity, const FlowMap& _flow)
     1202      : capacity(&_capacity), flow(&_flow) { }
     1203    ResForwardFilter() : capacity(0), flow(0) { }
     1204    void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
     1205    void setFlow(const FlowMap& _flow) { flow = &_flow; }
    11561206    bool operator[](const typename Graph::Edge& e) const {
    11571207      return (Number((*flow)[e]) < Number((*capacity)[e]));
     
    11651215    const FlowMap* flow;
    11661216  public:
    1167     ResBackwardFilter(/*const Graph& _graph,*/
    1168                       const CapacityMap& _capacity, const FlowMap& _flow) :
    1169       /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
    1170     ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
    1171     void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
    1172     void setFlow(const FlowMap& _flow) { flow=&_flow; }
     1217    typedef typename Graph::Edge Key;
     1218    typedef bool Value;
     1219
     1220    ResBackwardFilter(const CapacityMap& _capacity, const FlowMap& _flow)
     1221      : capacity(&_capacity), flow(&_flow) { }
     1222    ResBackwardFilter() : capacity(0), flow(0) { }
     1223    void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
     1224    void setFlow(const FlowMap& _flow) { flow = &_flow; }
    11731225    bool operator[](const typename Graph::Edge& e) const {
    11741226      return (Number(0) < Number((*flow)[e]));
     
    12081260  ///Graph::EdgeMap<int> f(g);
    12091261  ///Graph::EdgeMap<int> c(g);
    1210   ///ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
     1262  ///ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > ga(g);
    12111263  ///\endcode
    12121264  ///\author Marton Makai
     
    12151267           typename CapacityMap, typename FlowMap>
    12161268  class ResGraphAdaptor :
    1217     public SubBidirGraphAdaptor<
    1218     Graph,
     1269    public EdgeSubGraphAdaptor<
     1270    UndirGraphAdaptor<Graph>,
     1271    typename UndirGraphAdaptor<Graph>::template CombinedEdgeMap<
    12191272    ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
    1220     ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
    1221   public:
    1222     typedef SubBidirGraphAdaptor<
    1223       Graph,
    1224       ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
    1225       ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
     1273    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > > {
     1274  public:
     1275
     1276    typedef UndirGraphAdaptor<Graph> UGraph;
     1277
     1278    typedef ResForwardFilter<Graph, Number, CapacityMap, FlowMap>
     1279    ForwardFilter;
     1280
     1281    typedef ResBackwardFilter<Graph, Number, CapacityMap, FlowMap>
     1282    BackwardFilter;
     1283
     1284    typedef typename UGraph::
     1285    template CombinedEdgeMap<ForwardFilter, BackwardFilter>
     1286    EdgeFilter;
     1287
     1288    typedef EdgeSubGraphAdaptor<UGraph, EdgeFilter> Parent;
     1289
    12261290  protected:
     1291
    12271292    const CapacityMap* capacity;
    12281293    FlowMap* flow;
    1229     ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
    1230     ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
    1231     ResGraphAdaptor() : Parent(),
    1232                         capacity(0), flow(0) { }
     1294
     1295    UGraph ugraph;
     1296    ForwardFilter forward_filter;
     1297    BackwardFilter backward_filter;
     1298    EdgeFilter edge_filter;
     1299
    12331300    void setCapacityMap(const CapacityMap& _capacity) {
    12341301      capacity=&_capacity;
     
    12361303      backward_filter.setCapacity(_capacity);
    12371304    }
     1305
    12381306    void setFlowMap(FlowMap& _flow) {
    12391307      flow=&_flow;
     
    12411309      backward_filter.setFlow(_flow);
    12421310    }
    1243   public:
     1311
     1312  public:
     1313
    12441314    ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity,
    1245                        FlowMap& _flow) :
    1246       Parent(), capacity(&_capacity), flow(&_flow),
    1247       forward_filter(/*_graph,*/ _capacity, _flow),
    1248       backward_filter(/*_graph,*/ _capacity, _flow) {
    1249       Parent::setGraph(_graph);
    1250       Parent::setForwardFilterMap(forward_filter);
    1251       Parent::setBackwardFilterMap(backward_filter);
     1315                    FlowMap& _flow)
     1316      : Parent(), capacity(&_capacity), flow(&_flow),
     1317        ugraph(_graph),
     1318        forward_filter(_capacity, _flow),
     1319        backward_filter(_capacity, _flow),
     1320        edge_filter(forward_filter, backward_filter) {
     1321      Parent::setGraph(ugraph);
     1322      Parent::setEdgeFilterMap(edge_filter);
    12521323    }
    12531324
     
    12551326
    12561327    void augment(const Edge& e, Number a) const {
    1257       if (Parent::forward(e)) 
     1328      if (UGraph::direction(e)) {
    12581329        flow->set(e, (*flow)[e]+a);
    1259       else 
     1330      } else { 
    12601331        flow->set(e, (*flow)[e]-a);
    1261     }
     1332      }
     1333    }
     1334
     1335    static bool forward(const Edge& e) {
     1336      return UGraph::direction(e);
     1337    }
     1338
     1339    static bool backward(const Edge& e) {
     1340      return !UGraph::direction(e);
     1341    }
     1342
     1343    static Edge forward(const typename Graph::Edge& e) {
     1344      return UGraph::direct(e, true);
     1345    }
     1346
     1347    static Edge backward(const typename Graph::Edge& e) {
     1348      return UGraph::direct(e, false);
     1349    }
     1350
    12621351
    12631352    /// \brief Residual capacity map.
     
    12671356    class ResCap {
    12681357    protected:
    1269       const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>* res_graph;
     1358      const ResGraphAdaptor* res_graph;
    12701359    public:
    12711360      typedef Number Value;
    12721361      typedef Edge Key;
    1273       ResCap(const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>&
    1274              _res_graph) : res_graph(&_res_graph) { }
     1362      ResCap(const ResGraphAdaptor& _res_graph)
     1363        : res_graph(&_res_graph) {}
     1364     
    12751365      Number operator[](const Edge& e) const {
    1276         if (res_graph->forward(e))
     1366        if (ResGraphAdaptor::direction(e))
    12771367          return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
    12781368        else
    12791369          return (*(res_graph->flow))[e];
    12801370      }
     1371     
    12811372    };
    12821373
    1283     //    KEEP_MAPS(Parent, ResGraphAdaptor);
    12841374  };
    12851375
  • lemon/list_graph.h

    r1984 r1991  
    963963  ///
    964964  /// This is a bipartite undirected graph implementation.
    965   /// Except from this it conforms to
    966   /// the \ref concept::BpUGraph "BpUGraph" concept.
     965  /// It is conforms to the \ref concept::ErasableBpUGraph "ErasableBpUGraph"
     966  /// concept.
    967967  /// \sa concept::BpUGraph.
    968968  ///
  • 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.