source: lemon-0.x/demo/tight_edge_filter_map.h @ 1673:8919ca9e70f3

/* -*- C++ -*-
 * demo/tight_edge_filter_map.h - Part of LEMON, a generic C++ optimization
 * library
 *
 * Copyright (C) 2005 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 LEMON_TIGHT_EDGE_FILTER_MAP_H
#define LEMON_TIGHT_EDGE_FILTER_MAP_H

#include <lemon/maps.h>

// /// \file
// /// \brief Maximum flow algorithms.
// /// \ingroup galgs

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