3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
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 DEMO_TIGHT_EDGE_FILTER_MAP_H
20 #define DEMO_TIGHT_EDGE_FILTER_MAP_H
22 #include <lemon/maps.h>
25 /// \brief Tight edge filter map.
27 /// Tight edge filter map is bool map on the edges of the graph
28 /// which filters the edges which are not tight for a node-potential.
29 /// It is used in the \ref sub_graph_adaptor_demo.cc file.
31 /// \include tight_edge_filter_map.h
35 /// \brief A map for filtering the edge-set to those edges
36 /// which are tight w.r.t. a node-potential and
39 /// Let \f$ G=(V,A) \f$ be a directed graph (graph for short) and
40 /// let \f$ \mathbb{F} \f$ be a number type.
41 /// Given a distance function
42 /// \f$ d:E\to\mathbb{F} \f$,
43 /// \f$ \pi:V\to\mathbb{F} \f$ is said to be a potetial
46 /// \f$ \pi(v)\le d(uv)+\pi(u) \f$ holds for each edge \f$ uv\in E \f$
47 /// (or the reverse inequality holds for each edge).
48 /// An edge is said to be tight if this inequality holds with equality,
49 /// and the map returns \c true exactly for those edges.
50 /// To avoid rounding errors, it is recommended to use this class with exact
51 /// number types, e.g. with \c int.
52 template<typename Graph,
53 typename NodePotentialMap, typename EdgeDistanceMap>
54 class TightEdgeFilterMap : public MapBase<typename Graph::Edge, bool> {
57 NodePotentialMap* node_potential;
58 EdgeDistanceMap* edge_distance;
60 TightEdgeFilterMap(Graph& _g, NodePotentialMap& _node_potential,
61 EdgeDistanceMap& _edge_distance) :
62 g(&_g), node_potential(&_node_potential),
63 edge_distance(&_edge_distance) { }
64 bool operator[](const typename Graph::Edge& e) const {
65 return ((*node_potential)[g->target(e)] ==
66 (*edge_distance)[e]+(*node_potential)[g->source(e)]);
72 #endif //DEMO_TIGHT_EDGE_FILTER_MAP_H