COIN-OR::LEMON - Graph Library

source: lemon-0.x/demo/tight_edge_filter_map.h @ 1637:9d64d5672b88

Last change on this file since 1637:9d64d5672b88 was 1435:8e85e6bbefdf, checked in by Akos Ladanyi, 19 years ago

trunk/src/* move to trunk/

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) 2005 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.