Changeset 1276:b143e42c44de in lemon-0.x for src/demo
- Timestamp:
- 03/30/05 16:29:11 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1708
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
TabularUnified src/demo/tight_edge_filter_map.h ¶
r1164 r1276 26 26 namespace lemon { 27 27 28 /// \brief A map for filtering the edge-set to those edges 29 /// which are tight w.r.t. some node_potential map and 30 /// edge_distance map. 31 /// 32 /// A node-map node_potential is said to be a potential w.r.t. 33 /// an edge-map edge_distance 34 /// if and only if for each edge e, node_potential[g.target(e)] 35 /// <= edge_distance[e]+node_potential[g.source(e)] 36 /// (or the reverse inequality holds for each edge). 37 /// An edge is said to be tight if this inequality holds with equality, 38 /// and the map returns true exactly for those edges. 39 /// To avoid rounding errors, it is recommended to use this class with exact 40 /// types, e.g. with int. 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 */ 41 47 template<typename Graph, 42 48 typename NodePotentialMap, typename EdgeDistanceMap> … … 60 66 61 67 #endif //LEMON_TIGHT_EDGE_FILTER_MAP_H 62 63
Note: See TracChangeset
for help on using the changeset viewer.