COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/tight_edge_filter_map.h @ 906:17f31d280385

Last change on this file since 906:17f31d280385 was 906:17f31d280385, checked in by Alpar Juttner, 17 years ago

Copyright header added.

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// /// \file
21// /// \brief Maximum flow algorithms.
22// /// \ingroup galgs
23
24namespace hugo {
25
26  /// \brief A map for filtering the edge-set to those edges
27  /// which are tight w.r.t. some node_potential map and
28  /// edge_distance map.
29  ///
30  /// A node-map node_potential is said to be a potential w.r.t.
31  /// an edge-map edge_distance
32  /// if and only if for each edge e, node_potential[g.head(e)]
33  /// <= edge_distance[e]+node_potential[g.tail(e)]
34  /// (or the reverse inequality holds for each edge).
35  /// An edge is said to be tight if this inequality holds with equality,
36  /// and the map returns true exactly for those edges.
37  /// To avoid rounding errors, it is recommended to use this class with exact
38  /// types, e.g. with int.
39  template<typename Graph,
40           typename NodePotentialMap, typename EdgeDistanceMap>
41  class TightEdgeFilterMap {
42  protected:
43    const Graph* g;
44    NodePotentialMap* node_potential;
45    EdgeDistanceMap* edge_distance;
46  public:
47    TightEdgeFilterMap(Graph& _g, NodePotentialMap& _node_potential,
48                       EdgeDistanceMap& _edge_distance) :
49      g(&_g), node_potential(&_node_potential),
50      edge_distance(&_edge_distance) { }
51    bool operator[](const typename Graph::Edge& e) const {
52      return ((*node_potential)[g->head(e)] ==
53              (*edge_distance)[e]+(*node_potential)[g->tail(e)]);
54    }
55  };
56
57} //namespace hugo
58
59#endif //HUGO_TIGHT_EDGE_FILTER_MAP_H
60
61
Note: See TracBrowser for help on using the repository browser.