1.1 --- a/lemon/adaptors.h Fri Aug 09 11:07:27 2013 +0200
1.2 +++ b/lemon/adaptors.h Sun Aug 11 15:28:12 2013 +0200
1.3 @@ -2,7 +2,7 @@
1.4 *
1.5 * This file is a part of LEMON, a generic C++ optimization library.
1.6 *
1.7 - * Copyright (C) 2003-2009
1.8 + * Copyright (C) 2003-2010
1.9 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 *
1.12 @@ -360,6 +360,9 @@
1.13 /// by adding or removing nodes or arcs, unless the \c GR template
1.14 /// parameter is set to be \c const.
1.15 ///
1.16 + /// This class provides item counting in the same time as the adapted
1.17 + /// digraph structure.
1.18 + ///
1.19 /// \tparam DGR The type of the adapted digraph.
1.20 /// It must conform to the \ref concepts::Digraph "Digraph" concept.
1.21 /// It can also be specified to be \c const.
1.22 @@ -418,7 +421,7 @@
1.23 void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
1.24 Parent::initialize(digraph);
1.25 _node_filter = &node_filter;
1.26 - _arc_filter = &arc_filter;
1.27 + _arc_filter = &arc_filter;
1.28 }
1.29
1.30 public:
1.31 @@ -505,11 +508,11 @@
1.32 public:
1.33
1.34 template <typename V>
1.35 - class NodeMap
1.36 - : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
1.37 - LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
1.38 + class NodeMap
1.39 + : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
1.40 + LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
1.41 typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
1.42 - LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
1.43 + LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
1.44
1.45 public:
1.46 typedef V Value;
1.47 @@ -532,9 +535,9 @@
1.48 };
1.49
1.50 template <typename V>
1.51 - class ArcMap
1.52 + class ArcMap
1.53 : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
1.54 - LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
1.55 + LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
1.56 typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
1.57 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
1.58
1.59 @@ -579,7 +582,7 @@
1.60 void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
1.61 Parent::initialize(digraph);
1.62 _node_filter = &node_filter;
1.63 - _arc_filter = &arc_filter;
1.64 + _arc_filter = &arc_filter;
1.65 }
1.66
1.67 public:
1.68 @@ -648,10 +651,10 @@
1.69 }
1.70
1.71 template <typename V>
1.72 - class NodeMap
1.73 + class NodeMap
1.74 : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
1.75 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
1.76 - typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
1.77 + typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
1.78 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
1.79
1.80 public:
1.81 @@ -675,7 +678,7 @@
1.82 };
1.83
1.84 template <typename V>
1.85 - class ArcMap
1.86 + class ArcMap
1.87 : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
1.88 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
1.89 typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
1.90 @@ -719,6 +722,8 @@
1.91 /// by adding or removing nodes or arcs, unless the \c GR template
1.92 /// parameter is set to be \c const.
1.93 ///
1.94 + /// This class provides only linear time counting for nodes and arcs.
1.95 + ///
1.96 /// \tparam DGR The type of the adapted digraph.
1.97 /// It must conform to the \ref concepts::Digraph "Digraph" concept.
1.98 /// It can also be specified to be \c const.
1.99 @@ -1016,10 +1021,10 @@
1.100 }
1.101
1.102 template <typename V>
1.103 - class NodeMap
1.104 + class NodeMap
1.105 : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
1.106 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
1.107 - typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
1.108 + typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
1.109 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
1.110
1.111 public:
1.112 @@ -1043,10 +1048,10 @@
1.113 };
1.114
1.115 template <typename V>
1.116 - class ArcMap
1.117 + class ArcMap
1.118 : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
1.119 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
1.120 - typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
1.121 + typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
1.122 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
1.123
1.124 public:
1.125 @@ -1070,10 +1075,10 @@
1.126 };
1.127
1.128 template <typename V>
1.129 - class EdgeMap
1.130 + class EdgeMap
1.131 : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
1.132 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
1.133 - typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
1.134 + typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
1.135 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
1.136
1.137 public:
1.138 @@ -1112,8 +1117,8 @@
1.139 protected:
1.140 NF* _node_filter;
1.141 EF* _edge_filter;
1.142 - SubGraphBase()
1.143 - : Parent(), _node_filter(0), _edge_filter(0) { }
1.144 + SubGraphBase()
1.145 + : Parent(), _node_filter(0), _edge_filter(0) { }
1.146
1.147 void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
1.148 Parent::initialize(graph);
1.149 @@ -1214,10 +1219,10 @@
1.150 }
1.151
1.152 template <typename V>
1.153 - class NodeMap
1.154 + class NodeMap
1.155 : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
1.156 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
1.157 - typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
1.158 + typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
1.159 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
1.160
1.161 public:
1.162 @@ -1241,10 +1246,10 @@
1.163 };
1.164
1.165 template <typename V>
1.166 - class ArcMap
1.167 + class ArcMap
1.168 : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
1.169 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
1.170 - typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
1.171 + typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
1.172 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
1.173
1.174 public:
1.175 @@ -1268,11 +1273,11 @@
1.176 };
1.177
1.178 template <typename V>
1.179 - class EdgeMap
1.180 + class EdgeMap
1.181 : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
1.182 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
1.183 - typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
1.184 - LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
1.185 + typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
1.186 + LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
1.187
1.188 public:
1.189 typedef V Value;
1.190 @@ -1314,6 +1319,8 @@
1.191 /// by adding or removing nodes or edges, unless the \c GR template
1.192 /// parameter is set to be \c const.
1.193 ///
1.194 + /// This class provides only linear time counting for nodes, edges and arcs.
1.195 + ///
1.196 /// \tparam GR The type of the adapted graph.
1.197 /// It must conform to the \ref concepts::Graph "Graph" concept.
1.198 /// It can also be specified to be \c const.
1.199 @@ -1471,6 +1478,8 @@
1.200 /// by adding or removing nodes or arcs/edges, unless the \c GR template
1.201 /// parameter is set to be \c const.
1.202 ///
1.203 + /// This class provides only linear time item counting.
1.204 + ///
1.205 /// \tparam GR The type of the adapted digraph or graph.
1.206 /// It must conform to the \ref concepts::Digraph "Digraph" concept
1.207 /// or the \ref concepts::Graph "Graph" concept.
1.208 @@ -1495,7 +1504,7 @@
1.209 true> > {
1.210 #endif
1.211 typedef DigraphAdaptorExtender<
1.212 - SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
1.213 + SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
1.214 true> > Parent;
1.215
1.216 public:
1.217 @@ -1516,7 +1525,7 @@
1.218 ///
1.219 /// Creates a subgraph for the given digraph or graph with the
1.220 /// given node filter map.
1.221 - FilterNodes(GR& graph, NF& node_filter)
1.222 + FilterNodes(GR& graph, NF& node_filter)
1.223 : Parent(), const_true_map()
1.224 {
1.225 Parent::initialize(graph, node_filter, const_true_map);
1.226 @@ -1554,11 +1563,11 @@
1.227 class FilterNodes<GR, NF,
1.228 typename enable_if<UndirectedTagIndicator<GR> >::type> :
1.229 public GraphAdaptorExtender<
1.230 - SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
1.231 + SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
1.232 true> > {
1.233
1.234 typedef GraphAdaptorExtender<
1.235 - SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
1.236 + SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
1.237 true> > Parent;
1.238
1.239 public:
1.240 @@ -1619,6 +1628,8 @@
1.241 /// by adding or removing nodes or arcs, unless the \c GR template
1.242 /// parameter is set to be \c const.
1.243 ///
1.244 + /// This class provides only linear time counting for nodes and arcs.
1.245 + ///
1.246 /// \tparam DGR The type of the adapted digraph.
1.247 /// It must conform to the \ref concepts::Digraph "Digraph" concept.
1.248 /// It can also be specified to be \c const.
1.249 @@ -1642,7 +1653,7 @@
1.250 AF, false> > {
1.251 #endif
1.252 typedef DigraphAdaptorExtender<
1.253 - SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
1.254 + SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
1.255 AF, false> > Parent;
1.256
1.257 public:
1.258 @@ -1729,6 +1740,8 @@
1.259 /// by adding or removing nodes or edges, unless the \c GR template
1.260 /// parameter is set to be \c const.
1.261 ///
1.262 + /// This class provides only linear time counting for nodes, edges and arcs.
1.263 + ///
1.264 /// \tparam GR The type of the adapted graph.
1.265 /// It must conform to the \ref concepts::Graph "Graph" concept.
1.266 /// It can also be specified to be \c const.
1.267 @@ -1748,11 +1761,11 @@
1.268 typename EF = typename GR::template EdgeMap<bool> >
1.269 class FilterEdges :
1.270 public GraphAdaptorExtender<
1.271 - SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >,
1.272 + SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >,
1.273 EF, false> > {
1.274 #endif
1.275 typedef GraphAdaptorExtender<
1.276 - SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,
1.277 + SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,
1.278 EF, false> > Parent;
1.279
1.280 public:
1.281 @@ -1777,7 +1790,7 @@
1.282 ///
1.283 /// Creates a subgraph for the given graph with the given edge
1.284 /// filter map.
1.285 - FilterEdges(GR& graph, EF& edge_filter)
1.286 + FilterEdges(GR& graph, EF& edge_filter)
1.287 : Parent(), const_true_map() {
1.288 Parent::initialize(graph, const_true_map, edge_filter);
1.289 }
1.290 @@ -1845,7 +1858,7 @@
1.291 Edge _edge;
1.292 bool _forward;
1.293
1.294 - Arc(const Edge& edge, bool forward)
1.295 + Arc(const Edge& edge, bool forward)
1.296 : _edge(edge), _forward(forward) {}
1.297
1.298 public:
1.299 @@ -2085,7 +2098,7 @@
1.300 _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
1.301
1.302 ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value)
1.303 - : _forward(*adaptor._digraph, value),
1.304 + : _forward(*adaptor._digraph, value),
1.305 _backward(*adaptor._digraph, value) {}
1.306
1.307 void set(const Arc& a, const V& value) {
1.308 @@ -2203,7 +2216,7 @@
1.309
1.310 typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;
1.311 EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
1.312 -
1.313 +
1.314 typedef EdgeNotifier ArcNotifier;
1.315 ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }
1.316
1.317 @@ -2232,6 +2245,9 @@
1.318 /// by adding or removing nodes or edges, unless the \c GR template
1.319 /// parameter is set to be \c const.
1.320 ///
1.321 + /// This class provides item counting in the same time as the adapted
1.322 + /// digraph structure.
1.323 + ///
1.324 /// \tparam DGR The type of the adapted digraph.
1.325 /// It must conform to the \ref concepts::Digraph "Digraph" concept.
1.326 /// It can also be specified to be \c const.
1.327 @@ -2535,6 +2551,9 @@
1.328 /// by adding or removing nodes or arcs, unless the \c GR template
1.329 /// parameter is set to be \c const.
1.330 ///
1.331 + /// This class provides item counting in the same time as the adapted
1.332 + /// graph structure.
1.333 + ///
1.334 /// \tparam GR The type of the adapted graph.
1.335 /// It must conform to the \ref concepts::Graph "Graph" concept.
1.336 /// It can also be specified to be \c const.
1.337 @@ -2678,6 +2697,8 @@
1.338 /// arcs).
1.339 /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
1.340 ///
1.341 + /// This class provides only linear time counting for nodes and arcs.
1.342 + ///
1.343 /// \tparam DGR The type of the adapted digraph.
1.344 /// It must conform to the \ref concepts::Digraph "Digraph" concept.
1.345 /// It is implicitly \c const.
1.346 @@ -2707,7 +2728,7 @@
1.347 typename CM = typename DGR::template ArcMap<int>,
1.348 typename FM = CM,
1.349 typename TL = Tolerance<typename CM::Value> >
1.350 - class ResidualDigraph
1.351 + class ResidualDigraph
1.352 : public SubDigraph<
1.353 Undirector<const DGR>,
1.354 ConstMap<typename DGR::Node, Const<bool, true> >,
1.355 @@ -2764,7 +2785,7 @@
1.356 /// digraph, the capacity map, the flow map, and a tolerance object.
1.357 ResidualDigraph(const DGR& digraph, const CM& capacity,
1.358 FM& flow, const TL& tolerance = Tolerance())
1.359 - : Parent(), _capacity(&capacity), _flow(&flow),
1.360 + : Parent(), _capacity(&capacity), _flow(&flow),
1.361 _graph(digraph), _node_filter(),
1.362 _forward_filter(capacity, flow, tolerance),
1.363 _backward_filter(capacity, flow, tolerance),
1.364 @@ -2846,7 +2867,7 @@
1.365 typedef typename CapacityMap::Value Value;
1.366
1.367 /// Constructor
1.368 - ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor)
1.369 + ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor)
1.370 : _adaptor(&adaptor) {}
1.371
1.372 /// Returns the value associated with the given residual arc
1.373 @@ -3325,6 +3346,9 @@
1.374 /// costs/capacities of the original digraph to the \e bind \e arcs
1.375 /// in the adaptor.
1.376 ///
1.377 + /// This class provides item counting in the same time as the adapted
1.378 + /// digraph structure.
1.379 + ///
1.380 /// \tparam DGR The type of the adapted digraph.
1.381 /// It must conform to the \ref concepts::Digraph "Digraph" concept.
1.382 /// It is implicitly \c const.
1.383 @@ -3423,7 +3447,7 @@
1.384 /// This map adaptor class adapts two node maps of the original digraph
1.385 /// to get a node map of the split digraph.
1.386 /// Its value type is inherited from the first node map type (\c IN).
1.387 - /// \tparam IN The type of the node map for the in-nodes.
1.388 + /// \tparam IN The type of the node map for the in-nodes.
1.389 /// \tparam OUT The type of the node map for the out-nodes.
1.390 template <typename IN, typename OUT>
1.391 class CombinedNodeMap {