alpar@906: /* -*- C++ -*-
alpar@921:  * src/lemon/tight_edge_filter_map.h - Part of LEMON, a generic C++ optimization library
alpar@906:  *
alpar@906:  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@906:  * (Egervary Combinatorial Optimization Research Group, EGRES).
alpar@906:  *
alpar@906:  * Permission to use, modify and distribute this software is granted
alpar@906:  * provided that this copyright notice appears in all copies. For
alpar@906:  * precise terms see the accompanying LICENSE file.
alpar@906:  *
alpar@906:  * This software is provided "AS IS" with no warranty of any kind,
alpar@906:  * express or implied, and with no claim as to its suitability for any
alpar@906:  * purpose.
alpar@906:  *
alpar@906:  */
alpar@906: 
alpar@921: #ifndef LEMON_TIGHT_EDGE_FILTER_MAP_H
alpar@921: #define LEMON_TIGHT_EDGE_FILTER_MAP_H
marci@888: 
alpar@921: #include <lemon/maps.h>
marci@910: 
marci@888: // /// \file
marci@888: // /// \brief Maximum flow algorithms.
marci@888: // /// \ingroup galgs
marci@888: 
alpar@921: namespace lemon {
marci@888: 
marci@888:   /// \brief A map for filtering the edge-set to those edges 
marci@888:   /// which are tight w.r.t. some node_potential map and 
marci@888:   /// edge_distance map.
marci@888:   ///
marci@888:   /// A node-map node_potential is said to be a potential w.r.t. 
marci@888:   /// an edge-map edge_distance 
marci@888:   /// if and only if for each edge e, node_potential[g.head(e)] 
marci@888:   /// <= edge_distance[e]+node_potential[g.tail(e)] 
marci@888:   /// (or the reverse inequality holds for each edge).
marci@888:   /// An edge is said to be tight if this inequality holds with equality, 
marci@888:   /// and the map returns true exactly for those edges.
marci@888:   /// To avoid rounding errors, it is recommended to use this class with exact 
marci@888:   /// types, e.g. with int.
marci@888:   template<typename Graph, 
marci@888: 	   typename NodePotentialMap, typename EdgeDistanceMap>
marci@910:   class TightEdgeFilterMap : public MapBase<typename Graph::Edge, bool> {
marci@888:   protected:
marci@888:     const Graph* g;
marci@888:     NodePotentialMap* node_potential;
marci@888:     EdgeDistanceMap* edge_distance;
marci@888:   public:
marci@888:     TightEdgeFilterMap(Graph& _g, NodePotentialMap& _node_potential, 
marci@888: 		       EdgeDistanceMap& _edge_distance) : 
marci@888:       g(&_g), node_potential(&_node_potential), 
marci@888:       edge_distance(&_edge_distance) { }
marci@888:     bool operator[](const typename Graph::Edge& e) const {
marci@888:       return ((*node_potential)[g->head(e)] == 
marci@888: 	      (*edge_distance)[e]+(*node_potential)[g->tail(e)]);
marci@888:     }
marci@888:   };
marci@888: 
alpar@921: } //namespace lemon
marci@888: 
alpar@921: #endif //LEMON_TIGHT_EDGE_FILTER_MAP_H
marci@888: 
marci@888: