COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/demo/tight_edge_filter_map.h @ 1087:d496d1d5a5e7

Last change on this file since 1087:d496d1d5a5e7 was 986:e997802b855c, checked in by Alpar Juttner, 19 years ago

Naming changes:

  • head -> target
  • tail -> source
File size: 2.1 KB
Line 
1/* -*- C++ -*-
2 * src/lemon/tight_edge_filter_map.h - Part of LEMON, 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 LEMON_TIGHT_EDGE_FILTER_MAP_H
18#define LEMON_TIGHT_EDGE_FILTER_MAP_H
19
20#include <lemon/maps.h>
21
22// /// \file
23// /// \brief Maximum flow algorithms.
24// /// \ingroup galgs
25
26namespace lemon {
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.target(e)]
35  /// <= edge_distance[e]+node_potential[g.source(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 {
54      return ((*node_potential)[g->target(e)] ==
55              (*edge_distance)[e]+(*node_potential)[g->source(e)]);
56    }
57  };
58
59} //namespace lemon
60
61#endif //LEMON_TIGHT_EDGE_FILTER_MAP_H
62
63
Note: See TracBrowser for help on using the repository browser.