Changeset 2034:b71f8ff62046 in lemon-0.x

Timestamp:

04/03/06 18:34:23 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2673

Message:

Edmonds-Karp MaxFlow?
ResGraphAdaptor? with Tolerance

Location:

lemon

Files:

• Makefile.am (modified) (1 diff)
• edmonds_karp.h (added)
• graph_adaptor.h (modified) (7 diffs)

lemon/Makefile.am

@@ -36 +36 @@
         dag_shortest_path.h \
         edge_set.h \
+        edmonds_karp.h \
         error.h \
         eps.h \

lemon/graph_adaptor.h

@@ -35 +35 @@
 #include <lemon/bits/graph_extender.h>
 
+#include <lemon/tolerance.h>
+
 #include <iostream>
 
@@ -72 +74 @@
   public:
     GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
+
+    Graph& getGraph() { return *graph; }
+    const Graph& getGraph() const { return *graph; }
  
     typedef typename Graph::Node Node;
@@ -1423 +1428 @@
   }
 
-  template<typename Graph, typename Number,
-           typename CapacityMap, typename FlowMap>
+  template<typename Graph, typename Number,  
+           typename CapacityMap, typename FlowMap, 
+           typename Tolerance = Tolerance<Number> >
   class ResForwardFilter {
     const CapacityMap* capacity;
     const FlowMap* flow;
+    Tolerance tolerance;
   public:
     typedef typename Graph::Edge Key;
     typedef bool Value;
 
-    ResForwardFilter(const CapacityMap& _capacity, const FlowMap& _flow) 
-      : capacity(&_capacity), flow(&_flow) { }
-    ResForwardFilter() : capacity(0), flow(0) { }
+    ResForwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,
+                     const Tolerance& _tolerance = Tolerance()) 
+      : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }
+
+    ResForwardFilter(const Tolerance& _tolerance) 
+      : capacity(0), flow(0), tolerance(_tolerance)  { }
+
+    void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
+    void setFlow(const FlowMap& _flow) { flow = &_flow; }
+
+    bool operator[](const typename Graph::Edge& e) const {
+      return tolerance.less((*flow)[e], (*capacity)[e]);
+    }
+  };
+
+  template<typename Graph, typename Number,
+           typename CapacityMap, typename FlowMap,
+           typename Tolerance = Tolerance<Number> >
+  class ResBackwardFilter {
+    const CapacityMap* capacity;
+    const FlowMap* flow;
+    Tolerance tolerance;
+  public:
+    typedef typename Graph::Edge Key;
+    typedef bool Value;
+
+    ResBackwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,
+                      const Tolerance& _tolerance = Tolerance())
+      : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }
+    ResBackwardFilter(const Tolerance& _tolerance = Tolerance())
+      : capacity(0), flow(0), tolerance(_tolerance) { }
     void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
     void setFlow(const FlowMap& _flow) { flow = &_flow; }
     bool operator[](const typename Graph::Edge& e) const {
-      return (Number((*flow)[e]) < Number((*capacity)[e]));
-    }
-  };
-
-  template<typename Graph, typename Number,
-           typename CapacityMap, typename FlowMap>
-  class ResBackwardFilter {
-    const CapacityMap* capacity;
-    const FlowMap* flow;
-  public:
-    typedef typename Graph::Edge Key;
-    typedef bool Value;
-
-    ResBackwardFilter(const CapacityMap& _capacity, const FlowMap& _flow) 
-      : capacity(&_capacity), flow(&_flow) { }
-    ResBackwardFilter() : capacity(0), flow(0) { }
-    void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
-    void setFlow(const FlowMap& _flow) { flow = &_flow; }
-    bool operator[](const typename Graph::Edge& e) const {
-      return (Number(0) < Number((*flow)[e]));
+      return tolerance.less(0, Number((*flow)[e]));
     }
   };
@@ -1498 +1514 @@
   ///
   template<typename Graph, typename Number, 
-           typename CapacityMap, typename FlowMap>
+           typename CapacityMap, typename FlowMap,
+           typename Tolerance = Tolerance<Number> >
   class ResGraphAdaptor : 
     public EdgeSubGraphAdaptor< 
