1 // -*- C++ -*- |
1 // -*- C++ -*- |
2 #ifndef HUGO_AUGMENTING_FLOW_H |
2 #ifndef HUGO_AUGMENTING_FLOW_H |
3 #define HUGO_AUGMENTING_FLOW_H |
3 #define HUGO_AUGMENTING_FLOW_H |
4 |
4 |
5 #include <vector> |
5 #include <vector> |
6 //#include <queue> |
|
7 //#include <stack> |
|
8 #include <iostream> |
6 #include <iostream> |
9 |
7 |
10 #include <hugo/graph_wrapper.h> |
8 #include <hugo/graph_wrapper.h> |
11 #include <bfs_dfs.h> |
9 #include <bfs_dfs.h> |
12 #include <hugo/invalid.h> |
10 #include <hugo/invalid.h> |
13 #include <hugo/maps.h> |
11 #include <hugo/maps.h> |
|
12 #include <tight_edge_filter_map.h> |
14 |
13 |
15 /// \file |
14 /// \file |
16 /// \brief Maximum flow algorithms. |
15 /// \brief Maximum flow algorithms. |
17 /// \ingroup galgs |
16 /// \ingroup galgs |
18 |
17 |
19 namespace hugo { |
18 namespace 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 }; |
|
57 |
19 |
58 /// \addtogroup galgs |
20 /// \addtogroup galgs |
59 /// @{ |
21 /// @{ |
60 /// Class for augmenting path flow algorithms. |
22 /// Class for augmenting path flow algorithms. |
61 |
23 |