COIN-OR::LEMON - Graph Library

Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/adaptors.h

    r956 r703  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    361361  /// parameter is set to be \c const.
    362362  ///
    363   /// This class provides item counting in the same time as the adapted
    364   /// digraph structure.
    365   ///
    366363  /// \tparam DGR The type of the adapted digraph.
    367364  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
     
    422419      Parent::initialize(digraph);
    423420      _node_filter = &node_filter;
    424       _arc_filter = &arc_filter;
     421      _arc_filter = &arc_filter;     
    425422    }
    426423
     
    509506
    510507    template <typename V>
    511     class NodeMap
    512       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    513               LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
     508    class NodeMap 
     509      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 
     510              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
    514511      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    515         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
     512        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
    516513
    517514    public:
     
    536533
    537534    template <typename V>
    538     class ArcMap
     535    class ArcMap 
    539536      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    540               LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
     537              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
    541538      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    542539        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
     
    583580      Parent::initialize(digraph);
    584581      _node_filter = &node_filter;
    585       _arc_filter = &arc_filter;
     582      _arc_filter = &arc_filter;     
    586583    }
    587584
     
    652649
    653650    template <typename V>
    654     class NodeMap
     651    class NodeMap 
    655652      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    656653          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
    657       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
     654      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 
    658655        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
    659656
     
    679676
    680677    template <typename V>
    681     class ArcMap
     678    class ArcMap 
    682679      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    683680          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
     
    722719  /// by adding or removing nodes or arcs, unless the \c GR template
    723720  /// parameter is set to be \c const.
    724   ///
    725   /// This class provides only linear time counting for nodes and arcs.
    726721  ///
    727722  /// \tparam DGR The type of the adapted digraph.
     
    10221017
    10231018    template <typename V>
    1024     class NodeMap
     1019    class NodeMap 
    10251020      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10261021          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
    1027       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
     1022      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
    10281023        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
    10291024
     
    10491044
    10501045    template <typename V>
    1051     class ArcMap
     1046    class ArcMap 
    10521047      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10531048          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
    1054       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
     1049      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
    10551050        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
    10561051
     
    10761071
    10771072    template <typename V>
    1078     class EdgeMap
     1073    class EdgeMap 
    10791074      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10801075        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
    1081       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
     1076      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
    10821077        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
    10831078
     
    11181113    NF* _node_filter;
    11191114    EF* _edge_filter;
    1120     SubGraphBase()
    1121           : Parent(), _node_filter(0), _edge_filter(0) { }
     1115    SubGraphBase() 
     1116          : Parent(), _node_filter(0), _edge_filter(0) { }
    11221117
    11231118    void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
     
    12201215
    12211216    template <typename V>
    1222     class NodeMap
     1217    class NodeMap 
    12231218      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12241219          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
    1225       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
     1220      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
    12261221        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
    12271222
     
    12471242
    12481243    template <typename V>
    1249     class ArcMap
     1244    class ArcMap 
    12501245      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12511246          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
    1252       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
     1247      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
    12531248        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
    12541249
     
    12741269
    12751270    template <typename V>
    1276     class EdgeMap
     1271    class EdgeMap 
    12771272      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12781273        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
    1279       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    1280         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
     1274      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
     1275        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
    12811276
    12821277    public:
     
    13191314  /// by adding or removing nodes or edges, unless the \c GR template
    13201315  /// parameter is set to be \c const.
    1321   ///
    1322   /// This class provides only linear time counting for nodes, edges and arcs.
    13231316  ///
    13241317  /// \tparam GR The type of the adapted graph.
     
    14781471  /// by adding or removing nodes or arcs/edges, unless the \c GR template
    14791472  /// parameter is set to be \c const.
    1480   ///
    1481   /// This class provides only linear time item counting.
    14821473  ///
    14831474  /// \tparam GR The type of the adapted digraph or graph.
     
    15051496#endif
    15061497    typedef DigraphAdaptorExtender<
    1507       SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
     1498      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >, 
    15081499                     true> > Parent;
    15091500
     
    15261517    /// Creates a subgraph for the given digraph or graph with the
    15271518    /// given node filter map.
    1528     FilterNodes(GR& graph, NF& node_filter)
     1519    FilterNodes(GR& graph, NF& node_filter) 
    15291520      : Parent(), const_true_map()
    15301521    {
     
    15641555                    typename enable_if<UndirectedTagIndicator<GR> >::type> :
    15651556    public GraphAdaptorExtender<
    1566       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
     1557      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 
    15671558                   true> > {
    15681559
    15691560    typedef GraphAdaptorExtender<
    1570       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
     1561      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 
    15711562                   true> > Parent;
    15721563
     
    16281619  /// by adding or removing nodes or arcs, unless the \c GR template
    16291620  /// parameter is set to be \c const.
    1630   ///
    1631   /// This class provides only linear time counting for nodes and arcs.
    16321621  ///
    16331622  /// \tparam DGR The type of the adapted digraph.
     
    16541643#endif
    16551644    typedef DigraphAdaptorExtender<
    1656       SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
     1645      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >, 
    16571646                     AF, false> > Parent;
    16581647
     
    17401729  /// by adding or removing nodes or edges, unless the \c GR template
    17411730  /// parameter is set to be \c const.
    1742   ///
    1743   /// This class provides only linear time counting for nodes, edges and arcs.
    17441731  ///
    17451732  /// \tparam GR The type of the adapted graph.
     
    17621749  class FilterEdges :
    17631750    public GraphAdaptorExtender<
    1764       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >,
     1751      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >, 
    17651752                   EF, false> > {
    17661753#endif
    17671754    typedef GraphAdaptorExtender<
    1768       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,
     1755      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >, 
    17691756                   EF, false> > Parent;
    17701757
     
    17911778    /// Creates a subgraph for the given graph with the given edge
    17921779    /// filter map.
    1793     FilterEdges(GR& graph, EF& edge_filter)
     1780    FilterEdges(GR& graph, EF& edge_filter) 
    17941781      : Parent(), const_true_map() {
    17951782      Parent::initialize(graph, const_true_map, edge_filter);
     
    18591846      bool _forward;
    18601847
    1861       Arc(const Edge& edge, bool forward)
     1848      Arc(const Edge& edge, bool forward) 
    18621849        : _edge(edge), _forward(forward) {}
    18631850
     
    20992086
    21002087      ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value)
    2101         : _forward(*adaptor._digraph, value),
     2088        : _forward(*adaptor._digraph, value), 
    21022089          _backward(*adaptor._digraph, value) {}
    21032090
     
    22172204    typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;
    22182205    EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
    2219 
     2206   
    22202207    typedef EdgeNotifier ArcNotifier;
    22212208    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }
     
    22452232  /// by adding or removing nodes or edges, unless the \c GR template
    22462233  /// parameter is set to be \c const.
    2247   ///
    2248   /// This class provides item counting in the same time as the adapted
    2249   /// digraph structure.
    22502234  ///
    22512235  /// \tparam DGR The type of the adapted digraph.
     
    25512535  /// by adding or removing nodes or arcs, unless the \c GR template
    25522536  /// parameter is set to be \c const.
    2553   ///
    2554   /// This class provides item counting in the same time as the adapted
    2555   /// graph structure.
    25562537  ///
    25572538  /// \tparam GR The type of the adapted graph.
     
    26982679  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
    26992680  ///
    2700   /// This class provides only linear time counting for nodes and arcs.
    2701   ///
    27022681  /// \tparam DGR The type of the adapted digraph.
    27032682  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
     
    27292708           typename FM = CM,
    27302709           typename TL = Tolerance<typename CM::Value> >
    2731   class ResidualDigraph
     2710  class ResidualDigraph 
    27322711    : public SubDigraph<
    27332712        Undirector<const DGR>,
     
    27862765    ResidualDigraph(const DGR& digraph, const CM& capacity,
    27872766                    FM& flow, const TL& tolerance = Tolerance())
    2788       : Parent(), _capacity(&capacity), _flow(&flow),
     2767      : Parent(), _capacity(&capacity), _flow(&flow), 
    27892768        _graph(digraph), _node_filter(),
    27902769        _forward_filter(capacity, flow, tolerance),
     
    28682847
    28692848      /// Constructor
    2870       ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor)
     2849      ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor) 
    28712850        : _adaptor(&adaptor) {}
    28722851
     
    33473326  /// in the adaptor.
    33483327  ///
    3349   /// This class provides item counting in the same time as the adapted
    3350   /// digraph structure.
    3351   ///
    33523328  /// \tparam DGR The type of the adapted digraph.
    33533329  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
     
    34483424    /// to get a node map of the split digraph.
    34493425    /// Its value type is inherited from the first node map type (\c IN).
    3450     /// \tparam IN The type of the node map for the in-nodes.
     3426    /// \tparam IN The type of the node map for the in-nodes. 
    34513427    /// \tparam OUT The type of the node map for the out-nodes.
    34523428    template <typename IN, typename OUT>
Note: See TracChangeset for help on using the changeset viewer.