source: lemon-0.x/demo/tight_edge_filter_map.h

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