-    UndirGraphAdaptor<Graph>, 
-    typename UndirGraphAdaptor<Graph>::template CombinedEdgeMap<
-    ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,  
-    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > > {
-  public:
-
-    typedef UndirGraphAdaptor<Graph> UGraph;
-
-    typedef ResForwardFilter<Graph, Number, CapacityMap, FlowMap> 
+    UndirGraphAdaptor<const Graph>, 
+    typename UndirGraphAdaptor<const Graph>::template CombinedEdgeMap<
+    ResForwardFilter<const Graph, Number, CapacityMap, FlowMap>,  
+    ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap> > > {
+  public:
+
+    typedef UndirGraphAdaptor<const Graph> UGraph;
+
+    typedef ResForwardFilter<const Graph, Number, CapacityMap, FlowMap> 
     ForwardFilter;
 
-    typedef ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> 
+    typedef ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap> 
     BackwardFilter;
 
@@ -1545 +1562 @@
   public:
 
-    ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity, 
-                    FlowMap& _flow) 
-      : Parent(), capacity(&_capacity), flow(&_flow),
-        ugraph(_graph),
-        forward_filter(_capacity, _flow), 
-        backward_filter(_capacity, _flow),
-        edge_filter(forward_filter, backward_filter) {
+    const Graph& getGraph() const { return ugraph.getGraph(); }
+
+    /// \brief Constructor of the residual graph.
+    ///
+    /// Constructor of the residual graph. The parameters are the graph type,
+    /// the flow map, the capacity map and a tolerance object.
+    ResGraphAdaptor(const Graph& _graph, const CapacityMap& _capacity, 
+                    FlowMap& _flow, const Tolerance& _tolerance = Tolerance()) 
+      : Parent(), capacity(&_capacity), flow(&_flow), ugraph(_graph),
+        forward_filter(_capacity, _flow, _tolerance), 
+        backward_filter(_capacity, _flow, _tolerance),
+        edge_filter(forward_filter, backward_filter)
+    {
       Parent::setGraph(ugraph);
       Parent::setEdgeFilterMap(edge_filter);
@@ -1558 +1581 @@
     typedef typename Parent::Edge Edge;
 
+    /// \brief Gives back the residual capacity of the edge.
+    ///
+    /// Gives back the residual capacity of the edge.
+    Number rescap(const Edge& edge) const {
+      if (UGraph::direction(edge)) {
+        return (*capacity)[edge]-(*flow)[edge]; 
+      } else {
+        return (*flow)[edge];
+      }
+    } 
+
+    /// \brief Augment on the given edge in the residual graph.
+    ///
+    /// Augment on the given edge in the residual graph. It increase
+    /// or decrease the flow on the original edge depend on the direction
+    /// of the residual edge.
     void augment(const Edge& e, Number a) const {
       if (UGraph::direction(e)) {
-        flow->set(e, (*flow)[e]+a);
+        flow->set(e, (*flow)[e] + a);
       } else {  
-        flow->set(e, (*flow)[e]-a);
-      }
-    }
-
+        flow->set(e, (*flow)[e] - a);
+      }
+    }
+
+    /// \brief Returns the direction of the edge.
+    ///
+    /// Returns true when the edge is same oriented as the original edge.
     static bool forward(const Edge& e) {
       return UGraph::direction(e);
     }
 
+    /// \brief Returns the direction of the edge.
+    ///
+    /// Returns true when the edge is opposite oriented as the original edge.
     static bool backward(const Edge& e) {
       return !UGraph::direction(e);
     }
 
+    /// \brief Gives back the forward oriented residual edge.
+    ///
+    /// Gives back the forward oriented residual edge.
     static Edge forward(const typename Graph::Edge& e) {
       return UGraph::direct(e, true);
     }
 
+    /// \brief Gives back the backward oriented residual edge.
+    ///
+    /// Gives back the backward oriented residual edge.
     static Edge backward(const typename Graph::Edge& e) {
       return UGraph::direct(e, false);
     }
-
 
     /// \brief Residual capacity map.
@@ -1596 +1646 @@
         : res_graph(&_res_graph) {}
       
-      Number operator[](const Edge& e) const { 
-        if (ResGraphAdaptor::direction(e)) 
-          return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e]; 
-        else 
-          return (*(res_graph->flow))[e]; 
+      Number operator[](const Edge& e) const {
+        return res_graph->rescap(e);
       }