# HG changeset patch # User marci # Date 1096560500 0 # Node ID 882790531532084ca5aa46476d604b4c35767693 # Parent 71dc900ee30f95efebcd329b209a7d51f1b5dd5b mv after 0.2 diff -r 71dc900ee30f -r 882790531532 src/demo/tight_edge_filter_map.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/demo/tight_edge_filter_map.h Thu Sep 30 16:08:20 2004 +0000 @@ -0,0 +1,63 @@ +/* -*- C++ -*- + * src/lemon/tight_edge_filter_map.h - Part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Combinatorial Optimization Research Group, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#ifndef LEMON_TIGHT_EDGE_FILTER_MAP_H +#define LEMON_TIGHT_EDGE_FILTER_MAP_H + +#include + +// /// \file +// /// \brief Maximum flow algorithms. +// /// \ingroup galgs + +namespace lemon { + + /// \brief A map for filtering the edge-set to those edges + /// which are tight w.r.t. some node_potential map and + /// edge_distance map. + /// + /// A node-map node_potential is said to be a potential w.r.t. + /// an edge-map edge_distance + /// if and only if for each edge e, node_potential[g.head(e)] + /// <= edge_distance[e]+node_potential[g.tail(e)] + /// (or the reverse inequality holds for each edge). + /// An edge is said to be tight if this inequality holds with equality, + /// and the map returns true exactly for those edges. + /// To avoid rounding errors, it is recommended to use this class with exact + /// types, e.g. with int. + template + class TightEdgeFilterMap : public MapBase { + protected: + const Graph* g; + NodePotentialMap* node_potential; + EdgeDistanceMap* edge_distance; + public: + TightEdgeFilterMap(Graph& _g, NodePotentialMap& _node_potential, + EdgeDistanceMap& _edge_distance) : + g(&_g), node_potential(&_node_potential), + edge_distance(&_edge_distance) { } + bool operator[](const typename Graph::Edge& e) const { + return ((*node_potential)[g->head(e)] == + (*edge_distance)[e]+(*node_potential)[g->tail(e)]); + } + }; + +} //namespace lemon + +#endif //LEMON_TIGHT_EDGE_FILTER_MAP_H + + diff -r 71dc900ee30f -r 882790531532 src/lemon/attic/tight_edge_filter_map.h --- a/src/lemon/attic/tight_edge_filter_map.h Thu Sep 30 10:15:52 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,63 +0,0 @@ -/* -*- C++ -*- - * src/lemon/tight_edge_filter_map.h - Part of LEMON, a generic C++ optimization library - * - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport - * (Egervary Combinatorial Optimization Research Group, EGRES). - * - * Permission to use, modify and distribute this software is granted - * provided that this copyright notice appears in all copies. For - * precise terms see the accompanying LICENSE file. - * - * This software is provided "AS IS" with no warranty of any kind, - * express or implied, and with no claim as to its suitability for any - * purpose. - * - */ - -#ifndef LEMON_TIGHT_EDGE_FILTER_MAP_H -#define LEMON_TIGHT_EDGE_FILTER_MAP_H - -#include - -// /// \file -// /// \brief Maximum flow algorithms. -// /// \ingroup galgs - -namespace lemon { - - /// \brief A map for filtering the edge-set to those edges - /// which are tight w.r.t. some node_potential map and - /// edge_distance map. - /// - /// A node-map node_potential is said to be a potential w.r.t. - /// an edge-map edge_distance - /// if and only if for each edge e, node_potential[g.head(e)] - /// <= edge_distance[e]+node_potential[g.tail(e)] - /// (or the reverse inequality holds for each edge). - /// An edge is said to be tight if this inequality holds with equality, - /// and the map returns true exactly for those edges. - /// To avoid rounding errors, it is recommended to use this class with exact - /// types, e.g. with int. - template - class TightEdgeFilterMap : public MapBase { - protected: - const Graph* g; - NodePotentialMap* node_potential; - EdgeDistanceMap* edge_distance; - public: - TightEdgeFilterMap(Graph& _g, NodePotentialMap& _node_potential, - EdgeDistanceMap& _edge_distance) : - g(&_g), node_potential(&_node_potential), - edge_distance(&_edge_distance) { } - bool operator[](const typename Graph::Edge& e) const { - return ((*node_potential)[g->head(e)] == - (*edge_distance)[e]+(*node_potential)[g->tail(e)]); - } - }; - -} //namespace lemon - -#endif //LEMON_TIGHT_EDGE_FILTER_MAP_H - -