/* -*- 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