/* -*- C++ -*-

  * src/lemon/tight_edge_filter_map.h - Part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Combinatorial Optimization Research Group, EGRES).

  *

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * precise terms see the accompanying LICENSE file.

  *

  * This software is provided "AS IS" with no warranty of any kind,

  * express or implied, and with no claim as to its suitability for any

  * purpose.

  *

  */

 #ifndef LEMON_TIGHT_EDGE_FILTER_MAP_H

 #define LEMON_TIGHT_EDGE_FILTER_MAP_H

 #include <lemon/maps.h>

 // /// \file

 // /// \brief Maximum flow algorithms.

 // /// \ingroup galgs

 namespace lemon {

   /// \brief A map for filtering the edge-set to those edges 

   /// which are tight w.r.t. some node_potential map and 

   /// edge_distance map.

   ///

   /// A node-map node_potential is said to be a potential w.r.t. 

   /// an edge-map edge_distance 

   /// if and only if for each edge e, node_potential[g.head(e)] 

   /// <= edge_distance[e]+node_potential[g.tail(e)] 

   /// (or the reverse inequality holds for each edge).

   /// An edge is said to be tight if this inequality holds with equality, 

   /// and the map returns true exactly for those edges.

   /// To avoid rounding errors, it is recommended to use this class with exact 

   /// types, e.g. with int.

   template<typename Graph, 

 	   typename NodePotentialMap, typename EdgeDistanceMap>

   class TightEdgeFilterMap : public MapBase<typename Graph::Edge, bool> {

   protected:

     const Graph* g;

     NodePotentialMap* node_potential;

     EdgeDistanceMap* edge_distance;

   public:

     TightEdgeFilterMap(Graph& _g, NodePotentialMap& _node_potential, 

 		       EdgeDistanceMap& _edge_distance) : 

       g(&_g), node_potential(&_node_potential), 

       edge_distance(&_edge_distance) { }

     bool operator[](const typename Graph::Edge& e) const {

       return ((*node_potential)[g->head(e)] == 

 	      (*edge_distance)[e]+(*node_potential)[g->tail(e)]);

     }

   };

 } //namespace lemon

 #endif //LEMON_TIGHT_EDGE_FILTER_MAP_H