/* -*- C++ -*-

  *

  * This file is a part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2003-2008

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * precise terms see the accompanying LICENSE file.

  *

  * This software is provided "AS IS" with no warranty of any kind,

  * express or implied, and with no claim as to its suitability for any

  * purpose.

  *

  */

 #ifndef DEMO_TIGHT_EDGE_FILTER_MAP_H

 #define DEMO_TIGHT_EDGE_FILTER_MAP_H

 #include <lemon/maps.h>

 /// \file

 /// \brief Tight edge filter map.

 ///

 /// Tight edge filter map is bool map on the edges of the graph

 /// which filters the edges which are not tight for a node-potential.

 /// It is used in the \ref sub_graph_adaptor_demo.cc file. 

 ///

 /// \include tight_edge_filter_map.h

 namespace lemon {

   /// \brief A map for filtering the edge-set to those edges 

   /// which are tight w.r.t. a node-potential and 

   /// edge-distance.

   /// 

   /// Let \f$ G=(V,A) \f$ be a directed graph (graph for short) and 

   /// let \f$ \mathbb{F} \f$ be a number type. 

   /// Given a distance function 

   /// \f$ d:E\to\mathbb{F} \f$, 

   /// \f$ \pi:V\to\mathbb{F} \f$ is said to be a potetial 

   /// w.r.t. \f$ d \f$ 

   /// if and only if 

   /// \f$ \pi(v)\le d(uv)+\pi(u) \f$ holds for each edge \f$ uv\in E \f$ 

   /// (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 \c true exactly for those edges. 

   /// To avoid rounding errors, it is recommended to use this class with exact 

   /// number types, e.g. with \c int.

   template<typename Graph, 

 	   typename NodePotentialMap, typename EdgeDistanceMap>

   class TightEdgeFilterMap : public MapBase<typename Graph::Edge, bool> {

   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->target(e)] == 

 	      (*edge_distance)[e]+(*node_potential)[g->source(e)]);

     }

   };

 } //namespace lemon

 #endif //DEMO_TIGHT_EDGE_FILTER_MAP_H