COIN-OR::LEMON - Graph Library

Ignore:
Timestamp:
09/16/04 13:11:01 (17 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1163
Message:

An edge-map which shows the tight edges w.r.t a potential and an edge-distance function.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci/augmenting_flow.h

    r862 r863  
    44
    55#include <vector>
    6 //#include <queue>
    7 //#include <stack>
    86#include <iostream>
    97
     
    1210#include <hugo/invalid.h>
    1311#include <hugo/maps.h>
     12#include <tight_edge_filter_map.h>
    1413
    1514/// \file
     
    1817
    1918namespace hugo {
    20 
    21   /// \brief A map for filtering the edge-set to those edges
    22   /// which are tight w.r.t. some node_potential map and
    23   /// edge_distance map.
    24   ///
    25   /// A node-map node_potential is said to be a potential w.r.t.
    26   /// an edge-map edge_distance
    27   /// if and only if for each edge e, node_potential[g.head(e)]
    28   /// <= edge_distance[e]+node_potential[g.tail(e)]
    29   /// (or the reverse inequality holds for each edge).
    30   /// An edge is said to be tight if this inequality holds with equality,
    31   /// and the map returns true exactly for those edges.
    32   /// To avoid rounding errors, it is recommended to use this class with exact
    33   /// types, e.g. with int.
    34   template<typename Graph,
    35            typename NodePotentialMap, typename EdgeDistanceMap>
    36   class TightEdgeFilterMap {
    37   protected:
    38     const Graph* g;
    39     NodePotentialMap* node_potential;
    40     EdgeDistanceMap* edge_distance;
    41   public:
    42     TightEdgeFilterMap(Graph& _g, NodePotentialMap& _node_potential,
    43                        EdgeDistanceMap& _edge_distance) :
    44       g(&_g), node_potential(&_node_potential),
    45       edge_distance(&_edge_distance) { }
    46 //     void set(const typename Graph::Node& n, int a) {
    47 //       pot->set(n, a);
    48 //     }
    49 //     int operator[](const typename Graph::Node& n) const {
    50 //       return (*node_potential)[n];
    51 //     }
    52     bool operator[](const typename Graph::Edge& e) const {
    53       return ((*node_potential)[g->head(e)] ==
    54               (*edge_distance)[e]+(*node_potential)[g->tail(e)]);
    55     }
    56   };
    5719
    5820  /// \addtogroup galgs
Note: See TracChangeset for help on using the changeset viewer.