marci@762: // -*- C++ -*-
marci@863: #ifndef HUGO_TIGHT_EDGE_FILTER_MAP_H
marci@863: #define HUGO_TIGHT_EDGE_FILTER_MAP_H
marci@762: 
marci@863: // /// \file
marci@863: // /// \brief Maximum flow algorithms.
marci@863: // /// \ingroup galgs
marci@762: 
marci@762: namespace hugo {
marci@762: 
marci@862:   /// \brief A map for filtering the edge-set to those edges 
marci@862:   /// which are tight w.r.t. some node_potential map and 
marci@862:   /// edge_distance map.
marci@862:   ///
marci@862:   /// A node-map node_potential is said to be a potential w.r.t. 
marci@862:   /// an edge-map edge_distance 
marci@862:   /// if and only if for each edge e, node_potential[g.head(e)] 
marci@862:   /// <= edge_distance[e]+node_potential[g.tail(e)] 
marci@862:   /// (or the reverse inequality holds for each edge).
marci@862:   /// An edge is said to be tight if this inequality holds with equality, 
marci@862:   /// and the map returns true exactly for those edges.
marci@862:   /// To avoid rounding errors, it is recommended to use this class with exact 
marci@862:   /// types, e.g. with int.
marci@862:   template<typename Graph, 
marci@862: 	   typename NodePotentialMap, typename EdgeDistanceMap>
marci@862:   class TightEdgeFilterMap {
marci@862:   protected:
marci@862:     const Graph* g;
marci@862:     NodePotentialMap* node_potential;
marci@862:     EdgeDistanceMap* edge_distance;
marci@862:   public:
marci@862:     TightEdgeFilterMap(Graph& _g, NodePotentialMap& _node_potential, 
marci@862: 		       EdgeDistanceMap& _edge_distance) : 
marci@862:       g(&_g), node_potential(&_node_potential), 
marci@862:       edge_distance(&_edge_distance) { }
marci@862:     bool operator[](const typename Graph::Edge& e) const {
marci@862:       return ((*node_potential)[g->head(e)] == 
marci@862: 	      (*edge_distance)[e]+(*node_potential)[g->tail(e)]);
marci@862:     }
marci@862:   };
marci@862: 
marci@762: } //namespace hugo
marci@762: 
marci@863: #endif //HUGO_TIGHT_EDGE_FILTER_MAP_H
marci@762: 
marci@762: