# source:lemon-0.x/src/hugo/tight_edge_filter_map.h@910:5a89cacf17f1

Last change on this file since 910:5a89cacf17f1 was 910:5a89cacf17f1, checked in by marci, 18 years ago

minor corrections

File size: 2.1 KB
Line
1/* -*- C++ -*-
2 * src/hugo/tight_edge_filter_map.h - Part of HUGOlib, a generic C++ optimization library
3 *
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#ifndef HUGO_TIGHT_EDGE_FILTER_MAP_H
18#define HUGO_TIGHT_EDGE_FILTER_MAP_H
19
20#include <hugo/maps.h>
21
22// /// \file
23// /// \brief Maximum flow algorithms.
24// /// \ingroup galgs
25
26namespace hugo {
27
28  /// \brief A map for filtering the edge-set to those edges
29  /// which are tight w.r.t. some node_potential map and
30  /// edge_distance map.
31  ///
32  /// A node-map node_potential is said to be a potential w.r.t.
33  /// an edge-map edge_distance
34  /// if and only if for each edge e, node_potential[g.head(e)]
35  /// <= edge_distance[e]+node_potential[g.tail(e)]
36  /// (or the reverse inequality holds for each edge).
37  /// An edge is said to be tight if this inequality holds with equality,
38  /// and the map returns true exactly for those edges.
39  /// To avoid rounding errors, it is recommended to use this class with exact
40  /// types, e.g. with int.
41  template<typename Graph,
42           typename NodePotentialMap, typename EdgeDistanceMap>
43  class TightEdgeFilterMap : public MapBase<typename Graph::Edge, bool> {
44  protected:
45    const Graph* g;
46    NodePotentialMap* node_potential;
47    EdgeDistanceMap* edge_distance;
48  public:
49    TightEdgeFilterMap(Graph& _g, NodePotentialMap& _node_potential,
50                       EdgeDistanceMap& _edge_distance) :
51      g(&_g), node_potential(&_node_potential),
52      edge_distance(&_edge_distance) { }
53    bool operator[](const typename Graph::Edge& e) const {