23 // /// \brief Maximum flow algorithms. |
23 // /// \brief Maximum flow algorithms. |
24 // /// \ingroup galgs |
24 // /// \ingroup galgs |
25 |
25 |
26 namespace lemon { |
26 namespace lemon { |
27 |
27 |
28 /// \brief A map for filtering the edge-set to those edges |
28 /*! |
29 /// which are tight w.r.t. some node_potential map and |
29 \brief A map for filtering the edge-set to those edges |
30 /// edge_distance map. |
30 which are tight w.r.t. a node-potential and |
31 /// |
31 edge-distance. |
32 /// A node-map node_potential is said to be a potential w.r.t. |
32 |
33 /// an edge-map edge_distance |
33 Let \f$G=(V,A)\f$ be a directed graph (graph for short) and |
34 /// if and only if for each edge e, node_potential[g.target(e)] |
34 let \f$\mathbb{F}\f$ be a number type. |
35 /// <= edge_distance[e]+node_potential[g.source(e)] |
35 Given a distance function |
36 /// (or the reverse inequality holds for each edge). |
36 \f$d:E\to\mathbb{F}\f$, |
37 /// An edge is said to be tight if this inequality holds with equality, |
37 \f$\pi:V\to\mathbb{F}\f$ is said to be a potetial |
38 /// and the map returns true exactly for those edges. |
38 w.r.t. \f$d\f$ |
39 /// To avoid rounding errors, it is recommended to use this class with exact |
39 if and only if |
40 /// types, e.g. with int. |
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 */ |
41 template<typename Graph, |
47 template<typename Graph, |
42 typename NodePotentialMap, typename EdgeDistanceMap> |
48 typename NodePotentialMap, typename EdgeDistanceMap> |
43 class TightEdgeFilterMap : public MapBase<typename Graph::Edge, bool> { |
49 class TightEdgeFilterMap : public MapBase<typename Graph::Edge, bool> { |
44 protected: |
50 protected: |
45 const Graph* g; |
51 const Graph* g; |