50 #include <queue> |
50 #include <queue> |
51 |
51 |
52 namespace hugo { |
52 namespace hugo { |
53 |
53 |
54 template <typename Graph, typename T, |
54 template <typename Graph, typename T, |
55 typename CapMap=typename Graph::EdgeMap<T>, |
55 typename CapMap=typename Graph::template EdgeMap<T>, |
56 typename FlowMap=typename Graph::EdgeMap<T> > |
56 typename FlowMap=typename Graph::template EdgeMap<T> > |
57 class Preflow { |
57 class Preflow { |
58 |
58 |
59 typedef typename Graph::Node Node; |
59 typedef typename Graph::Node Node; |
60 typedef typename Graph::Edge Edge; |
60 typedef typename Graph::Edge Edge; |
61 typedef typename Graph::NodeIt NodeIt; |
61 typedef typename Graph::NodeIt NodeIt; |
97 */ |
97 */ |
98 int relabel=0; |
98 int relabel=0; |
99 int k=n-2; //bound on the highest level under n containing a node |
99 int k=n-2; //bound on the highest level under n containing a node |
100 int b=k; //bound on the highest level under n of an active node |
100 int b=k; //bound on the highest level under n of an active node |
101 |
101 |
102 typename Graph::NodeMap<int> level(G,n); |
102 typename Graph::template NodeMap<int> level(G,n); |
103 typename Graph::NodeMap<T> excess(G); |
103 typename Graph::template NodeMap<T> excess(G); |
104 |
104 |
105 std::vector<Node> active(n-1,INVALID); |
105 std::vector<Node> active(n-1,INVALID); |
106 typename Graph::NodeMap<Node> next(G,INVALID); |
106 typename Graph::template NodeMap<Node> next(G,INVALID); |
107 //Stack of the active nodes in level i < n. |
107 //Stack of the active nodes in level i < n. |
108 //We use it in both phases. |
108 //We use it in both phases. |
109 |
109 |
110 typename Graph::NodeMap<Node> left(G,INVALID); |
110 typename Graph::template NodeMap<Node> left(G,INVALID); |
111 typename Graph::NodeMap<Node> right(G,INVALID); |
111 typename Graph::template NodeMap<Node> right(G,INVALID); |
112 std::vector<Node> level_list(n,INVALID); |
112 std::vector<Node> level_list(n,INVALID); |
113 /* |
113 /* |
114 List of the nodes in level i<n. |
114 List of the nodes in level i<n. |
115 */ |
115 */ |
116 |
116 |