2 #ifndef HUGO_TIGHT_EDGE_FILTER_MAP_H
3 #define HUGO_TIGHT_EDGE_FILTER_MAP_H
6 // /// \brief Maximum flow algorithms.
11 /// \brief A map for filtering the edge-set to those edges
12 /// which are tight w.r.t. some node_potential map and
13 /// edge_distance map.
15 /// A node-map node_potential is said to be a potential w.r.t.
16 /// an edge-map edge_distance
17 /// if and only if for each edge e, node_potential[g.head(e)]
18 /// <= edge_distance[e]+node_potential[g.tail(e)]
19 /// (or the reverse inequality holds for each edge).
20 /// An edge is said to be tight if this inequality holds with equality,
21 /// and the map returns true exactly for those edges.
22 /// To avoid rounding errors, it is recommended to use this class with exact
23 /// types, e.g. with int.
24 template<typename Graph,
25 typename NodePotentialMap, typename EdgeDistanceMap>
26 class TightEdgeFilterMap {
29 NodePotentialMap* node_potential;
30 EdgeDistanceMap* edge_distance;
32 TightEdgeFilterMap(Graph& _g, NodePotentialMap& _node_potential,
33 EdgeDistanceMap& _edge_distance) :
34 g(&_g), node_potential(&_node_potential),
35 edge_distance(&_edge_distance) { }
36 bool operator[](const typename Graph::Edge& e) const {
37 return ((*node_potential)[g->head(e)] ==
38 (*edge_distance)[e]+(*node_potential)[g->tail(e)]);
44 #endif //HUGO_TIGHT_EDGE_FILTER_MAP_H