lemon/adaptors.h
changeset 629 70a356a461a5
parent 579 d11bf7998905
child 656 cb38ccedd2c1
equal deleted inserted replaced
17:a57f9d421f45 18:eb42694f3106
   107     typedef typename ItemSetTraits<DGR, Arc>::ItemNotifier ArcNotifier;
   107     typedef typename ItemSetTraits<DGR, Arc>::ItemNotifier ArcNotifier;
   108     ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }
   108     ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); }
   109 
   109 
   110     template <typename V>
   110     template <typename V>
   111     class NodeMap : public DGR::template NodeMap<V> {
   111     class NodeMap : public DGR::template NodeMap<V> {
       
   112       typedef typename DGR::template NodeMap<V> Parent;
       
   113 
   112     public:
   114     public:
   113 
       
   114       typedef typename DGR::template NodeMap<V> Parent;
       
   115 
       
   116       explicit NodeMap(const Adaptor& adaptor)
   115       explicit NodeMap(const Adaptor& adaptor)
   117         : Parent(*adaptor._digraph) {}
   116         : Parent(*adaptor._digraph) {}
   118 
       
   119       NodeMap(const Adaptor& adaptor, const V& value)
   117       NodeMap(const Adaptor& adaptor, const V& value)
   120         : Parent(*adaptor._digraph, value) { }
   118         : Parent(*adaptor._digraph, value) { }
   121 
   119 
   122     private:
   120     private:
   123       NodeMap& operator=(const NodeMap& cmap) {
   121       NodeMap& operator=(const NodeMap& cmap) {
   132 
   130 
   133     };
   131     };
   134 
   132 
   135     template <typename V>
   133     template <typename V>
   136     class ArcMap : public DGR::template ArcMap<V> {
   134     class ArcMap : public DGR::template ArcMap<V> {
       
   135       typedef typename DGR::template ArcMap<V> Parent;
       
   136 
   137     public:
   137     public:
   138 
       
   139       typedef typename DGR::template ArcMap<V> Parent;
       
   140 
       
   141       explicit ArcMap(const DigraphAdaptorBase<DGR>& adaptor)
   138       explicit ArcMap(const DigraphAdaptorBase<DGR>& adaptor)
   142         : Parent(*adaptor._digraph) {}
   139         : Parent(*adaptor._digraph) {}
   143 
       
   144       ArcMap(const DigraphAdaptorBase<DGR>& adaptor, const V& value)
   140       ArcMap(const DigraphAdaptorBase<DGR>& adaptor, const V& value)
   145         : Parent(*adaptor._digraph, value) {}
   141         : Parent(*adaptor._digraph, value) {}
   146 
   142 
   147     private:
   143     private:
   148       ArcMap& operator=(const ArcMap& cmap) {
   144       ArcMap& operator=(const ArcMap& cmap) {
   253     typedef typename ItemSetTraits<GR, Edge>::ItemNotifier EdgeNotifier;
   249     typedef typename ItemSetTraits<GR, Edge>::ItemNotifier EdgeNotifier;
   254     EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }
   250     EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); }
   255 
   251 
   256     template <typename V>
   252     template <typename V>
   257     class NodeMap : public GR::template NodeMap<V> {
   253     class NodeMap : public GR::template NodeMap<V> {
       
   254       typedef typename GR::template NodeMap<V> Parent;
       
   255 
   258     public:
   256     public:
   259       typedef typename GR::template NodeMap<V> Parent;
       
   260       explicit NodeMap(const GraphAdaptorBase<GR>& adapter)
   257       explicit NodeMap(const GraphAdaptorBase<GR>& adapter)
   261         : Parent(*adapter._graph) {}
   258         : Parent(*adapter._graph) {}
   262       NodeMap(const GraphAdaptorBase<GR>& adapter, const V& value)
   259       NodeMap(const GraphAdaptorBase<GR>& adapter, const V& value)
   263         : Parent(*adapter._graph, value) {}
   260         : Parent(*adapter._graph, value) {}
   264 
   261 
   275 
   272 
   276     };
   273     };
   277 
   274 
   278     template <typename V>
   275     template <typename V>
   279     class ArcMap : public GR::template ArcMap<V> {
   276     class ArcMap : public GR::template ArcMap<V> {
       
   277       typedef typename GR::template ArcMap<V> Parent;
       
   278 
   280     public:
   279     public:
   281       typedef typename GR::template ArcMap<V> Parent;
       
   282       explicit ArcMap(const GraphAdaptorBase<GR>& adapter)
   280       explicit ArcMap(const GraphAdaptorBase<GR>& adapter)
   283         : Parent(*adapter._graph) {}
   281         : Parent(*adapter._graph) {}
   284       ArcMap(const GraphAdaptorBase<GR>& adapter, const V& value)
   282       ArcMap(const GraphAdaptorBase<GR>& adapter, const V& value)
   285         : Parent(*adapter._graph, value) {}
   283         : Parent(*adapter._graph, value) {}
   286 
   284 
   296       }
   294       }
   297     };
   295     };
   298 
   296 
   299     template <typename V>
   297     template <typename V>
   300     class EdgeMap : public GR::template EdgeMap<V> {
   298     class EdgeMap : public GR::template EdgeMap<V> {
       
   299       typedef typename GR::template EdgeMap<V> Parent;
       
   300 
   301     public:
   301     public:
   302       typedef typename GR::template EdgeMap<V> Parent;
       
   303       explicit EdgeMap(const GraphAdaptorBase<GR>& adapter)
   302       explicit EdgeMap(const GraphAdaptorBase<GR>& adapter)
   304         : Parent(*adapter._graph) {}
   303         : Parent(*adapter._graph) {}
   305       EdgeMap(const GraphAdaptorBase<GR>& adapter, const V& value)
   304       EdgeMap(const GraphAdaptorBase<GR>& adapter, const V& value)
   306         : Parent(*adapter._graph, value) {}
   305         : Parent(*adapter._graph, value) {}
   307 
   306 
   319 
   318 
   320   };
   319   };
   321 
   320 
   322   template <typename DGR>
   321   template <typename DGR>
   323   class ReverseDigraphBase : public DigraphAdaptorBase<DGR> {
   322   class ReverseDigraphBase : public DigraphAdaptorBase<DGR> {
       
   323     typedef DigraphAdaptorBase<DGR> Parent;
   324   public:
   324   public:
   325     typedef DGR Digraph;
   325     typedef DGR Digraph;
   326     typedef DigraphAdaptorBase<DGR> Parent;
       
   327   protected:
   326   protected:
   328     ReverseDigraphBase() : Parent() { }
   327     ReverseDigraphBase() : Parent() { }
   329   public:
   328   public:
   330     typedef typename Parent::Node Node;
   329     typedef typename Parent::Node Node;
   331     typedef typename Parent::Arc Arc;
   330     typedef typename Parent::Arc Arc;
   372   class ReverseDigraph {
   371   class ReverseDigraph {
   373 #else
   372 #else
   374   class ReverseDigraph :
   373   class ReverseDigraph :
   375     public DigraphAdaptorExtender<ReverseDigraphBase<DGR> > {
   374     public DigraphAdaptorExtender<ReverseDigraphBase<DGR> > {
   376 #endif
   375 #endif
       
   376     typedef DigraphAdaptorExtender<ReverseDigraphBase<DGR> > Parent;
   377   public:
   377   public:
   378     /// The type of the adapted digraph.
   378     /// The type of the adapted digraph.
   379     typedef DGR Digraph;
   379     typedef DGR Digraph;
   380     typedef DigraphAdaptorExtender<ReverseDigraphBase<DGR> > Parent;
       
   381   protected:
   380   protected:
   382     ReverseDigraph() { }
   381     ReverseDigraph() { }
   383   public:
   382   public:
   384 
   383 
   385     /// \brief Constructor
   384     /// \brief Constructor
   401   }
   400   }
   402 
   401 
   403 
   402 
   404   template <typename DGR, typename NF, typename AF, bool ch = true>
   403   template <typename DGR, typename NF, typename AF, bool ch = true>
   405   class SubDigraphBase : public DigraphAdaptorBase<DGR> {
   404   class SubDigraphBase : public DigraphAdaptorBase<DGR> {
       
   405     typedef DigraphAdaptorBase<DGR> Parent;
   406   public:
   406   public:
   407     typedef DGR Digraph;
   407     typedef DGR Digraph;
   408     typedef NF NodeFilterMap;
   408     typedef NF NodeFilterMap;
   409     typedef AF ArcFilterMap;
   409     typedef AF ArcFilterMap;
   410 
   410 
   411     typedef SubDigraphBase Adaptor;
   411     typedef SubDigraphBase Adaptor;
   412     typedef DigraphAdaptorBase<DGR> Parent;
       
   413   protected:
   412   protected:
   414     NF* _node_filter;
   413     NF* _node_filter;
   415     AF* _arc_filter;
   414     AF* _arc_filter;
   416     SubDigraphBase()
   415     SubDigraphBase()
   417       : Parent(), _node_filter(0), _arc_filter(0) { }
   416       : Parent(), _node_filter(0), _arc_filter(0) { }
   507 
   506 
   508     template <typename V>
   507     template <typename V>
   509     class NodeMap 
   508     class NodeMap 
   510       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 
   509       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 
   511 	      LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
   510 	      LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
       
   511       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
       
   512 	LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
       
   513 
   512     public:
   514     public:
   513       typedef V Value;
   515       typedef V Value;
   514       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
       
   515 	    LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
       
   516 
   516 
   517       NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
   517       NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
   518         : Parent(adaptor) {}
   518         : Parent(adaptor) {}
   519       NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)
   519       NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)
   520         : Parent(adaptor, value) {}
   520         : Parent(adaptor, value) {}
   533 
   533 
   534     template <typename V>
   534     template <typename V>
   535     class ArcMap 
   535     class ArcMap 
   536       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
   536       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
   537 	      LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
   537 	      LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
       
   538       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
       
   539         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
       
   540 
   538     public:
   541     public:
   539       typedef V Value;
   542       typedef V Value;
   540       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
       
   541         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
       
   542 
   543 
   543       ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
   544       ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
   544         : Parent(adaptor) {}
   545         : Parent(adaptor) {}
   545       ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)
   546       ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)
   546         : Parent(adaptor, value) {}
   547         : Parent(adaptor, value) {}
   560   };
   561   };
   561 
   562 
   562   template <typename DGR, typename NF, typename AF>
   563   template <typename DGR, typename NF, typename AF>
   563   class SubDigraphBase<DGR, NF, AF, false>
   564   class SubDigraphBase<DGR, NF, AF, false>
   564     : public DigraphAdaptorBase<DGR> {
   565     : public DigraphAdaptorBase<DGR> {
       
   566     typedef DigraphAdaptorBase<DGR> Parent;
   565   public:
   567   public:
   566     typedef DGR Digraph;
   568     typedef DGR Digraph;
   567     typedef NF NodeFilterMap;
   569     typedef NF NodeFilterMap;
   568     typedef AF ArcFilterMap;
   570     typedef AF ArcFilterMap;
   569 
   571 
   570     typedef SubDigraphBase Adaptor;
   572     typedef SubDigraphBase Adaptor;
   571     typedef DigraphAdaptorBase<Digraph> Parent;
       
   572   protected:
   573   protected:
   573     NF* _node_filter;
   574     NF* _node_filter;
   574     AF* _arc_filter;
   575     AF* _arc_filter;
   575     SubDigraphBase()
   576     SubDigraphBase()
   576       : Parent(), _node_filter(0), _arc_filter(0) { }
   577       : Parent(), _node_filter(0), _arc_filter(0) { }
   648 
   649 
   649     template <typename V>
   650     template <typename V>
   650     class NodeMap 
   651     class NodeMap 
   651       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
   652       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
   652           LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
   653           LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
       
   654       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 
       
   655         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
       
   656 
   653     public:
   657     public:
   654       typedef V Value;
   658       typedef V Value;
   655       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 
       
   656         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
       
   657 
   659 
   658       NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
   660       NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
   659         : Parent(adaptor) {}
   661         : Parent(adaptor) {}
   660       NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)
   662       NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)
   661         : Parent(adaptor, value) {}
   663         : Parent(adaptor, value) {}
   674 
   676 
   675     template <typename V>
   677     template <typename V>
   676     class ArcMap 
   678     class ArcMap 
   677       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
   679       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
   678           LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
   680           LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
       
   681       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
       
   682         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
       
   683 
   679     public:
   684     public:
   680       typedef V Value;
   685       typedef V Value;
   681       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
       
   682           LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
       
   683 
   686 
   684       ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
   687       ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
   685         : Parent(adaptor) {}
   688         : Parent(adaptor) {}
   686       ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)
   689       ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)
   687         : Parent(adaptor, value) {}
   690         : Parent(adaptor, value) {}
   861   }
   864   }
   862 
   865 
   863 
   866 
   864   template <typename GR, typename NF, typename EF, bool ch = true>
   867   template <typename GR, typename NF, typename EF, bool ch = true>
   865   class SubGraphBase : public GraphAdaptorBase<GR> {
   868   class SubGraphBase : public GraphAdaptorBase<GR> {
       
   869     typedef GraphAdaptorBase<GR> Parent;
   866   public:
   870   public:
   867     typedef GR Graph;
   871     typedef GR Graph;
   868     typedef NF NodeFilterMap;
   872     typedef NF NodeFilterMap;
   869     typedef EF EdgeFilterMap;
   873     typedef EF EdgeFilterMap;
   870 
   874 
   871     typedef SubGraphBase Adaptor;
   875     typedef SubGraphBase Adaptor;
   872     typedef GraphAdaptorBase<GR> Parent;
       
   873   protected:
   876   protected:
   874 
   877 
   875     NF* _node_filter;
   878     NF* _node_filter;
   876     EF* _edge_filter;
   879     EF* _edge_filter;
   877 
   880 
  1014 
  1017 
  1015     template <typename V>
  1018     template <typename V>
  1016     class NodeMap 
  1019     class NodeMap 
  1017       : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
  1020       : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
  1018           LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
  1021           LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
       
  1022       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
       
  1023         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
       
  1024 
  1019     public:
  1025     public:
  1020       typedef V Value;
  1026       typedef V Value;
  1021       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
       
  1022         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
       
  1023 
  1027 
  1024       NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
  1028       NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
  1025         : Parent(adaptor) {}
  1029         : Parent(adaptor) {}
  1026       NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
  1030       NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
  1027         : Parent(adaptor, value) {}
  1031         : Parent(adaptor, value) {}
  1040 
  1044 
  1041     template <typename V>
  1045     template <typename V>
  1042     class ArcMap 
  1046     class ArcMap 
  1043       : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
  1047       : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
  1044           LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
  1048           LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
       
  1049       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
       
  1050         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
       
  1051 
  1045     public:
  1052     public:
  1046       typedef V Value;
  1053       typedef V Value;
  1047       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
       
  1048         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
       
  1049 
  1054 
  1050       ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
  1055       ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
  1051         : Parent(adaptor) {}
  1056         : Parent(adaptor) {}
  1052       ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
  1057       ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
  1053         : Parent(adaptor, value) {}
  1058         : Parent(adaptor, value) {}
  1066 
  1071 
  1067     template <typename V>
  1072     template <typename V>
  1068     class EdgeMap 
  1073     class EdgeMap 
  1069       : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
  1074       : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
  1070         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
  1075         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
       
  1076       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
       
  1077         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
       
  1078 
  1071     public:
  1079     public:
  1072       typedef V Value;
  1080       typedef V Value;
  1073       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
       
  1074         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
       
  1075 
  1081 
  1076       EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
  1082       EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
  1077         : Parent(adaptor) {}
  1083         : Parent(adaptor) {}
  1078 
  1084 
  1079       EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
  1085       EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
  1094   };
  1100   };
  1095 
  1101 
  1096   template <typename GR, typename NF, typename EF>
  1102   template <typename GR, typename NF, typename EF>
  1097   class SubGraphBase<GR, NF, EF, false>
  1103   class SubGraphBase<GR, NF, EF, false>
  1098     : public GraphAdaptorBase<GR> {
  1104     : public GraphAdaptorBase<GR> {
       
  1105     typedef GraphAdaptorBase<GR> Parent;
  1099   public:
  1106   public:
  1100     typedef GR Graph;
  1107     typedef GR Graph;
  1101     typedef NF NodeFilterMap;
  1108     typedef NF NodeFilterMap;
  1102     typedef EF EdgeFilterMap;
  1109     typedef EF EdgeFilterMap;
  1103 
  1110 
  1104     typedef SubGraphBase Adaptor;
  1111     typedef SubGraphBase Adaptor;
  1105     typedef GraphAdaptorBase<GR> Parent;
       
  1106   protected:
  1112   protected:
  1107     NF* _node_filter;
  1113     NF* _node_filter;
  1108     EF* _edge_filter;
  1114     EF* _edge_filter;
  1109     SubGraphBase() 
  1115     SubGraphBase() 
  1110 	  : Parent(), _node_filter(0), _edge_filter(0) { }
  1116 	  : Parent(), _node_filter(0), _edge_filter(0) { }
  1209 
  1215 
  1210     template <typename V>
  1216     template <typename V>
  1211     class NodeMap 
  1217     class NodeMap 
  1212       : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
  1218       : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
  1213           LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
  1219           LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
       
  1220       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
       
  1221         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
       
  1222 
  1214     public:
  1223     public:
  1215       typedef V Value;
  1224       typedef V Value;
  1216       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
       
  1217         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
       
  1218 
  1225 
  1219       NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
  1226       NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
  1220         : Parent(adaptor) {}
  1227         : Parent(adaptor) {}
  1221       NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
  1228       NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
  1222         : Parent(adaptor, value) {}
  1229         : Parent(adaptor, value) {}
  1235 
  1242 
  1236     template <typename V>
  1243     template <typename V>
  1237     class ArcMap 
  1244     class ArcMap 
  1238       : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
  1245       : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
  1239           LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
  1246           LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
       
  1247       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
       
  1248         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
       
  1249 
  1240     public:
  1250     public:
  1241       typedef V Value;
  1251       typedef V Value;
  1242       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
       
  1243         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
       
  1244 
  1252 
  1245       ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
  1253       ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
  1246         : Parent(adaptor) {}
  1254         : Parent(adaptor) {}
  1247       ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
  1255       ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
  1248         : Parent(adaptor, value) {}
  1256         : Parent(adaptor, value) {}
  1261 
  1269 
  1262     template <typename V>
  1270     template <typename V>
  1263     class EdgeMap 
  1271     class EdgeMap 
  1264       : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
  1272       : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
  1265         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
  1273         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
       
  1274       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
       
  1275 	LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
       
  1276 
  1266     public:
  1277     public:
  1267       typedef V Value;
  1278       typedef V Value;
  1268       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
       
  1269 		  LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
       
  1270 
  1279 
  1271       EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
  1280       EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
  1272         : Parent(adaptor) {}
  1281         : Parent(adaptor) {}
  1273 
  1282 
  1274       EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
  1283       EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
  1483   class FilterNodes :
  1492   class FilterNodes :
  1484     public DigraphAdaptorExtender<
  1493     public DigraphAdaptorExtender<
  1485       SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
  1494       SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
  1486                      true> > {
  1495                      true> > {
  1487 #endif
  1496 #endif
  1488   public:
       
  1489 
       
  1490     typedef GR Digraph;
       
  1491     typedef NF NodeFilterMap;
       
  1492 
       
  1493     typedef DigraphAdaptorExtender<
  1497     typedef DigraphAdaptorExtender<
  1494       SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >, 
  1498       SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >, 
  1495                      true> > Parent;
  1499                      true> > Parent;
       
  1500 
       
  1501   public:
       
  1502 
       
  1503     typedef GR Digraph;
       
  1504     typedef NF NodeFilterMap;
  1496 
  1505 
  1497     typedef typename Parent::Node Node;
  1506     typedef typename Parent::Node Node;
  1498 
  1507 
  1499   protected:
  1508   protected:
  1500     ConstMap<typename Digraph::Arc, Const<bool, true> > const_true_map;
  1509     ConstMap<typename Digraph::Arc, Const<bool, true> > const_true_map;
  1546                     typename enable_if<UndirectedTagIndicator<GR> >::type> :
  1555                     typename enable_if<UndirectedTagIndicator<GR> >::type> :
  1547     public GraphAdaptorExtender<
  1556     public GraphAdaptorExtender<
  1548       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 
  1557       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 
  1549                    true> > {
  1558                    true> > {
  1550 
  1559 
  1551   public:
       
  1552     typedef GR Graph;
       
  1553     typedef NF NodeFilterMap;
       
  1554     typedef GraphAdaptorExtender<
  1560     typedef GraphAdaptorExtender<
  1555       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 
  1561       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 
  1556                    true> > Parent;
  1562                    true> > Parent;
  1557 
  1563 
       
  1564   public:
       
  1565 
       
  1566     typedef GR Graph;
       
  1567     typedef NF NodeFilterMap;
       
  1568 
  1558     typedef typename Parent::Node Node;
  1569     typedef typename Parent::Node Node;
       
  1570 
  1559   protected:
  1571   protected:
  1560     ConstMap<typename GR::Edge, Const<bool, true> > const_true_map;
  1572     ConstMap<typename GR::Edge, Const<bool, true> > const_true_map;
  1561 
  1573 
  1562     FilterNodes() : const_true_map() {}
  1574     FilterNodes() : const_true_map() {}
  1563 
  1575 
  1627   class FilterArcs :
  1639   class FilterArcs :
  1628     public DigraphAdaptorExtender<
  1640     public DigraphAdaptorExtender<
  1629       SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
  1641       SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
  1630                      AF, false> > {
  1642                      AF, false> > {
  1631 #endif
  1643 #endif
  1632   public:
  1644     typedef DigraphAdaptorExtender<
       
  1645       SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >, 
       
  1646                      AF, false> > Parent;
       
  1647 
       
  1648   public:
       
  1649 
  1633     /// The type of the adapted digraph.
  1650     /// The type of the adapted digraph.
  1634     typedef DGR Digraph;
  1651     typedef DGR Digraph;
  1635     /// The type of the arc filter map.
  1652     /// The type of the arc filter map.
  1636     typedef AF ArcFilterMap;
  1653     typedef AF ArcFilterMap;
  1637 
       
  1638     typedef DigraphAdaptorExtender<
       
  1639       SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >, 
       
  1640                      AF, false> > Parent;
       
  1641 
  1654 
  1642     typedef typename Parent::Arc Arc;
  1655     typedef typename Parent::Arc Arc;
  1643 
  1656 
  1644   protected:
  1657   protected:
  1645     ConstMap<typename DGR::Node, Const<bool, true> > const_true_map;
  1658     ConstMap<typename DGR::Node, Const<bool, true> > const_true_map;
  1736   class FilterEdges :
  1749   class FilterEdges :
  1737     public GraphAdaptorExtender<
  1750     public GraphAdaptorExtender<
  1738       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >, 
  1751       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >, 
  1739                    EF, false> > {
  1752                    EF, false> > {
  1740 #endif
  1753 #endif
  1741   public:
  1754     typedef GraphAdaptorExtender<
       
  1755       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >, 
       
  1756                    EF, false> > Parent;
       
  1757 
       
  1758   public:
       
  1759 
  1742     /// The type of the adapted graph.
  1760     /// The type of the adapted graph.
  1743     typedef GR Graph;
  1761     typedef GR Graph;
  1744     /// The type of the edge filter map.
  1762     /// The type of the edge filter map.
  1745     typedef EF EdgeFilterMap;
  1763     typedef EF EdgeFilterMap;
  1746 
       
  1747     typedef GraphAdaptorExtender<
       
  1748       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >, 
       
  1749                    EF, false> > Parent;
       
  1750 
  1764 
  1751     typedef typename Parent::Edge Edge;
  1765     typedef typename Parent::Edge Edge;
  1752 
  1766 
  1753   protected:
  1767   protected:
  1754     ConstMap<typename GR::Node, Const<bool, true> > const_true_map;
  1768     ConstMap<typename GR::Node, Const<bool, true> > const_true_map;
  2109 
  2123 
  2110   public:
  2124   public:
  2111 
  2125 
  2112     template <typename V>
  2126     template <typename V>
  2113     class NodeMap : public DGR::template NodeMap<V> {
  2127     class NodeMap : public DGR::template NodeMap<V> {
       
  2128       typedef typename DGR::template NodeMap<V> Parent;
       
  2129 
  2114     public:
  2130     public:
  2115 
       
  2116       typedef V Value;
  2131       typedef V Value;
  2117       typedef typename DGR::template NodeMap<Value> Parent;
       
  2118 
  2132 
  2119       explicit NodeMap(const UndirectorBase<DGR>& adaptor)
  2133       explicit NodeMap(const UndirectorBase<DGR>& adaptor)
  2120         : Parent(*adaptor._digraph) {}
  2134         : Parent(*adaptor._digraph) {}
  2121 
  2135 
  2122       NodeMap(const UndirectorBase<DGR>& adaptor, const V& value)
  2136       NodeMap(const UndirectorBase<DGR>& adaptor, const V& value)
  2135 
  2149 
  2136     };
  2150     };
  2137 
  2151 
  2138     template <typename V>
  2152     template <typename V>
  2139     class ArcMap
  2153     class ArcMap
  2140       : public SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> >
  2154       : public SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > {
  2141     {
  2155       typedef SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > Parent;
       
  2156 
  2142     public:
  2157     public:
  2143       typedef V Value;
  2158       typedef V Value;
  2144       typedef SubMapExtender<Adaptor, ArcMapBase<V> > Parent;
       
  2145 
  2159 
  2146       explicit ArcMap(const UndirectorBase<DGR>& adaptor)
  2160       explicit ArcMap(const UndirectorBase<DGR>& adaptor)
  2147         : Parent(adaptor) {}
  2161         : Parent(adaptor) {}
  2148 
  2162 
  2149       ArcMap(const UndirectorBase<DGR>& adaptor, const V& value)
  2163       ArcMap(const UndirectorBase<DGR>& adaptor, const V& value)
  2161       }
  2175       }
  2162     };
  2176     };
  2163 
  2177 
  2164     template <typename V>
  2178     template <typename V>
  2165     class EdgeMap : public Digraph::template ArcMap<V> {
  2179     class EdgeMap : public Digraph::template ArcMap<V> {
       
  2180       typedef typename Digraph::template ArcMap<V> Parent;
       
  2181 
  2166     public:
  2182     public:
  2167 
       
  2168       typedef V Value;
  2183       typedef V Value;
  2169       typedef typename Digraph::template ArcMap<V> Parent;
       
  2170 
  2184 
  2171       explicit EdgeMap(const UndirectorBase<DGR>& adaptor)
  2185       explicit EdgeMap(const UndirectorBase<DGR>& adaptor)
  2172         : Parent(*adaptor._digraph) {}
  2186         : Parent(*adaptor._digraph) {}
  2173 
  2187 
  2174       EdgeMap(const UndirectorBase<DGR>& adaptor, const V& value)
  2188       EdgeMap(const UndirectorBase<DGR>& adaptor, const V& value)
  2236   class Undirector {
  2250   class Undirector {
  2237 #else
  2251 #else
  2238   class Undirector :
  2252   class Undirector :
  2239     public GraphAdaptorExtender<UndirectorBase<DGR> > {
  2253     public GraphAdaptorExtender<UndirectorBase<DGR> > {
  2240 #endif
  2254 #endif
       
  2255     typedef GraphAdaptorExtender<UndirectorBase<DGR> > Parent;
  2241   public:
  2256   public:
  2242     /// The type of the adapted digraph.
  2257     /// The type of the adapted digraph.
  2243     typedef DGR Digraph;
  2258     typedef DGR Digraph;
  2244     typedef GraphAdaptorExtender<UndirectorBase<DGR> > Parent;
       
  2245   protected:
  2259   protected:
  2246     Undirector() { }
  2260     Undirector() { }
  2247   public:
  2261   public:
  2248 
  2262 
  2249     /// \brief Constructor
  2263     /// \brief Constructor
  2447     typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier;
  2461     typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier;
  2448     ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
  2462     ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
  2449 
  2463 
  2450     template <typename V>
  2464     template <typename V>
  2451     class NodeMap : public GR::template NodeMap<V> {
  2465     class NodeMap : public GR::template NodeMap<V> {
       
  2466       typedef typename GR::template NodeMap<V> Parent;
       
  2467 
  2452     public:
  2468     public:
  2453 
       
  2454       typedef typename GR::template NodeMap<V> Parent;
       
  2455 
  2469 
  2456       explicit NodeMap(const OrienterBase<GR, DM>& adapter)
  2470       explicit NodeMap(const OrienterBase<GR, DM>& adapter)
  2457         : Parent(*adapter._graph) {}
  2471         : Parent(*adapter._graph) {}
  2458 
  2472 
  2459       NodeMap(const OrienterBase<GR, DM>& adapter, const V& value)
  2473       NodeMap(const OrienterBase<GR, DM>& adapter, const V& value)
  2472 
  2486 
  2473     };
  2487     };
  2474 
  2488 
  2475     template <typename V>
  2489     template <typename V>
  2476     class ArcMap : public GR::template EdgeMap<V> {
  2490     class ArcMap : public GR::template EdgeMap<V> {
       
  2491       typedef typename Graph::template EdgeMap<V> Parent;
       
  2492 
  2477     public:
  2493     public:
  2478 
       
  2479       typedef typename Graph::template EdgeMap<V> Parent;
       
  2480 
  2494 
  2481       explicit ArcMap(const OrienterBase<GR, DM>& adapter)
  2495       explicit ArcMap(const OrienterBase<GR, DM>& adapter)
  2482         : Parent(*adapter._graph) { }
  2496         : Parent(*adapter._graph) { }
  2483 
  2497 
  2484       ArcMap(const OrienterBase<GR, DM>& adapter, const V& value)
  2498       ArcMap(const OrienterBase<GR, DM>& adapter, const V& value)
  2544   template<typename GR,
  2558   template<typename GR,
  2545            typename DM = typename GR::template EdgeMap<bool> >
  2559            typename DM = typename GR::template EdgeMap<bool> >
  2546   class Orienter :
  2560   class Orienter :
  2547     public DigraphAdaptorExtender<OrienterBase<GR, DM> > {
  2561     public DigraphAdaptorExtender<OrienterBase<GR, DM> > {
  2548 #endif
  2562 #endif
       
  2563     typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;
  2549   public:
  2564   public:
  2550 
  2565 
  2551     /// The type of the adapted graph.
  2566     /// The type of the adapted graph.
  2552     typedef GR Graph;
  2567     typedef GR Graph;
  2553     /// The type of the direction edge map.
  2568     /// The type of the direction edge map.
  2554     typedef DM DirectionMap;
  2569     typedef DM DirectionMap;
  2555 
  2570 
  2556     typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;
       
  2557     typedef typename Parent::Arc Arc;
  2571     typedef typename Parent::Arc Arc;
       
  2572 
  2558   protected:
  2573   protected:
  2559     Orienter() { }
  2574     Orienter() { }
       
  2575 
  2560   public:
  2576   public:
  2561 
  2577 
  2562     /// \brief Constructor
  2578     /// \brief Constructor
  2563     ///
  2579     ///
  2564     /// Constructor of the adaptor.
  2580     /// Constructor of the adaptor.
  2864   }
  2880   }
  2865 
  2881 
  2866 
  2882 
  2867   template <typename DGR>
  2883   template <typename DGR>
  2868   class SplitNodesBase {
  2884   class SplitNodesBase {
       
  2885     typedef DigraphAdaptorBase<const DGR> Parent;
       
  2886 
  2869   public:
  2887   public:
  2870 
  2888 
  2871     typedef DGR Digraph;
  2889     typedef DGR Digraph;
  2872     typedef DigraphAdaptorBase<const DGR> Parent;
       
  2873     typedef SplitNodesBase Adaptor;
  2890     typedef SplitNodesBase Adaptor;
  2874 
  2891 
  2875     typedef typename DGR::Node DigraphNode;
  2892     typedef typename DGR::Node DigraphNode;
  2876     typedef typename DGR::Arc DigraphArc;
  2893     typedef typename DGR::Arc DigraphArc;
  2877 
  2894 
  3226 
  3243 
  3227   public:
  3244   public:
  3228 
  3245 
  3229     template <typename V>
  3246     template <typename V>
  3230     class NodeMap
  3247     class NodeMap
  3231       : public SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> >
  3248       : public SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > {
  3232     {
  3249       typedef SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > Parent;
       
  3250 
  3233     public:
  3251     public:
  3234       typedef V Value;
  3252       typedef V Value;
  3235       typedef SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<Value> > Parent;
       
  3236 
  3253 
  3237       NodeMap(const SplitNodesBase<DGR>& adaptor)
  3254       NodeMap(const SplitNodesBase<DGR>& adaptor)
  3238         : Parent(adaptor) {}
  3255         : Parent(adaptor) {}
  3239 
  3256 
  3240       NodeMap(const SplitNodesBase<DGR>& adaptor, const V& value)
  3257       NodeMap(const SplitNodesBase<DGR>& adaptor, const V& value)
  3252       }
  3269       }
  3253     };
  3270     };
  3254 
  3271 
  3255     template <typename V>
  3272     template <typename V>
  3256     class ArcMap
  3273     class ArcMap
  3257       : public SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> >
  3274       : public SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > {
  3258     {
  3275       typedef SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > Parent;
       
  3276 
  3259     public:
  3277     public:
  3260       typedef V Value;
  3278       typedef V Value;
  3261       typedef SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<Value> > Parent;
       
  3262 
  3279 
  3263       ArcMap(const SplitNodesBase<DGR>& adaptor)
  3280       ArcMap(const SplitNodesBase<DGR>& adaptor)
  3264         : Parent(adaptor) {}
  3281         : Parent(adaptor) {}
  3265 
  3282 
  3266       ArcMap(const SplitNodesBase<DGR>& adaptor, const V& value)
  3283       ArcMap(const SplitNodesBase<DGR>& adaptor, const V& value)
  3322   class SplitNodes {
  3339   class SplitNodes {
  3323 #else
  3340 #else
  3324   class SplitNodes
  3341   class SplitNodes
  3325     : public DigraphAdaptorExtender<SplitNodesBase<const DGR> > {
  3342     : public DigraphAdaptorExtender<SplitNodesBase<const DGR> > {
  3326 #endif
  3343 #endif
       
  3344     typedef DigraphAdaptorExtender<SplitNodesBase<const DGR> > Parent;
       
  3345 
  3327   public:
  3346   public:
  3328     typedef DGR Digraph;
  3347     typedef DGR Digraph;
  3329     typedef DigraphAdaptorExtender<SplitNodesBase<const DGR> > Parent;
       
  3330 
  3348 
  3331     typedef typename DGR::Node DigraphNode;
  3349     typedef typename DGR::Node DigraphNode;
  3332     typedef typename DGR::Arc DigraphArc;
  3350     typedef typename DGR::Arc DigraphArc;
  3333 
  3351 
  3334     typedef typename Parent::Node Node;
  3352     typedef typename Parent::Node Node;