source: lemon-0.x/src/hugo/tight_edge_filter_map.h @ 906:17f31d280385

/* -*- C++ -*-
 * src/hugo/tight_edge_filter_map.h - Part of HUGOlib, a generic C++ optimization library
 *
 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Combinatorial Optimization Research Group, 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 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