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