/* -*- 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
/// \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
class TightEdgeFilterMap : public MapBase {
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