COIN-OR::LEMON - Graph Library

source: lemon-0.x/demo/tight_edge_filter_map.h @ 1922:1ee37068316b

Last change on this file since 1922:1ee37068316b was 1875:98698b69a902, checked in by Alpar Juttner, 14 years ago

Happy new year to LEMON

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