1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/demo/tight_edge_filter_map.h	Mon May 23 04:48:14 2005 +0000
     1.3 @@ -0,0 +1,68 @@
     1.4 +/* -*- C++ -*-
     1.5 + * demo/tight_edge_filter_map.h - Part of LEMON, a generic C++ optimization
     1.6 + * library
     1.7 + *
     1.8 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     1.9 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.10 + *
    1.11 + * Permission to use, modify and distribute this software is granted
    1.12 + * provided that this copyright notice appears in all copies. For
    1.13 + * precise terms see the accompanying LICENSE file.
    1.14 + *
    1.15 + * This software is provided "AS IS" with no warranty of any kind,
    1.16 + * express or implied, and with no claim as to its suitability for any
    1.17 + * purpose.
    1.18 + *
    1.19 + */
    1.20 +
    1.21 +#ifndef LEMON_TIGHT_EDGE_FILTER_MAP_H
    1.22 +#define LEMON_TIGHT_EDGE_FILTER_MAP_H
    1.23 +
    1.24 +#include <lemon/maps.h>
    1.25 +
    1.26 +// /// \file
    1.27 +// /// \brief Maximum flow algorithms.
    1.28 +// /// \ingroup galgs
    1.29 +
    1.30 +namespace lemon {
    1.31 +
    1.32 +  /*! 
    1.33 +    \brief A map for filtering the edge-set to those edges 
    1.34 +    which are tight w.r.t. a node-potential and 
    1.35 +    edge-distance.
    1.36 +    
    1.37 +    Let \f$G=(V,A)\f$ be a directed graph (graph for short) and 
    1.38 +    let \f$\mathbb{F}\f$ be a number type. 
    1.39 +    Given a distance function 
    1.40 +    \f$d:E\to\mathbb{F}\f$, 
    1.41 +    \f$\pi:V\to\mathbb{F}\f$ is said to be a potetial 
    1.42 +    w.r.t. \f$d\f$ 
    1.43 +    if and only if 
    1.44 +    \f$\pi(v)\le d(uv)+\pi(u)\f$ holds for each edge \f$uv\in E\f$ 
    1.45 +    (or the reverse inequality holds for each edge). 
    1.46 +    An edge is said to be tight if this inequality holds with equality, 
    1.47 +    and the map returns \c true exactly for those edges. 
    1.48 +    To avoid rounding errors, it is recommended to use this class with exact 
    1.49 +    number types, e.g. with \c int.
    1.50 +  */
    1.51 +  template<typename Graph, 
    1.52 +	   typename NodePotentialMap, typename EdgeDistanceMap>
    1.53 +  class TightEdgeFilterMap : public MapBase<typename Graph::Edge, bool> {
    1.54 +  protected:
    1.55 +    const Graph* g;
    1.56 +    NodePotentialMap* node_potential;
    1.57 +    EdgeDistanceMap* edge_distance;
    1.58 +  public:
    1.59 +    TightEdgeFilterMap(Graph& _g, NodePotentialMap& _node_potential, 
    1.60 +		       EdgeDistanceMap& _edge_distance) : 
    1.61 +      g(&_g), node_potential(&_node_potential), 
    1.62 +      edge_distance(&_edge_distance) { }
    1.63 +    bool operator[](const typename Graph::Edge& e) const {
    1.64 +      return ((*node_potential)[g->target(e)] == 
    1.65 +	      (*edge_distance)[e]+(*node_potential)[g->source(e)]);
    1.66 +    }
    1.67 +  };
    1.68 +
    1.69 +} //namespace lemon
    1.70 +
    1.71 +#endif //LEMON_TIGHT_EDGE_FILTER_MAP_H