1.1 --- a/lemon/Makefile.am Mon Apr 03 16:05:26 2006 +0000
1.2 +++ b/lemon/Makefile.am Mon Apr 03 16:34:23 2006 +0000
1.3 @@ -35,6 +35,7 @@
1.4 dimacs.h \
1.5 dag_shortest_path.h \
1.6 edge_set.h \
1.7 + edmonds_karp.h \
1.8 error.h \
1.9 eps.h \
1.10 fib_heap.h \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/edmonds_karp.h Mon Apr 03 16:34:23 2006 +0000
2.3 @@ -0,0 +1,390 @@
2.4 +/* -*- C++ -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library
2.7 + *
2.8 + * Copyright (C) 2003-2006
2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.11 + *
2.12 + * Permission to use, modify and distribute this software is granted
2.13 + * provided that this copyright notice appears in all copies. For
2.14 + * precise terms see the accompanying LICENSE file.
2.15 + *
2.16 + * This software is provided "AS IS" with no warranty of any kind,
2.17 + * express or implied, and with no claim as to its suitability for any
2.18 + * purpose.
2.19 + *
2.20 + */
2.21 +
2.22 +#ifndef LEMON_EDMONDS_KARP_H
2.23 +#define LEMON_EDMONDS_KARP_H
2.24 +
2.25 +/// \file
2.26 +/// \ingroup flowalgs
2.27 +/// \brief Implementation of the Edmonds-Karp algorithm.
2.28 +
2.29 +#include <lemon/graph_adaptor.h>
2.30 +#include <lemon/tolerance.h>
2.31 +#include <lemon/bfs.h>
2.32 +
2.33 +namespace lemon {
2.34 +
2.35 + /// \ingroup flowalgs
2.36 + /// \brief Edmonds-Karp algorithms class.
2.37 + ///
2.38 + /// This class provides an implementation of the \e Edmonds-Karp \e
2.39 + /// algorithm producing a flow of maximum value in a directed
2.40 + /// graph. The Edmonds-Karp algorithm is slower than the Preflow algorithm
2.41 + /// but it has an advantage of the step-by-step execution control with
2.42 + /// feasible flow solutions. The \e source node, the \e target node, the \e
2.43 + /// capacity of the edges and the \e starting \e flow value of the
2.44 + /// edges should be passed to the algorithm through the
2.45 + /// constructor. It is possible to change these quantities using the
2.46 + /// functions \ref source, \ref target, \ref capacityMap and \ref
2.47 + /// flowMap.
2.48 + ///
2.49 + /// The time complexity of the algorithm is O(n * e^2) in worst case.
2.50 + /// Always try the preflow algorithm instead of this if you does not
2.51 + /// have some additional reason than to compute the optimal flow which
2.52 + /// has O(n^3) time complexity.
2.53 + ///
2.54 + /// \param _Graph The directed graph type the algorithm runs on.
2.55 + /// \param _Number The number type of the capacities and the flow values.
2.56 + /// \param _CapacityMap The capacity map type.
2.57 + /// \param _FlowMap The flow map type.
2.58 + /// \param _Tolerance The tolerance class to handle computation problems.
2.59 + ///
2.60 + /// \author Balazs Dezso
2.61 + template <typename _Graph, typename _Number,
2.62 + typename _CapacityMap = typename _Graph::template EdgeMap<_Number>,
2.63 + typename _FlowMap = typename _Graph::template EdgeMap<_Number>,
2.64 + typename _Tolerance = Tolerance<_Number> >
2.65 + class EdmondsKarp {
2.66 + public:
2.67 +
2.68 + /// \brief \ref Exception for the case when the source equals the target.
2.69 + ///
2.70 + /// \ref Exception for the case when the source equals the target.
2.71 + ///
2.72 + class InvalidArgument : public lemon::LogicError {
2.73 + public:
2.74 + virtual const char* exceptionName() const {
2.75 + return "lemon::EdmondsKarp::InvalidArgument";
2.76 + }
2.77 + };
2.78 +
2.79 +
2.80 + /// \brief The graph type the algorithm runs on.
2.81 + typedef _Graph Graph;
2.82 + /// \brief The value type of the algorithms.
2.83 + typedef _Number Number;
2.84 + /// \brief The capacity map on the edges.
2.85 + typedef _CapacityMap CapacityMap;
2.86 + /// \brief The flow map on the edges.
2.87 + typedef _FlowMap FlowMap;
2.88 + /// \brief The tolerance used by the algorithm.
2.89 + typedef _Tolerance Tolerance;
2.90 +
2.91 + typedef ResGraphAdaptor<Graph, Number, CapacityMap,
2.92 + FlowMap, Tolerance> ResGraph;
2.93 +
2.94 + private:
2.95 +
2.96 + typedef typename Graph::Node Node;
2.97 + typedef typename Graph::Edge Edge;
2.98 +
2.99 + typedef typename Graph::NodeIt NodeIt;
2.100 + typedef typename Graph::EdgeIt EdgeIt;
2.101 + typedef typename Graph::InEdgeIt InEdgeIt;
2.102 + typedef typename Graph::OutEdgeIt OutEdgeIt;
2.103 +
2.104 + public:
2.105 +
2.106 + /// \brief The constructor of the class.
2.107 + ///
2.108 + /// The constructor of the class.
2.109 + /// \param _graph The directed graph the algorithm runs on.
2.110 + /// \param _source The source node.
2.111 + /// \param _target The target node.
2.112 + /// \param _capacity The capacity of the edges.
2.113 + /// \param _flow The flow of the edges.
2.114 + /// \param _tolerance Tolerance class.
2.115 + /// Except the graph, all of these parameters can be reset by
2.116 + /// calling \ref source, \ref target, \ref capacityMap and \ref
2.117 + /// flowMap, resp.
2.118 + EdmondsKarp(const Graph& graph, Node source, Node target,
2.119 + const CapacityMap& capacity, FlowMap& flow,
2.120 + const Tolerance& tolerance = Tolerance())
2.121 + : _graph(graph), _capacity(capacity), _flow(flow),
2.122 + _tolerance(tolerance), _resgraph(graph, capacity, flow, tolerance),
2.123 + _source(source), _target(target)
2.124 + {
2.125 + if (_source == _target) {
2.126 + throw InvalidArgument();
2.127 + }
2.128 + }
2.129 +
2.130 + /// \brief Initializes the algorithm
2.131 + ///
2.132 + /// It sets the flow to empty flow.
2.133 + void init() {
2.134 + for (EdgeIt it(_graph); it != INVALID; ++it) {
2.135 + _flow.set(it, 0);
2.136 + }
2.137 + _value = 0;
2.138 + }
2.139 +
2.140 + /// \brief Initializes the algorithm
2.141 + ///
2.142 + /// If the flow map initially flow this let the flow map
2.143 + /// unchanged but the flow value will be set by the flow
2.144 + /// on the outedges from the source.
2.145 + void flowInit() {
2.146 + _value = 0;
2.147 + for (OutEdgeIt jt(_graph, _source); jt != INVALID; ++jt) {
2.148 + _value += _flow[jt];
2.149 + }
2.150 + for (InEdgeIt jt(_graph, _source); jt != INVALID; ++jt) {
2.151 + _value -= _flow[jt];
2.152 + }
2.153 + }
2.154 +
2.155 + /// \brief Initializes the algorithm
2.156 + ///
2.157 + /// If the flow map initially flow this let the flow map
2.158 + /// unchanged but the flow value will be set by the flow
2.159 + /// on the outedges from the source. It also checks that
2.160 + /// the flow map really contains a flow.
2.161 + /// \return %True when the flow map really a flow.
2.162 + bool checkedFlowInit() {
2.163 + _value = 0;
2.164 + for (OutEdgeIt jt(_graph, _source); jt != INVALID; ++jt) {
2.165 + _value += _flow[jt];
2.166 + }
2.167 + for (InEdgeIt jt(_graph, _source); jt != INVALID; ++jt) {
2.168 + _value -= _flow[jt];
2.169 + }
2.170 + for (NodeIt it(_graph); it != INVALID; ++it) {
2.171 + if (it == _source || it == _target) continue;
2.172 + Number outFlow = 0;
2.173 + for (OutEdgeIt jt(_graph, it); jt != INVALID; ++jt) {
2.174 + outFlow += _flow[jt];
2.175 + }
2.176 + Number inFlow = 0;
2.177 + for (InEdgeIt jt(_graph, it); jt != INVALID; ++jt) {
2.178 + inFlow += _flow[jt];
2.179 + }
2.180 + if (_tolerance.different(outFlow, inFlow)) {
2.181 + return false;
2.182 + }
2.183 + }
2.184 + for (EdgeIt it(_graph); it != INVALID; ++it) {
2.185 + if (_tolerance.less(_flow[it], 0)) return false;
2.186 + if (_tolerance.less(_capacity[it], _flow[it])) return false;
2.187 + }
2.188 + return true;
2.189 + }
2.190 +
2.191 + /// \brief Augment the solution on an edge shortest path.
2.192 + ///
2.193 + /// Augment the solution on an edge shortest path. It search an
2.194 + /// edge shortest path between the source and the target
2.195 + /// in the residual graph with the bfs algoritm.
2.196 + /// Then it increase the flow on this path with the minimal residual
2.197 + /// capacity on the path. If there is not such path it gives back
2.198 + /// false.
2.199 + /// \return %False when the augmenting is not success so the
2.200 + /// current flow is a feasible and optimal solution.
2.201 + bool augment() {
2.202 + typename Bfs<ResGraph>
2.203 + ::template DefDistMap<NullMap<Node, int> >
2.204 + ::Create bfs(_resgraph);
2.205 +
2.206 + NullMap<Node, int> distMap;
2.207 + bfs.distMap(distMap);
2.208 +
2.209 + bfs.init();
2.210 + bfs.addSource(_source);
2.211 + bfs.start(_target);
2.212 +
2.213 + if (!bfs.reached(_target)) {
2.214 + return false;
2.215 + }
2.216 + Number min = _resgraph.rescap(bfs.predEdge(_target));
2.217 + for (Node it = bfs.predNode(_target); it != _source;
2.218 + it = bfs.predNode(it)) {
2.219 + if (min > _resgraph.rescap(bfs.predEdge(it))) {
2.220 + min = _resgraph.rescap(bfs.predEdge(it));
2.221 + }
2.222 + }
2.223 + for (Node it = _target; it != _source; it = bfs.predNode(it)) {
2.224 + _resgraph.augment(bfs.predEdge(it), min);
2.225 + }
2.226 + _value += min;
2.227 + return true;
2.228 + }
2.229 +
2.230 + /// \brief Executes the algorithm
2.231 + ///
2.232 + /// It runs augmenting phases until the optimal solution is reached.
2.233 + void start() {
2.234 + while (augment()) {}
2.235 + }
2.236 +
2.237 + /// \brief Gives back the current flow value.
2.238 + ///
2.239 + /// Gives back the current flow _value.
2.240 + Number flowValue() const {
2.241 + return _value;
2.242 + }
2.243 +
2.244 + /// \brief runs the algorithm.
2.245 + ///
2.246 + /// It is just a shorthand for:
2.247 + /// \code
2.248 + /// ek.init();
2.249 + /// ek.start();
2.250 + /// \endcode
2.251 + void run() {
2.252 + init();
2.253 + start();
2.254 + }
2.255 +
2.256 + /// \brief Returns a minimum value cut.
2.257 + ///
2.258 + /// Sets \c cut to the characteristic vector of a minimum value cut
2.259 + /// It simply calls the minMinCut member.
2.260 + template <typename CutMap>
2.261 + void minCut(CutMap& cut) const {
2.262 + minMinCut(cut);
2.263 + }
2.264 +
2.265 + /// \brief Returns the inclusionwise minimum of the minimum value cuts.
2.266 + ///
2.267 + /// Sets \c cut to the characteristic vector of the minimum value cut
2.268 + /// which is inclusionwise minimum. It is computed by processing a
2.269 + /// bfs from the source node \c source in the residual graph.
2.270 + template <typename CutMap>
2.271 + void minMinCut(CutMap& cut) const {
2.272 +
2.273 + typename Bfs<ResGraph>
2.274 + ::template DefDistMap<NullMap<Node, int> >
2.275 + ::template DefProcessedMap<CutMap>
2.276 + ::Create bfs(_resgraph);
2.277 +
2.278 + NullMap<Node, int> distMap;
2.279 + bfs.distMap(distMap);
2.280 +
2.281 + bfs.processedMap(cut);
2.282 +
2.283 + bfs.run(_source);
2.284 + }
2.285 +
2.286 + /// \brief Returns the inclusionwise minimum of the minimum value cuts.
2.287 + ///
2.288 + /// Sets \c cut to the characteristic vector of the minimum value cut
2.289 + /// which is inclusionwise minimum. It is computed by processing a
2.290 + /// bfs from the source node \c source in the residual graph.
2.291 + template <typename CutMap>
2.292 + void maxMinCut(CutMap& cut) const {
2.293 +
2.294 + typedef RevGraphAdaptor<const ResGraph> RevGraph;
2.295 +
2.296 + RevGraph revgraph(_resgraph);
2.297 +
2.298 + typename Bfs<RevGraph>
2.299 + ::template DefDistMap<NullMap<Node, int> >
2.300 + ::template DefPredMap<NullMap<Node, Edge> >
2.301 + ::template DefProcessedMap<NotWriteMap<CutMap> >
2.302 + ::Create bfs(revgraph);
2.303 +
2.304 + NullMap<Node, int> distMap;
2.305 + bfs.distMap(distMap);
2.306 +
2.307 + NullMap<Node, Edge> predMap;
2.308 + bfs.predMap(predMap);
2.309 +
2.310 + NotWriteMap<CutMap> notcut(cut);
2.311 + bfs.processedMap(notcut);
2.312 +
2.313 + bfs.run(_target);
2.314 + }
2.315 +
2.316 + /// \brief Sets the source node to \c _source.
2.317 + ///
2.318 + /// Sets the source node to \c _source.
2.319 + void source(Node source) {
2.320 + _source = source;
2.321 + }
2.322 +
2.323 + /// \brief Returns the source node.
2.324 + ///
2.325 + /// Returns the source node.
2.326 + ///
2.327 + Node source() const {
2.328 + return _source;
2.329 + }
2.330 +
2.331 + /// \brief Sets the target node to \c target.
2.332 + ///
2.333 + /// Sets the target node to \c target.
2.334 + void target(Node target) {
2.335 + _target = target;
2.336 + }
2.337 +
2.338 + /// \brief Returns the target node.
2.339 + ///
2.340 + /// Returns the target node.
2.341 + ///
2.342 + Node target() const {
2.343 + return _target;
2.344 + }
2.345 +
2.346 + /// \brief Sets the edge map of the capacities to _cap.
2.347 + ///
2.348 + /// Sets the edge map of the capacities to _cap.
2.349 + ///
2.350 + void capacityMap(const CapacityMap& capacity) {
2.351 + _capacity = &capacity;
2.352 + }
2.353 +
2.354 + /// \brief Returns a reference to capacity map.
2.355 + ///
2.356 + /// Returns a reference to capacity map.
2.357 + ///
2.358 + const CapacityMap &capacityMap() const {
2.359 + return *_capacity;
2.360 + }
2.361 +
2.362 + /// \brief Sets the edge map of the flows to \c flow.
2.363 + ///
2.364 + /// Sets the edge map of the flows to \c flow.
2.365 + ///
2.366 + void flowMap(FlowMap& flow) {
2.367 + _flow = &flow;
2.368 + }
2.369 +
2.370 + /// \brief Returns a reference to flow map.
2.371 + ///
2.372 + /// Returns a reference to flow map.
2.373 + ///
2.374 + const FlowMap &flowMap() const {
2.375 + return *_flow;
2.376 + }
2.377 +
2.378 + private:
2.379 +
2.380 + const Graph& _graph;
2.381 + const CapacityMap& _capacity;
2.382 + FlowMap& _flow;
2.383 + Tolerance _tolerance;
2.384 +
2.385 + ResGraph _resgraph;
2.386 + Node _source, _target;
2.387 + Number _value;
2.388 +
2.389 + };
2.390 +
2.391 +}
2.392 +
2.393 +#endif
3.1 --- a/lemon/graph_adaptor.h Mon Apr 03 16:05:26 2006 +0000
3.2 +++ b/lemon/graph_adaptor.h Mon Apr 03 16:34:23 2006 +0000
3.3 @@ -34,6 +34,8 @@
3.4 #include <lemon/bits/graph_adaptor_extender.h>
3.5 #include <lemon/bits/graph_extender.h>
3.6
3.7 +#include <lemon/tolerance.h>
3.8 +
3.9 #include <iostream>
3.10
3.11 namespace lemon {
3.12 @@ -71,6 +73,9 @@
3.13
3.14 public:
3.15 GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
3.16 +
3.17 + Graph& getGraph() { return *graph; }
3.18 + const Graph& getGraph() const { return *graph; }
3.19
3.20 typedef typename Graph::Node Node;
3.21 typedef typename Graph::Edge Edge;
3.22 @@ -1422,41 +1427,52 @@
3.23 return UndirGraphAdaptor<const Graph>(graph);
3.24 }
3.25
3.26 - template<typename Graph, typename Number,
3.27 - typename CapacityMap, typename FlowMap>
3.28 + template<typename Graph, typename Number,
3.29 + typename CapacityMap, typename FlowMap,
3.30 + typename Tolerance = Tolerance<Number> >
3.31 class ResForwardFilter {
3.32 const CapacityMap* capacity;
3.33 const FlowMap* flow;
3.34 + Tolerance tolerance;
3.35 public:
3.36 typedef typename Graph::Edge Key;
3.37 typedef bool Value;
3.38
3.39 - ResForwardFilter(const CapacityMap& _capacity, const FlowMap& _flow)
3.40 - : capacity(&_capacity), flow(&_flow) { }
3.41 - ResForwardFilter() : capacity(0), flow(0) { }
3.42 + ResForwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,
3.43 + const Tolerance& _tolerance = Tolerance())
3.44 + : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }
3.45 +
3.46 + ResForwardFilter(const Tolerance& _tolerance)
3.47 + : capacity(0), flow(0), tolerance(_tolerance) { }
3.48 +
3.49 void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
3.50 void setFlow(const FlowMap& _flow) { flow = &_flow; }
3.51 +
3.52 bool operator[](const typename Graph::Edge& e) const {
3.53 - return (Number((*flow)[e]) < Number((*capacity)[e]));
3.54 + return tolerance.less((*flow)[e], (*capacity)[e]);
3.55 }
3.56 };
3.57
3.58 template<typename Graph, typename Number,
3.59 - typename CapacityMap, typename FlowMap>
3.60 + typename CapacityMap, typename FlowMap,
3.61 + typename Tolerance = Tolerance<Number> >
3.62 class ResBackwardFilter {
3.63 const CapacityMap* capacity;
3.64 const FlowMap* flow;
3.65 + Tolerance tolerance;
3.66 public:
3.67 typedef typename Graph::Edge Key;
3.68 typedef bool Value;
3.69
3.70 - ResBackwardFilter(const CapacityMap& _capacity, const FlowMap& _flow)
3.71 - : capacity(&_capacity), flow(&_flow) { }
3.72 - ResBackwardFilter() : capacity(0), flow(0) { }
3.73 + ResBackwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,
3.74 + const Tolerance& _tolerance = Tolerance())
3.75 + : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }
3.76 + ResBackwardFilter(const Tolerance& _tolerance = Tolerance())
3.77 + : capacity(0), flow(0), tolerance(_tolerance) { }
3.78 void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
3.79 void setFlow(const FlowMap& _flow) { flow = &_flow; }
3.80 bool operator[](const typename Graph::Edge& e) const {
3.81 - return (Number(0) < Number((*flow)[e]));
3.82 + return tolerance.less(0, Number((*flow)[e]));
3.83 }
3.84 };
3.85
3.86 @@ -1497,21 +1513,22 @@
3.87 ///\author Marton Makai
3.88 ///
3.89 template<typename Graph, typename Number,
3.90 - typename CapacityMap, typename FlowMap>
3.91 + typename CapacityMap, typename FlowMap,
3.92 + typename Tolerance = Tolerance<Number> >
3.93 class ResGraphAdaptor :
3.94 public EdgeSubGraphAdaptor<
3.95 - UndirGraphAdaptor<Graph>,
3.96 - typename UndirGraphAdaptor<Graph>::template CombinedEdgeMap<
3.97 - ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
3.98 - ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > > {
3.99 + UndirGraphAdaptor<const Graph>,
3.100 + typename UndirGraphAdaptor<const Graph>::template CombinedEdgeMap<
3.101 + ResForwardFilter<const Graph, Number, CapacityMap, FlowMap>,
3.102 + ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap> > > {
3.103 public:
3.104
3.105 - typedef UndirGraphAdaptor<Graph> UGraph;
3.106 + typedef UndirGraphAdaptor<const Graph> UGraph;
3.107
3.108 - typedef ResForwardFilter<Graph, Number, CapacityMap, FlowMap>
3.109 + typedef ResForwardFilter<const Graph, Number, CapacityMap, FlowMap>
3.110 ForwardFilter;
3.111
3.112 - typedef ResBackwardFilter<Graph, Number, CapacityMap, FlowMap>
3.113 + typedef ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap>
3.114 BackwardFilter;
3.115
3.116 typedef typename UGraph::
3.117 @@ -1544,44 +1561,77 @@
3.118
3.119 public:
3.120
3.121 - ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity,
3.122 - FlowMap& _flow)
3.123 - : Parent(), capacity(&_capacity), flow(&_flow),
3.124 - ugraph(_graph),
3.125 - forward_filter(_capacity, _flow),
3.126 - backward_filter(_capacity, _flow),
3.127 - edge_filter(forward_filter, backward_filter) {
3.128 + const Graph& getGraph() const { return ugraph.getGraph(); }
3.129 +
3.130 + /// \brief Constructor of the residual graph.
3.131 + ///
3.132 + /// Constructor of the residual graph. The parameters are the graph type,
3.133 + /// the flow map, the capacity map and a tolerance object.
3.134 + ResGraphAdaptor(const Graph& _graph, const CapacityMap& _capacity,
3.135 + FlowMap& _flow, const Tolerance& _tolerance = Tolerance())
3.136 + : Parent(), capacity(&_capacity), flow(&_flow), ugraph(_graph),
3.137 + forward_filter(_capacity, _flow, _tolerance),
3.138 + backward_filter(_capacity, _flow, _tolerance),
3.139 + edge_filter(forward_filter, backward_filter)
3.140 + {
3.141 Parent::setGraph(ugraph);
3.142 Parent::setEdgeFilterMap(edge_filter);
3.143 }
3.144
3.145 typedef typename Parent::Edge Edge;
3.146
3.147 + /// \brief Gives back the residual capacity of the edge.
3.148 + ///
3.149 + /// Gives back the residual capacity of the edge.
3.150 + Number rescap(const Edge& edge) const {
3.151 + if (UGraph::direction(edge)) {
3.152 + return (*capacity)[edge]-(*flow)[edge];
3.153 + } else {
3.154 + return (*flow)[edge];
3.155 + }
3.156 + }
3.157 +
3.158 + /// \brief Augment on the given edge in the residual graph.
3.159 + ///
3.160 + /// Augment on the given edge in the residual graph. It increase
3.161 + /// or decrease the flow on the original edge depend on the direction
3.162 + /// of the residual edge.
3.163 void augment(const Edge& e, Number a) const {
3.164 if (UGraph::direction(e)) {
3.165 - flow->set(e, (*flow)[e]+a);
3.166 + flow->set(e, (*flow)[e] + a);
3.167 } else {
3.168 - flow->set(e, (*flow)[e]-a);
3.169 + flow->set(e, (*flow)[e] - a);
3.170 }
3.171 }
3.172
3.173 + /// \brief Returns the direction of the edge.
3.174 + ///
3.175 + /// Returns true when the edge is same oriented as the original edge.
3.176 static bool forward(const Edge& e) {
3.177 return UGraph::direction(e);
3.178 }
3.179
3.180 + /// \brief Returns the direction of the edge.
3.181 + ///
3.182 + /// Returns true when the edge is opposite oriented as the original edge.
3.183 static bool backward(const Edge& e) {
3.184 return !UGraph::direction(e);
3.185 }
3.186
3.187 + /// \brief Gives back the forward oriented residual edge.
3.188 + ///
3.189 + /// Gives back the forward oriented residual edge.
3.190 static Edge forward(const typename Graph::Edge& e) {
3.191 return UGraph::direct(e, true);
3.192 }
3.193
3.194 + /// \brief Gives back the backward oriented residual edge.
3.195 + ///
3.196 + /// Gives back the backward oriented residual edge.
3.197 static Edge backward(const typename Graph::Edge& e) {
3.198 return UGraph::direct(e, false);
3.199 }
3.200
3.201 -
3.202 /// \brief Residual capacity map.
3.203 ///
3.204 /// In generic residual graphs the residual capacity can be obtained
3.205 @@ -1595,11 +1645,8 @@
3.206 ResCap(const ResGraphAdaptor& _res_graph)
3.207 : res_graph(&_res_graph) {}
3.208
3.209 - Number operator[](const Edge& e) const {
3.210 - if (ResGraphAdaptor::direction(e))
3.211 - return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
3.212 - else
3.213 - return (*(res_graph->flow))[e];
3.214 + Number operator[](const Edge& e) const {
3.215 + return res_graph->rescap(e);
3.216 }
3.217
3.218 };