COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/demo/tight_edge_filter_map.h @ 1295:02a403c305b9

Last change on this file since 1295:02a403c305b9 was 1276:b143e42c44de, checked in by marci, 19 years ago

latex documentation for TightEdgeFilterMap?, including amsmath and amssymb latex
packages for latex documentation

File size: 2.2 KB
Line 
1/* -*- C++ -*-
2 * src/lemon/tight_edge_filter_map.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 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  /*!
29    \brief A map for filtering the edge-set to those edges
30    which are tight w.r.t. a node-potential and
31    edge-distance.
32   
33    Let \f$G=(V,A)\f$ be a directed graph (graph for short) and
34    let \f$\mathbb{F}\f$ be a number type.
35    Given a distance function
36    \f$d:E\to\mathbb{F}\f$,
37    \f$\pi:V\to\mathbb{F}\f$ is said to be a potetial
38    w.r.t. \f$d\f$
39    if and only if
40    \f$\pi(v)\le d(uv)+\pi(u)\f$ holds for each edge \f$uv\in E\f$
41    (or the reverse inequality holds for each edge).
42    An edge is said to be tight if this inequality holds with equality,
43    and the map returns \c true exactly for those edges.
44    To avoid rounding errors, it is recommended to use this class with exact
45    number types, e.g. with \c int.
46  */
47  template<typename Graph,
48           typename NodePotentialMap, typename EdgeDistanceMap>
49  class TightEdgeFilterMap : public MapBase<typename Graph::Edge, bool> {
50  protected:
51    const Graph* g;
52    NodePotentialMap* node_potential;
53    EdgeDistanceMap* edge_distance;
54  public:
55    TightEdgeFilterMap(Graph& _g, NodePotentialMap& _node_potential,
56                       EdgeDistanceMap& _edge_distance) :
57      g(&_g), node_potential(&_node_potential),
58      edge_distance(&_edge_distance) { }
59    bool operator[](const typename Graph::Edge& e) const {
60      return ((*node_potential)[g->target(e)] ==
61              (*edge_distance)[e]+(*node_potential)[g->source(e)]);
62    }
63  };
64
65} //namespace lemon
66
67#endif //LEMON_TIGHT_EDGE_FILTER_MAP_H
Note: See TracBrowser for help on using the repository browser.