1 | // -*- C++ -*- |
---|

2 | #ifndef HUGO_TIGHT_EDGE_FILTER_MAP_H |
---|

3 | #define HUGO_TIGHT_EDGE_FILTER_MAP_H |
---|

4 | |
---|

5 | // /// \file |
---|

6 | // /// \brief Maximum flow algorithms. |
---|

7 | // /// \ingroup galgs |
---|

8 | |
---|

9 | namespace hugo { |
---|

10 | |
---|

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. |
---|

14 | /// |
---|

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 { |
---|

27 | protected: |
---|

28 | const Graph* g; |
---|

29 | NodePotentialMap* node_potential; |
---|

30 | EdgeDistanceMap* edge_distance; |
---|

31 | public: |
---|

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)]); |
---|

39 | } |
---|

40 | }; |
---|

41 | |
---|

42 | } //namespace hugo |
---|

43 | |
---|

44 | #endif //HUGO_TIGHT_EDGE_FILTER_MAP_H |
---|

45 | |
---|

46 | |
---|