// -*- 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<typename Graph, 

	   typename NodePotentialMap, typename EdgeDistanceMap>

  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