/* -*- 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 // /// \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 class TightEdgeFilterMap : public MapBase { 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