// -*- C++ -*- #ifndef HUGO_TIGHT_EDGE_FILTER_MAP_H #define HUGO_TIGHT_EDGE_FILTER_MAP_H // /// \file // /// \brief Maximum flow algorithms. // /// \ingroup galgs namespace hugo { /// \brief A map for filtering the edge-set to those edges /// which are tight w.r.t. some node_potential map and /// edge_distance map. /// /// A node-map node_potential is said to be a potential w.r.t. /// an edge-map edge_distance /// if and only if for each edge e, node_potential[g.head(e)] /// <= edge_distance[e]+node_potential[g.tail(e)] /// (or the reverse inequality holds for each edge). /// An edge is said to be tight if this inequality holds with equality, /// and the map returns true exactly for those edges. /// To avoid rounding errors, it is recommended to use this class with exact /// types, e.g. with int. template class TightEdgeFilterMap { protected: const Graph* g; NodePotentialMap* node_potential; EdgeDistanceMap* edge_distance; public: TightEdgeFilterMap(Graph& _g, NodePotentialMap& _node_potential, EdgeDistanceMap& _edge_distance) : g(&_g), node_potential(&_node_potential), edge_distance(&_edge_distance) { } bool operator[](const typename Graph::Edge& e) const { return ((*node_potential)[g->head(e)] == (*edge_distance)[e]+(*node_potential)[g->tail(e)]); } }; } //namespace hugo #endif //HUGO_TIGHT_EDGE_FILTER_MAP_H