30 /*! |
30 /*! |
31 \brief A map for filtering the edge-set to those edges |
31 \brief A map for filtering the edge-set to those edges |
32 which are tight w.r.t. a node-potential and |
32 which are tight w.r.t. a node-potential and |
33 edge-distance. |
33 edge-distance. |
34 |
34 |
35 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 |
36 let \f$\mathbb{F}\f$ be a number type. |
36 let \f$ \mathbb{F} \f$ be a number type. |
37 Given a distance function |
37 Given a distance function |
38 \f$d:E\to\mathbb{F}\f$, |
38 \f$ d:E\to\mathbb{F} \f$, |
39 \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 |
40 w.r.t. \f$d\f$ |
40 w.r.t. \f$ d \f$ |
41 if and only if |
41 if and only if |
42 \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$ |
43 (or the reverse inequality holds for each edge). |
43 (or the reverse inequality holds for each edge). |
44 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, |
45 and the map returns \c true exactly for those edges. |
45 and the map returns \c true exactly for those edges. |
46 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 |
47 number types, e.g. with \c int. |
47 number types, e.g. with \c int. |