# source:lemon-0.x/src/work/marci/tight_edge_filter_map.h@863:d27bbe17b0b8

Last change on this file since 863:d27bbe17b0b8 was 863:d27bbe17b0b8, checked in by marci, 20 years ago

An edge-map which shows the tight edges w.r.t a potential and an edge-distance function.

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 {
37      return ((*node_potential)[g->head(e)] ==
38              (*edge_distance)[e]+(*node_potential)[g->tail(e)]);
39    }
40  };
41
[762]42} //namespace hugo
43
[863]44#endif //HUGO_TIGHT_EDGE_FILTER_MAP_H
[762]45
46
Note: See TracBrowser for help on using the repository browser.