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