39 } else { |
39 } else { |
40 return (resG->flow.get(sym)); |
40 return (resG->flow.get(sym)); |
41 } |
41 } |
42 } |
42 } |
43 bool valid() const { return sym.valid(); } |
43 bool valid() const { return sym.valid(); } |
44 void augment(const T a) const { |
44 void augment(T a) const { |
45 if (resG->G.aNode(sym)==resG->G.tail(sym)) { |
45 if (resG->G.aNode(sym)==resG->G.tail(sym)) { |
46 resG->flow.set(sym, resG->flow.get(sym)+a); |
46 resG->flow.set(sym, resG->flow.get(sym)+a); |
47 } else { |
47 } else { |
48 resG->flow.set(sym, resG->flow.get(sym)-a); |
48 resG->flow.set(sym, resG->flow.get(sym)-a); |
49 } |
49 } |
54 friend class ResGraph<Graph, T, FlowMap, CapacityMap>; |
54 friend class ResGraph<Graph, T, FlowMap, CapacityMap>; |
55 public: |
55 public: |
56 OutEdgeIt() { } |
56 OutEdgeIt() { } |
57 //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; } |
57 //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; } |
58 private: |
58 private: |
59 OutEdgeIt(const ResGraph<Graph, T, FlowMap, CapacityMap>& _resG, const NodeIt v) { |
59 OutEdgeIt(const ResGraph<Graph, T, FlowMap, CapacityMap>& _resG, NodeIt v) { |
60 resG=&_resG; |
60 resG=&_resG; |
61 sym=resG->G.template first<OldSymEdgeIt>(v); |
61 sym=resG->G.template first<OldSymEdgeIt>(v); |
62 while( sym.valid() && !(free()>0) ) { ++sym; } |
62 while( sym.valid() && !(free()>0) ) { ++sym; } |
63 } |
63 } |
64 public: |
64 public: |
67 while( sym.valid() && !(free()>0) ) { ++sym; } |
67 while( sym.valid() && !(free()>0) ) { ++sym; } |
68 return *this; |
68 return *this; |
69 } |
69 } |
70 }; |
70 }; |
71 |
71 |
72 void getFirst(OutEdgeIt& e, const NodeIt v) const { |
72 void getFirst(OutEdgeIt& e, NodeIt v) const { |
73 e=OutEdgeIt(*this, v); |
73 e=OutEdgeIt(*this, v); |
74 } |
74 } |
75 void getFirst(EachNodeIt& v) const { G.getFirst(v); } |
75 void getFirst(EachNodeIt& v) const { G.getFirst(v); } |
76 |
76 |
77 template< typename It > |
77 template< typename It > |
80 getFirst(e); |
80 getFirst(e); |
81 return e; |
81 return e; |
82 } |
82 } |
83 |
83 |
84 template< typename It > |
84 template< typename It > |
85 It first(const NodeIt v) const { |
85 It first(NodeIt v) const { |
86 It e; |
86 It e; |
87 getFirst(e, v); |
87 getFirst(e, v); |
88 return e; |
88 return e; |
89 } |
89 } |
90 |
90 |
91 NodeIt tail(const EdgeIt e) const { return G.aNode(e.sym); } |
91 NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); } |
92 NodeIt head(const EdgeIt e) const { return G.bNode(e.sym); } |
92 NodeIt head(EdgeIt e) const { return G.bNode(e.sym); } |
93 |
93 |
94 NodeIt aNode(const OutEdgeIt e) const { return G.aNode(e.sym); } |
94 NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); } |
95 NodeIt bNode(const OutEdgeIt e) const { return G.bNode(e.sym); } |
95 NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); } |
96 |
96 |
97 int id(const NodeIt v) const { return G.id(v); } |
97 int id(NodeIt v) const { return G.id(v); } |
98 |
98 |
99 template <typename ValueType> |
99 template <typename ValueType> |
100 class NodeMap { |
100 class NodeMap { |
101 typename Graph::NodeMap<ValueType> node_map; |
101 typename Graph::NodeMap<ValueType> node_map; |
102 public: |
102 public: |
103 NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G) : node_map(_G.G) { } |
103 NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G) : node_map(_G.G) { } |
104 NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, const ValueType a) : node_map(_G.G, a) { } |
104 NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, ValueType a) : node_map(_G.G, a) { } |
105 void set(const NodeIt nit, const ValueType a) { node_map.set(nit, a); } |
105 void set(NodeIt nit, ValueType a) { node_map.set(nit, a); } |
106 ValueType get(const NodeIt nit) const { return node_map.get(nit); } |
106 ValueType get(NodeIt nit) const { return node_map.get(nit); } |
107 }; |
107 }; |
108 |
108 |
109 }; |
109 }; |
110 |
110 |
111 template <typename Graph, typename T, typename FlowMap, typename CapacityMap> |
111 template <typename Graph, typename T, typename FlowMap, typename CapacityMap> |
114 typedef typename Graph::EdgeIt EdgeIt; |
114 typedef typename Graph::EdgeIt EdgeIt; |
115 typedef typename Graph::EachEdgeIt EachEdgeIt; |
115 typedef typename Graph::EachEdgeIt EachEdgeIt; |
116 typedef typename Graph::OutEdgeIt OutEdgeIt; |
116 typedef typename Graph::OutEdgeIt OutEdgeIt; |
117 typedef typename Graph::InEdgeIt InEdgeIt; |
117 typedef typename Graph::InEdgeIt InEdgeIt; |
118 const Graph& G; |
118 const Graph& G; |
119 const NodeIt s; |
119 NodeIt s; |
120 const NodeIt t; |
120 NodeIt t; |
121 FlowMap& flow; |
121 FlowMap& flow; |
122 const CapacityMap& capacity; |
122 const CapacityMap& capacity; |
123 typedef ResGraph<Graph, T, FlowMap, CapacityMap > AugGraph; |
123 typedef ResGraph<Graph, T, FlowMap, CapacityMap > AugGraph; |
124 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; |
124 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; |
125 typedef typename AugGraph::EdgeIt AugEdgeIt; |
125 typedef typename AugGraph::EdgeIt AugEdgeIt; |
126 public: |
126 public: |
127 MaxFlow(const Graph& _G, const NodeIt _s, const NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) { } |
127 MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) { } |
128 bool augment() { |
128 bool augment() { |
129 AugGraph res_graph(G, flow, capacity); |
129 AugGraph res_graph(G, flow, capacity); |
130 bool _augment=false; |
130 bool _augment=false; |
131 |
131 |
132 typedef typename AugGraph::NodeMap<bool> ReachedMap; |
132 typedef typename AugGraph::NodeMap<bool> ReachedMap; |