1.1 --- a/src/lemon/tight_edge_filter_map.h Wed Sep 29 15:30:04 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,63 +0,0 @@
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 -