COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/tight_edge_filter_map.h @ 888:cc3590763f7f

Last change on this file since 888:cc3590763f7f was 888:cc3590763f7f, checked in by marci, 17 years ago
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 {
37      return ((*node_potential)[g->head(e)] ==
38              (*edge_distance)[e]+(*node_potential)[g->tail(e)]);
39    }
40  };
41
42} //namespace hugo
43
44#endif //HUGO_TIGHT_EDGE_FILTER_MAP_H
45
46
Note: See TracBrowser for help on using the repository browser.