14 * express or implied, and with no claim as to its suitability for any |
14 * express or implied, and with no claim as to its suitability for any |
15 * purpose. |
15 * purpose. |
16 * |
16 * |
17 */ |
17 */ |
18 |
18 |
19 #ifndef LEMON_TIGHT_EDGE_FILTER_MAP_H |
19 #ifndef DEMO_TIGHT_EDGE_FILTER_MAP_H |
20 #define LEMON_TIGHT_EDGE_FILTER_MAP_H |
20 #define DEMO_TIGHT_EDGE_FILTER_MAP_H |
21 |
21 |
22 #include <lemon/maps.h> |
22 #include <lemon/maps.h> |
23 |
23 |
24 // /// \file |
24 /// \file |
25 // /// \brief Maximum flow algorithms. |
25 /// \brief Tight edge filter map. |
26 // /// \ingroup galgs |
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 |
27 |
32 |
28 namespace lemon { |
33 namespace lemon { |
29 |
34 |
30 /*! |
35 /// \brief A map for filtering the edge-set to those edges |
31 \brief A map for filtering the edge-set to those edges |
36 /// which are tight w.r.t. a node-potential and |
32 which are tight w.r.t. a node-potential and |
37 /// edge-distance. |
33 edge-distance. |
38 /// |
34 |
39 /// Let \f$ G=(V,A) \f$ be a directed graph (graph for short) and |
35 Let \f$ G=(V,A) \f$ be a directed graph (graph for short) and |
40 /// let \f$ \mathbb{F} \f$ be a number type. |
36 let \f$ \mathbb{F} \f$ be a number type. |
41 /// Given a distance function |
37 Given a distance function |
42 /// \f$ d:E\to\mathbb{F} \f$, |
38 \f$ d:E\to\mathbb{F} \f$, |
43 /// \f$ \pi:V\to\mathbb{F} \f$ is said to be a potetial |
39 \f$ \pi:V\to\mathbb{F} \f$ is said to be a potetial |
44 /// w.r.t. \f$ d \f$ |
40 w.r.t. \f$ d \f$ |
45 /// if and only if |
41 if and only if |
46 /// \f$ \pi(v)\le d(uv)+\pi(u) \f$ holds for each edge \f$ uv\in E \f$ |
42 \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). |
43 (or the reverse inequality holds for each edge). |
48 /// An edge is said to be tight if this inequality holds with equality, |
44 An edge is said to be tight if this inequality holds with equality, |
49 /// and the map returns \c true exactly for those edges. |
45 and the map returns \c true exactly for those edges. |
50 /// To avoid rounding errors, it is recommended to use this class with exact |
46 To avoid rounding errors, it is recommended to use this class with exact |
51 /// number types, e.g. with \c int. |
47 number types, e.g. with \c int. |
|
48 */ |
|
49 template<typename Graph, |
52 template<typename Graph, |
50 typename NodePotentialMap, typename EdgeDistanceMap> |
53 typename NodePotentialMap, typename EdgeDistanceMap> |
51 class TightEdgeFilterMap : public MapBase<typename Graph::Edge, bool> { |
54 class TightEdgeFilterMap : public MapBase<typename Graph::Edge, bool> { |
52 protected: |
55 protected: |
53 const Graph* g; |
56 const Graph* g; |