COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/attic/tight_edge_filter_map.h @ 919:6153d9cf78c6

Last change on this file since 919:6153d9cf78c6 was 919:6153d9cf78c6, checked in by Alpar Juttner, 20 years ago
  • Backport -r1227 and -r1220
  • Temporarily remove (move to attic) tight_edge_filter.h
File size: 2.1 KB
RevLine 
[906]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
[888]17#ifndef HUGO_TIGHT_EDGE_FILTER_MAP_H
18#define HUGO_TIGHT_EDGE_FILTER_MAP_H
19
[910]20#include <hugo/maps.h>
21
[888]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>
[910]43  class TightEdgeFilterMap : public MapBase<typename Graph::Edge, bool> {
[888]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 {
54      return ((*node_potential)[g->head(e)] ==
55              (*edge_distance)[e]+(*node_potential)[g->tail(e)]);
56    }
57  };
58
59} //namespace hugo
60
61#endif //HUGO_TIGHT_EDGE_FILTER_MAP_H
62
63
Note: See TracBrowser for help on using the repository browser.