2 * src/hugo/tight_edge_filter_map.h - Part of HUGOlib, a generic C++ optimization library
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
17 #ifndef HUGO_TIGHT_EDGE_FILTER_MAP_H
18 #define HUGO_TIGHT_EDGE_FILTER_MAP_H
20 #include <hugo/maps.h>
23 // /// \brief Maximum flow algorithms.
28 /// \brief A map for filtering the edge-set to those edges
29 /// which are tight w.r.t. some node_potential map and
30 /// edge_distance map.
32 /// A node-map node_potential is said to be a potential w.r.t.
33 /// an edge-map edge_distance
34 /// if and only if for each edge e, node_potential[g.head(e)]
35 /// <= edge_distance[e]+node_potential[g.tail(e)]
36 /// (or the reverse inequality holds for each edge).
37 /// An edge is said to be tight if this inequality holds with equality,
38 /// and the map returns true exactly for those edges.
39 /// To avoid rounding errors, it is recommended to use this class with exact
40 /// types, e.g. with int.
41 template<typename Graph,
42 typename NodePotentialMap, typename EdgeDistanceMap>
43 class TightEdgeFilterMap : public MapBase<typename Graph::Edge, bool> {
46 NodePotentialMap* node_potential;
47 EdgeDistanceMap* edge_distance;
49 TightEdgeFilterMap(Graph& _g, NodePotentialMap& _node_potential,
50 EdgeDistanceMap& _edge_distance) :
51 g(&_g), node_potential(&_node_potential),
52 edge_distance(&_edge_distance) { }
53 bool operator[](const typename Graph::Edge& e) const {
54 return ((*node_potential)[g->head(e)] ==
55 (*edge_distance)[e]+(*node_potential)[g->tail(e)]);
61 #endif //HUGO_TIGHT_EDGE_FILTER_MAP_H