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