# source:lemon-0.x/demo/tight_edge_filter_map.h

Last change on this file was 2553:bfced05fa852, checked in by Alpar Juttner, 14 years ago

File size: 2.5 KB
Line
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef DEMO_TIGHT_EDGE_FILTER_MAP_H
20#define DEMO_TIGHT_EDGE_FILTER_MAP_H
21
22#include <lemon/maps.h>
23
24/// \file
25/// \brief Tight edge filter map.
26///
27/// Tight edge filter map is bool map on the edges of the graph
28/// which filters the edges which are not tight for a node-potential.
29/// It is used in the \ref sub_graph_adaptor_demo.cc file.
30///
31/// \include tight_edge_filter_map.h
32
33namespace lemon {
34
35  /// \brief A map for filtering the edge-set to those edges
36  /// which are tight w.r.t. a node-potential and
37  /// edge-distance.
38  ///
39  /// Let \f$G=(V,A) \f$ be a directed graph (graph for short) and
40  /// let \f$\mathbb{F} \f$ be a number type.
41  /// Given a distance function
42  /// \f$d:E\to\mathbb{F} \f$,
43  /// \f$\pi:V\to\mathbb{F} \f$ is said to be a potetial
44  /// w.r.t. \f$d \f$
45  /// if and only if
46  /// \f$\pi(v)\le d(uv)+\pi(u) \f$ holds for each edge \f$uv\in E \f$
47  /// (or the reverse inequality holds for each edge).
48  /// An edge is said to be tight if this inequality holds with equality,
49  /// and the map returns \c true exactly for those edges.
50  /// To avoid rounding errors, it is recommended to use this class with exact
51  /// number types, e.g. with \c int.
52  template<typename Graph,
53           typename NodePotentialMap, typename EdgeDistanceMap>
54  class TightEdgeFilterMap : public MapBase<typename Graph::Edge, bool> {
55  protected:
56    const Graph* g;
57    NodePotentialMap* node_potential;
58    EdgeDistanceMap* edge_distance;
59  public:
60    TightEdgeFilterMap(Graph& _g, NodePotentialMap& _node_potential,
61                       EdgeDistanceMap& _edge_distance) :
62      g(&_g), node_potential(&_node_potential),
63      edge_distance(&_edge_distance) { }
64    bool operator[](const typename Graph::Edge& e) const {
65      return ((*node_potential)[g->target(e)] ==
66              (*edge_distance)[e]+(*node_potential)[g->source(e)]);
67    }
68  };
69
70} //namespace lemon
71
72#endif //DEMO_TIGHT_EDGE_FILTER_MAP_H
Note: See TracBrowser for help on using the repository browser.