src/demo/tight_edge_filter_map.h
changeset 1345 71e0777b65e0
parent 1164 80bb73097736
child 1359 1581f961cfaa
equal deleted inserted replaced
3:e55390077ca7 4:d852650b40cd
    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;
    57   };
    63   };
    58 
    64 
    59 } //namespace lemon
    65 } //namespace lemon
    60 
    66 
    61 #endif //LEMON_TIGHT_EDGE_FILTER_MAP_H
    67 #endif //LEMON_TIGHT_EDGE_FILTER_MAP_H
    62 
       
    63