alpar@906: /* -*- C++ -*-
ladanyi@1435:  * demo/tight_edge_filter_map.h - Part of LEMON, a generic C++ optimization
ladanyi@1435:  * library
alpar@906:  *
alpar@1164:  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1359:  * (Egervary Research Group on Combinatorial Optimization, 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@1276:   /*! 
marci@1276:     \brief A map for filtering the edge-set to those edges 
marci@1276:     which are tight w.r.t. a node-potential and 
marci@1276:     edge-distance.
marci@1276:     
marci@1276:     Let \f$G=(V,A)\f$ be a directed graph (graph for short) and 
marci@1276:     let \f$\mathbb{F}\f$ be a number type. 
marci@1276:     Given a distance function 
marci@1276:     \f$d:E\to\mathbb{F}\f$, 
marci@1276:     \f$\pi:V\to\mathbb{F}\f$ is said to be a potetial 
marci@1276:     w.r.t. \f$d\f$ 
marci@1276:     if and only if 
marci@1276:     \f$\pi(v)\le d(uv)+\pi(u)\f$ holds for each edge \f$uv\in E\f$ 
marci@1276:     (or the reverse inequality holds for each edge). 
marci@1276:     An edge is said to be tight if this inequality holds with equality, 
marci@1276:     and the map returns \c true exactly for those edges. 
marci@1276:     To avoid rounding errors, it is recommended to use this class with exact 
marci@1276:     number types, e.g. with \c int.
marci@1276:   */
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 {
alpar@986:       return ((*node_potential)[g->target(e)] == 
alpar@986: 	      (*edge_distance)[e]+(*node_potential)[g->source(e)]);
marci@888:     }
marci@888:   };
marci@888: 
alpar@921: } //namespace lemon
marci@888: 
alpar@921: #endif //LEMON_TIGHT_EDGE_FILTER_MAP_H