/* -*- C++ -*- * * This file is a part of LEMON, a generic C++ optimization library * * Copyright (C) 2003-2006 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, 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 DEMO_TIGHT_EDGE_FILTER_MAP_H #define DEMO_TIGHT_EDGE_FILTER_MAP_H #include /// \file /// \brief Tight edge filter map. /// /// Tight edge filter map is bool map on the edges of the graph /// which filters the edges which are not tight for a node-potential. /// It is used in the \ref sub_graph_adaptor_demo.cc file. /// /// \include tight_edge_filter_map.h namespace lemon { /// \brief A map for filtering the edge-set to those edges /// which are tight w.r.t. a node-potential and /// edge-distance. /// /// Let \f$G=(V,A) \f$ be a directed graph (graph for short) and /// let \f$\mathbb{F} \f$ be a number type. /// Given a distance function /// \f$d:E\to\mathbb{F} \f$, /// \f$\pi:V\to\mathbb{F} \f$ is said to be a potetial /// w.r.t. \f$d \f$ /// if and only if /// \f$\pi(v)\le d(uv)+\pi(u) \f$ holds for each edge \f$uv\in E \f$ /// (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 \c true exactly for those edges. /// To avoid rounding errors, it is recommended to use this class with exact /// number types, e.g. with \c 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->target(e)] == (*edge_distance)[e]+(*node_potential)[g->source(e)]); } }; } //namespace lemon #endif //DEMO_TIGHT_EDGE_FILTER_MAP_H