1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/lemon/tight_edge_filter_map.h Wed Sep 29 15:30:04 2004 +0000
1.3 @@ -0,0 +1,63 @@
1.4 +/* -*- C++ -*-
1.5 + * src/hugo/tight_edge_filter_map.h - Part of HUGOlib, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
1.9 + *
1.10 + * Permission to use, modify and distribute this software is granted
1.11 + * provided that this copyright notice appears in all copies. For
1.12 + * precise terms see the accompanying LICENSE file.
1.13 + *
1.14 + * This software is provided "AS IS" with no warranty of any kind,
1.15 + * express or implied, and with no claim as to its suitability for any
1.16 + * purpose.
1.17 + *
1.18 + */
1.19 +
1.20 +#ifndef HUGO_TIGHT_EDGE_FILTER_MAP_H
1.21 +#define HUGO_TIGHT_EDGE_FILTER_MAP_H
1.22 +
1.23 +#include <hugo/maps.h>
1.24 +
1.25 +// /// \file
1.26 +// /// \brief Maximum flow algorithms.
1.27 +// /// \ingroup galgs
1.28 +
1.29 +namespace hugo {
1.30 +
1.31 + /// \brief A map for filtering the edge-set to those edges
1.32 + /// which are tight w.r.t. some node_potential map and
1.33 + /// edge_distance map.
1.34 + ///
1.35 + /// A node-map node_potential is said to be a potential w.r.t.
1.36 + /// an edge-map edge_distance
1.37 + /// if and only if for each edge e, node_potential[g.head(e)]
1.38 + /// <= edge_distance[e]+node_potential[g.tail(e)]
1.39 + /// (or the reverse inequality holds for each edge).
1.40 + /// An edge is said to be tight if this inequality holds with equality,
1.41 + /// and the map returns true exactly for those edges.
1.42 + /// To avoid rounding errors, it is recommended to use this class with exact
1.43 + /// types, e.g. with int.
1.44 + template<typename Graph,
1.45 + typename NodePotentialMap, typename EdgeDistanceMap>
1.46 + class TightEdgeFilterMap : public MapBase<typename Graph::Edge, bool> {
1.47 + protected:
1.48 + const Graph* g;
1.49 + NodePotentialMap* node_potential;
1.50 + EdgeDistanceMap* edge_distance;
1.51 + public:
1.52 + TightEdgeFilterMap(Graph& _g, NodePotentialMap& _node_potential,
1.53 + EdgeDistanceMap& _edge_distance) :
1.54 + g(&_g), node_potential(&_node_potential),
1.55 + edge_distance(&_edge_distance) { }
1.56 + bool operator[](const typename Graph::Edge& e) const {
1.57 + return ((*node_potential)[g->head(e)] ==
1.58 + (*edge_distance)[e]+(*node_potential)[g->tail(e)]);
1.59 + }
1.60 + };
1.61 +
1.62 +} //namespace hugo
1.63 +
1.64 +#endif //HUGO_TIGHT_EDGE_FILTER_MAP_H
1.65 +
1.66 +