1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/marci/tight_edge_filter_map.h Thu Sep 16 11:11:01 2004 +0000
1.3 @@ -0,0 +1,46 @@
1.4 +// -*- C++ -*-
1.5 +#ifndef HUGO_TIGHT_EDGE_FILTER_MAP_H
1.6 +#define HUGO_TIGHT_EDGE_FILTER_MAP_H
1.7 +
1.8 +// /// \file
1.9 +// /// \brief Maximum flow algorithms.
1.10 +// /// \ingroup galgs
1.11 +
1.12 +namespace hugo {
1.13 +
1.14 + /// \brief A map for filtering the edge-set to those edges
1.15 + /// which are tight w.r.t. some node_potential map and
1.16 + /// edge_distance map.
1.17 + ///
1.18 + /// A node-map node_potential is said to be a potential w.r.t.
1.19 + /// an edge-map edge_distance
1.20 + /// if and only if for each edge e, node_potential[g.head(e)]
1.21 + /// <= edge_distance[e]+node_potential[g.tail(e)]
1.22 + /// (or the reverse inequality holds for each edge).
1.23 + /// An edge is said to be tight if this inequality holds with equality,
1.24 + /// and the map returns true exactly for those edges.
1.25 + /// To avoid rounding errors, it is recommended to use this class with exact
1.26 + /// types, e.g. with int.
1.27 + template<typename Graph,
1.28 + typename NodePotentialMap, typename EdgeDistanceMap>
1.29 + class TightEdgeFilterMap {
1.30 + protected:
1.31 + const Graph* g;
1.32 + NodePotentialMap* node_potential;
1.33 + EdgeDistanceMap* edge_distance;
1.34 + public:
1.35 + TightEdgeFilterMap(Graph& _g, NodePotentialMap& _node_potential,
1.36 + EdgeDistanceMap& _edge_distance) :
1.37 + g(&_g), node_potential(&_node_potential),
1.38 + edge_distance(&_edge_distance) { }
1.39 + bool operator[](const typename Graph::Edge& e) const {
1.40 + return ((*node_potential)[g->head(e)] ==
1.41 + (*edge_distance)[e]+(*node_potential)[g->tail(e)]);
1.42 + }
1.43 + };
1.44 +
1.45 +} //namespace hugo
1.46 +
1.47 +#endif //HUGO_TIGHT_EDGE_FILTER_MAP_H
1.48 +
1.49 +