equal
deleted
inserted
replaced
41 #include <queue> |
41 #include <queue> |
42 |
42 |
43 namespace hugo { |
43 namespace hugo { |
44 |
44 |
45 template <typename Graph, typename T, |
45 template <typename Graph, typename T, |
46 typename FlowMap=typename Graph::EdgeMap<T>, |
46 typename CapMap=typename Graph::EdgeMap<T>, |
47 typename CapMap=typename Graph::EdgeMap<T> > |
47 typename FlowMap=typename Graph::EdgeMap<T> > |
48 class Preflow { |
48 class Preflow { |
49 |
49 |
50 typedef typename Graph::Node Node; |
50 typedef typename Graph::Node Node; |
51 typedef typename Graph::Edge Edge; |
51 typedef typename Graph::Edge Edge; |
52 typedef typename Graph::NodeIt NodeIt; |
52 typedef typename Graph::NodeIt NodeIt; |
54 typedef typename Graph::InEdgeIt InEdgeIt; |
54 typedef typename Graph::InEdgeIt InEdgeIt; |
55 |
55 |
56 const Graph& G; |
56 const Graph& G; |
57 Node s; |
57 Node s; |
58 Node t; |
58 Node t; |
|
59 const CapMap& capacity; |
59 FlowMap& flow; |
60 FlowMap& flow; |
60 const CapMap& capacity; |
|
61 T value; |
61 T value; |
62 |
62 |
63 public: |
63 public: |
64 Preflow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, |
64 Preflow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, |
65 FlowMap& _flow ) : |
65 FlowMap& _flow ) : |
66 G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) {} |
66 G(_G), s(_s), t(_t), capacity(_capacity), flow(_flow) {} |
67 |
|
68 |
67 |
69 void run() { |
68 void run() { |
70 |
69 |
71 bool phase=0; //phase 0 is the 1st phase, phase 1 is the 2nd |
70 bool phase=0; //phase 0 is the 1st phase, phase 1 is the 2nd |
72 int n=G.nodeNum(); |
71 int n=G.nodeNum(); |