3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_TIGHT_EDGE_FILTER_MAP_H
20 #define LEMON_TIGHT_EDGE_FILTER_MAP_H
22 #include <lemon/maps.h>
25 // /// \brief Maximum flow algorithms.
31 \brief A map for filtering the edge-set to those edges
32 which are tight w.r.t. a node-potential and
35 Let \f$ G=(V,A) \f$ be a directed graph (graph for short) and
36 let \f$ \mathbb{F} \f$ be a number type.
37 Given a distance function
38 \f$ d:E\to\mathbb{F} \f$,
39 \f$ \pi:V\to\mathbb{F} \f$ is said to be a potetial
42 \f$ \pi(v)\le d(uv)+\pi(u) \f$ holds for each edge \f$ uv\in E \f$
43 (or the reverse inequality holds for each edge).
44 An edge is said to be tight if this inequality holds with equality,
45 and the map returns \c true exactly for those edges.
46 To avoid rounding errors, it is recommended to use this class with exact
47 number types, e.g. with \c int.
49 template<typename Graph,
50 typename NodePotentialMap, typename EdgeDistanceMap>
51 class TightEdgeFilterMap : public MapBase<typename Graph::Edge, bool> {
54 NodePotentialMap* node_potential;
55 EdgeDistanceMap* edge_distance;
57 TightEdgeFilterMap(Graph& _g, NodePotentialMap& _node_potential,
58 EdgeDistanceMap& _edge_distance) :
59 g(&_g), node_potential(&_node_potential),
60 edge_distance(&_edge_distance) { }
61 bool operator[](const typename Graph::Edge& e) const {
62 return ((*node_potential)[g->target(e)] ==
63 (*edge_distance)[e]+(*node_potential)[g->source(e)]);
69 #endif //LEMON_TIGHT_EDGE_FILTER_MAP_H