# source:lemon-0.x/src/demo/tight_edge_filter_map.h@868:805963ea8654

Last change on this file since 868:805963ea8654 was 868:805963ea8654, checked in by marci, 18 years ago

This is needed for the demo.

File size: 1.5 KB
RevLine
[762]1// -*- C++ -*-
[863]2#ifndef HUGO_TIGHT_EDGE_FILTER_MAP_H
3#define HUGO_TIGHT_EDGE_FILTER_MAP_H
[762]4
[863]5// /// \file
6// /// \brief Maximum flow algorithms.
7// /// \ingroup galgs
[762]8
9namespace hugo {
10
[862]11  /// \brief A map for filtering the edge-set to those edges
12  /// which are tight w.r.t. some node_potential map and
13  /// edge_distance map.
14  ///
15  /// A node-map node_potential is said to be a potential w.r.t.
16  /// an edge-map edge_distance
17  /// if and only if for each edge e, node_potential[g.head(e)]
18  /// <= edge_distance[e]+node_potential[g.tail(e)]
19  /// (or the reverse inequality holds for each edge).
20  /// An edge is said to be tight if this inequality holds with equality,
21  /// and the map returns true exactly for those edges.
22  /// To avoid rounding errors, it is recommended to use this class with exact
23  /// types, e.g. with int.
24  template<typename Graph,
25           typename NodePotentialMap, typename EdgeDistanceMap>
26  class TightEdgeFilterMap {
27  protected:
28    const Graph* g;
29    NodePotentialMap* node_potential;
30    EdgeDistanceMap* edge_distance;
31  public:
32    TightEdgeFilterMap(Graph& _g, NodePotentialMap& _node_potential,
33                       EdgeDistanceMap& _edge_distance) :
34      g(&_g), node_potential(&_node_potential),
35      edge_distance(&_edge_distance) { }
36    bool operator[](const typename Graph::Edge& e) const {