COIN-OR::LEMON - Graph Library

Changeset 2034:b71f8ff62046 in lemon-0.x for lemon/graph_adaptor.h


Ignore:
Timestamp:
04/03/06 18:34:23 (14 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

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/graph_adaptor.h

    r2031 r2034  
    3535#include <lemon/bits/graph_extender.h>
    3636
     37#include <lemon/tolerance.h>
     38
    3739#include <iostream>
    3840
     
    7274  public:
    7375    GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
     76
     77    Graph& getGraph() { return *graph; }
     78    const Graph& getGraph() const { return *graph; }
    7479 
    7580    typedef typename Graph::Node Node;
     
    14231428  }
    14241429
    1425   template<typename Graph, typename Number,
    1426            typename CapacityMap, typename FlowMap>
     1430  template<typename Graph, typename Number, 
     1431           typename CapacityMap, typename FlowMap,
     1432           typename Tolerance = Tolerance<Number> >
    14271433  class ResForwardFilter {
    14281434    const CapacityMap* capacity;
    14291435    const FlowMap* flow;
     1436    Tolerance tolerance;
    14301437  public:
    14311438    typedef typename Graph::Edge Key;
    14321439    typedef bool Value;
    14331440
    1434     ResForwardFilter(const CapacityMap& _capacity, const FlowMap& _flow)
    1435       : capacity(&_capacity), flow(&_flow) { }
    1436     ResForwardFilter() : capacity(0), flow(0) { }
     1441    ResForwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,
     1442                     const Tolerance& _tolerance = Tolerance())
     1443      : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }
     1444
     1445    ResForwardFilter(const Tolerance& _tolerance)
     1446      : capacity(0), flow(0), tolerance(_tolerance)  { }
     1447
     1448    void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
     1449    void setFlow(const FlowMap& _flow) { flow = &_flow; }
     1450
     1451    bool operator[](const typename Graph::Edge& e) const {
     1452      return tolerance.less((*flow)[e], (*capacity)[e]);
     1453    }
     1454  };
     1455
     1456  template<typename Graph, typename Number,
     1457           typename CapacityMap, typename FlowMap,
     1458           typename Tolerance = Tolerance<Number> >
     1459  class ResBackwardFilter {
     1460    const CapacityMap* capacity;
     1461    const FlowMap* flow;
     1462    Tolerance tolerance;
     1463  public:
     1464    typedef typename Graph::Edge Key;
     1465    typedef bool Value;
     1466
     1467    ResBackwardFilter(const CapacityMap& _capacity, const FlowMap& _flow,
     1468                      const Tolerance& _tolerance = Tolerance())
     1469      : capacity(&_capacity), flow(&_flow), tolerance(_tolerance) { }
     1470    ResBackwardFilter(const Tolerance& _tolerance = Tolerance())
     1471      : capacity(0), flow(0), tolerance(_tolerance) { }
    14371472    void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
    14381473    void setFlow(const FlowMap& _flow) { flow = &_flow; }
    14391474    bool operator[](const typename Graph::Edge& e) const {
    1440       return (Number((*flow)[e]) < Number((*capacity)[e]));
    1441     }
    1442   };
    1443 
    1444   template<typename Graph, typename Number,
    1445            typename CapacityMap, typename FlowMap>
    1446   class ResBackwardFilter {
    1447     const CapacityMap* capacity;
    1448     const FlowMap* flow;
    1449   public:
    1450     typedef typename Graph::Edge Key;
    1451     typedef bool Value;
    1452 
    1453     ResBackwardFilter(const CapacityMap& _capacity, const FlowMap& _flow)
    1454       : capacity(&_capacity), flow(&_flow) { }
    1455     ResBackwardFilter() : capacity(0), flow(0) { }
    1456     void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
    1457     void setFlow(const FlowMap& _flow) { flow = &_flow; }
    1458     bool operator[](const typename Graph::Edge& e) const {
    1459       return (Number(0) < Number((*flow)[e]));
     1475      return tolerance.less(0, Number((*flow)[e]));
    14601476    }
    14611477  };
     
    14981514  ///
    14991515  template<typename Graph, typename Number,
    1500            typename CapacityMap, typename FlowMap>
     1516           typename CapacityMap, typename FlowMap,
     1517           typename Tolerance = Tolerance<Number> >
    15011518  class ResGraphAdaptor :
    15021519    public EdgeSubGraphAdaptor<
    1503     UndirGraphAdaptor<Graph>,
    1504     typename UndirGraphAdaptor<Graph>::template CombinedEdgeMap<
    1505     ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
    1506     ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > > {
    1507   public:
    1508 
    1509     typedef UndirGraphAdaptor<Graph> UGraph;
    1510 
    1511     typedef ResForwardFilter<Graph, Number, CapacityMap, FlowMap>
     1520    UndirGraphAdaptor<const Graph>,
     1521    typename UndirGraphAdaptor<const Graph>::template CombinedEdgeMap<
     1522    ResForwardFilter<const Graph, Number, CapacityMap, FlowMap>, 
     1523    ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap> > > {
     1524  public:
     1525
     1526    typedef UndirGraphAdaptor<const Graph> UGraph;
     1527
     1528    typedef ResForwardFilter<const Graph, Number, CapacityMap, FlowMap>
    15121529    ForwardFilter;
    15131530
    1514     typedef ResBackwardFilter<Graph, Number, CapacityMap, FlowMap>
     1531    typedef ResBackwardFilter<const Graph, Number, CapacityMap, FlowMap>
    15151532    BackwardFilter;
    15161533
     
    15451562  public:
    15461563
    1547     ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity,
    1548                     FlowMap& _flow)
    1549       : Parent(), capacity(&_capacity), flow(&_flow),
    1550         ugraph(_graph),
    1551         forward_filter(_capacity, _flow),
    1552         backward_filter(_capacity, _flow),
    1553         edge_filter(forward_filter, backward_filter) {
     1564    const Graph& getGraph() const { return ugraph.getGraph(); }
     1565
     1566    /// \brief Constructor of the residual graph.
     1567    ///
     1568    /// Constructor of the residual graph. The parameters are the graph type,
     1569    /// the flow map, the capacity map and a tolerance object.
     1570    ResGraphAdaptor(const Graph& _graph, const CapacityMap& _capacity,
     1571                    FlowMap& _flow, const Tolerance& _tolerance = Tolerance())
     1572      : Parent(), capacity(&_capacity), flow(&_flow), ugraph(_graph),
     1573        forward_filter(_capacity, _flow, _tolerance),
     1574        backward_filter(_capacity, _flow, _tolerance),
     1575        edge_filter(forward_filter, backward_filter)
     1576    {
    15541577      Parent::setGraph(ugraph);
    15551578      Parent::setEdgeFilterMap(edge_filter);
     
    15581581    typedef typename Parent::Edge Edge;
    15591582
     1583    /// \brief Gives back the residual capacity of the edge.
     1584    ///
     1585    /// Gives back the residual capacity of the edge.
     1586    Number rescap(const Edge& edge) const {
     1587      if (UGraph::direction(edge)) {
     1588        return (*capacity)[edge]-(*flow)[edge];
     1589      } else {
     1590        return (*flow)[edge];
     1591      }
     1592    }
     1593
     1594    /// \brief Augment on the given edge in the residual graph.
     1595    ///
     1596    /// Augment on the given edge in the residual graph. It increase
     1597    /// or decrease the flow on the original edge depend on the direction
     1598    /// of the residual edge.
    15601599    void augment(const Edge& e, Number a) const {
    15611600      if (UGraph::direction(e)) {
    1562         flow->set(e, (*flow)[e]+a);
     1601        flow->set(e, (*flow)[e] + a);
    15631602      } else { 
    1564         flow->set(e, (*flow)[e]-a);
    1565       }
    1566     }
    1567 
     1603        flow->set(e, (*flow)[e] - a);
     1604      }
     1605    }
     1606
     1607    /// \brief Returns the direction of the edge.
     1608    ///
     1609    /// Returns true when the edge is same oriented as the original edge.
    15681610    static bool forward(const Edge& e) {
    15691611      return UGraph::direction(e);
    15701612    }
    15711613
     1614    /// \brief Returns the direction of the edge.
     1615    ///
     1616    /// Returns true when the edge is opposite oriented as the original edge.
    15721617    static bool backward(const Edge& e) {
    15731618      return !UGraph::direction(e);
    15741619    }
    15751620
     1621    /// \brief Gives back the forward oriented residual edge.
     1622    ///
     1623    /// Gives back the forward oriented residual edge.
    15761624    static Edge forward(const typename Graph::Edge& e) {
    15771625      return UGraph::direct(e, true);
    15781626    }
    15791627
     1628    /// \brief Gives back the backward oriented residual edge.
     1629    ///
     1630    /// Gives back the backward oriented residual edge.
    15801631    static Edge backward(const typename Graph::Edge& e) {
    15811632      return UGraph::direct(e, false);
    15821633    }
    1583 
    15841634
    15851635    /// \brief Residual capacity map.
     
    15961646        : res_graph(&_res_graph) {}
    15971647     
    1598       Number operator[](const Edge& e) const {
    1599         if (ResGraphAdaptor::direction(e))
    1600           return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
    1601         else
    1602           return (*(res_graph->flow))[e];
     1648      Number operator[](const Edge& e) const {
     1649        return res_graph->rescap(e);
    16031650      }
    16041651     
Note: See TracChangeset for help on using the changeset viewer.