# source:lemon-0.x/src/demo/tight_edge_filter_map.h@879:5e284075b193

Last change on this file since 879:5e284075b193 was 868:805963ea8654, checked in by marci, 19 years ago

This is needed for the demo.

File size: 1.5 KB
Line
1// -*- C++ -*-
2#ifndef HUGO_TIGHT_EDGE_FILTER_MAP_H
3#define HUGO_TIGHT_EDGE_FILTER_MAP_H
4
5// /// \file
6// /// \brief Maximum flow algorithms.
7// /// \ingroup galgs
8
9namespace hugo {
10
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 {