1.1 --- a/src/work/marci/augmenting_flow.h	Thu Sep 16 10:59:52 2004 +0000
     1.2 +++ b/src/work/marci/augmenting_flow.h	Thu Sep 16 11:11:01 2004 +0000
     1.3 @@ -3,14 +3,13 @@
     1.4  #define HUGO_AUGMENTING_FLOW_H
     1.5  
     1.6  #include <vector>
     1.7 -//#include <queue>
     1.8 -//#include <stack>
     1.9  #include <iostream>
    1.10  
    1.11  #include <hugo/graph_wrapper.h>
    1.12  #include <bfs_dfs.h>
    1.13  #include <hugo/invalid.h>
    1.14  #include <hugo/maps.h>
    1.15 +#include <tight_edge_filter_map.h>
    1.16  
    1.17  /// \file
    1.18  /// \brief Maximum flow algorithms.
    1.19 @@ -18,43 +17,6 @@
    1.20  
    1.21  namespace hugo {
    1.22  
    1.23 -  /// \brief A map for filtering the edge-set to those edges 
    1.24 -  /// which are tight w.r.t. some node_potential map and 
    1.25 -  /// edge_distance map.
    1.26 -  ///
    1.27 -  /// A node-map node_potential is said to be a potential w.r.t. 
    1.28 -  /// an edge-map edge_distance 
    1.29 -  /// if and only if for each edge e, node_potential[g.head(e)] 
    1.30 -  /// <= edge_distance[e]+node_potential[g.tail(e)] 
    1.31 -  /// (or the reverse inequality holds for each edge).
    1.32 -  /// An edge is said to be tight if this inequality holds with equality, 
    1.33 -  /// and the map returns true exactly for those edges.
    1.34 -  /// To avoid rounding errors, it is recommended to use this class with exact 
    1.35 -  /// types, e.g. with int.
    1.36 -  template<typename Graph, 
    1.37 -	   typename NodePotentialMap, typename EdgeDistanceMap>
    1.38 -  class TightEdgeFilterMap {
    1.39 -  protected:
    1.40 -    const Graph* g;
    1.41 -    NodePotentialMap* node_potential;
    1.42 -    EdgeDistanceMap* edge_distance;
    1.43 -  public:
    1.44 -    TightEdgeFilterMap(Graph& _g, NodePotentialMap& _node_potential, 
    1.45 -		       EdgeDistanceMap& _edge_distance) : 
    1.46 -      g(&_g), node_potential(&_node_potential), 
    1.47 -      edge_distance(&_edge_distance) { }
    1.48 -//     void set(const typename Graph::Node& n, int a) {
    1.49 -//       pot->set(n, a);
    1.50 -//     }
    1.51 -//     int operator[](const typename Graph::Node& n) const { 
    1.52 -//       return (*node_potential)[n]; 
    1.53 -//     }
    1.54 -    bool operator[](const typename Graph::Edge& e) const {
    1.55 -      return ((*node_potential)[g->head(e)] == 
    1.56 -	      (*edge_distance)[e]+(*node_potential)[g->tail(e)]);
    1.57 -    }
    1.58 -  };
    1.59 -
    1.60    /// \addtogroup galgs
    1.61    /// @{                                                                                                                                        
    1.62    /// Class for augmenting path flow algorithms.

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/src/work/marci/tight_edge_filter_map.h	Thu Sep 16 11:11:01 2004 +0000
     2.3 @@ -0,0 +1,46 @@
     2.4 +// -*- C++ -*-
     2.5 +#ifndef HUGO_TIGHT_EDGE_FILTER_MAP_H
     2.6 +#define HUGO_TIGHT_EDGE_FILTER_MAP_H
     2.7 +
     2.8 +// /// \file
     2.9 +// /// \brief Maximum flow algorithms.
    2.10 +// /// \ingroup galgs
    2.11 +
    2.12 +namespace hugo {
    2.13 +
    2.14 +  /// \brief A map for filtering the edge-set to those edges 
    2.15 +  /// which are tight w.r.t. some node_potential map and 
    2.16 +  /// edge_distance map.
    2.17 +  ///
    2.18 +  /// A node-map node_potential is said to be a potential w.r.t. 
    2.19 +  /// an edge-map edge_distance 
    2.20 +  /// if and only if for each edge e, node_potential[g.head(e)] 
    2.21 +  /// <= edge_distance[e]+node_potential[g.tail(e)] 
    2.22 +  /// (or the reverse inequality holds for each edge).
    2.23 +  /// An edge is said to be tight if this inequality holds with equality, 
    2.24 +  /// and the map returns true exactly for those edges.
    2.25 +  /// To avoid rounding errors, it is recommended to use this class with exact 
    2.26 +  /// types, e.g. with int.
    2.27 +  template<typename Graph, 
    2.28 +	   typename NodePotentialMap, typename EdgeDistanceMap>
    2.29 +  class TightEdgeFilterMap {
    2.30 +  protected:
    2.31 +    const Graph* g;
    2.32 +    NodePotentialMap* node_potential;
    2.33 +    EdgeDistanceMap* edge_distance;
    2.34 +  public:
    2.35 +    TightEdgeFilterMap(Graph& _g, NodePotentialMap& _node_potential, 
    2.36 +		       EdgeDistanceMap& _edge_distance) : 
    2.37 +      g(&_g), node_potential(&_node_potential), 
    2.38 +      edge_distance(&_edge_distance) { }
    2.39 +    bool operator[](const typename Graph::Edge& e) const {
    2.40 +      return ((*node_potential)[g->head(e)] == 
    2.41 +	      (*edge_distance)[e]+(*node_potential)[g->tail(e)]);
    2.42 +    }
    2.43 +  };
    2.44 +
    2.45 +} //namespace hugo
    2.46 +
    2.47 +#endif //HUGO_TIGHT_EDGE_FILTER_MAP_H
    2.48 +
    2.49 +