# source:lemon-0.x/demo/tight_edge_filter_map.h@2042:bdc953f2a449

Last change on this file since 2042:bdc953f2a449 was 2042:bdc953f2a449, checked in by Balazs Dezso, 14 years ago

New Algorithm group for matchings

LaTeX formulas
Bug fix => /\f$will cause parsing error in doxygen File size: 2.2 KB Line 1/* -*- C++ -*- 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 4 * 5 * Copyright (C) 2003-2006 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). 8 * 9 * Permission to use, modify and distribute this software is granted 10 * provided that this copyright notice appears in all copies. For 11 * precise terms see the accompanying LICENSE file. 12 * 13 * This software is provided "AS IS" with no warranty of any kind, 14 * express or implied, and with no claim as to its suitability for any 15 * purpose. 16 * 17 */ 18 19#ifndef LEMON_TIGHT_EDGE_FILTER_MAP_H 20#define LEMON_TIGHT_EDGE_FILTER_MAP_H 21 22#include <lemon/maps.h> 23 24// /// \file 25// /// \brief Maximum flow algorithms. 26// /// \ingroup galgs 27 28namespace lemon { 29 30 /*! 31 \brief A map for filtering the edge-set to those edges 32 which are tight w.r.t. a node-potential and 33 edge-distance. 34 35 Let \f$ G=(V,A) \f$be a directed graph (graph for short) and 36 let \f$ \mathbb{F} \f$be a number type. 37 Given a distance function 38 \f$ d:E\to\mathbb{F} \f$, 39 \f$ \pi:V\to\mathbb{F} \f$is said to be a potetial 40 w.r.t. \f$ d \f$41 if and only if 42 \f$ \pi(v)\le d(uv)+\pi(u) \f$holds for each edge \f$ uv\in E \f\$
43    (or the reverse inequality holds for each edge).
44    An edge is said to be tight if this inequality holds with equality,
45    and the map returns \c true exactly for those edges.
46    To avoid rounding errors, it is recommended to use this class with exact
47    number types, e.g. with \c int.
48  */
49  template<typename Graph,
50           typename NodePotentialMap, typename EdgeDistanceMap>
51  class TightEdgeFilterMap : public MapBase<typename Graph::Edge, bool> {
52  protected:
53    const Graph* g;
54    NodePotentialMap* node_potential;
55    EdgeDistanceMap* edge_distance;
56  public:
57    TightEdgeFilterMap(Graph& _g, NodePotentialMap& _node_potential,
58                       EdgeDistanceMap& _edge_distance) :
59      g(&_g), node_potential(&_node_potential),
60      edge_distance(&_edge_distance) { }
61    bool operator[](const typename Graph::Edge& e) const {
62      return ((*node_potential)[g->target(e)] ==
63              (*edge_distance)[e]+(*node_potential)[g->source(e)]);
64    }
65  };
66
67} //namespace lemon
68
69#endif //LEMON_TIGHT_EDGE_FILTER_MAP_H
Note: See TracBrowser for help on using the repository browser.