SNAP Library 6.0, Developer Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
flow.cpp
Go to the documentation of this file.
1 namespace TSnap {
2 
3 // Returns the NId where the two directions of search meet up, or -1 if no augmenting path exists. ##TSnap::IntFlowBiDBFS
4 int IntFlowBiDBFS (const PNEANet &Net, const int& CapIndex, TIntV &Flow, TIntQ &FwdNodeQ, TIntH &PredEdgeH, TIntQ &BwdNodeQ, TIntH &SuccEdgeH, const int& SrcNId, const int& SnkNId) {
5  FwdNodeQ.Push(SrcNId);
6  PredEdgeH.AddDat(SrcNId, -1);
7  BwdNodeQ.Push(SnkNId);
8  SuccEdgeH.AddDat(SnkNId, -1);
9  while (!FwdNodeQ.Empty() && !BwdNodeQ.Empty()) {
10  // Forward search
11  const TNEANet::TNodeI &FwdNI = Net->GetNI(FwdNodeQ.Top()); FwdNodeQ.Pop();
12  // Check all edges that point into the current node for those over which flow can be returned.
13  for (int EdgeN = 0; EdgeN < FwdNI.GetInDeg(); EdgeN++) {
14  int NextNId = FwdNI.GetInNId(EdgeN);
15  int NextEId = FwdNI.GetInEId(EdgeN);
16  if (!PredEdgeH.IsKey(NextNId) && Flow[NextEId] > 0) {
17  PredEdgeH.AddDat(NextNId, NextEId);
18  if (SuccEdgeH.IsKey(NextNId)) {
19  return NextNId;
20  }
21  FwdNodeQ.Push(NextNId);
22  }
23  }
24  // Check all edges that point out of the current node for those over which flow can be added.
25  for (int EdgeN = 0; EdgeN < FwdNI.GetOutDeg(); EdgeN++) {
26  int NextNId = FwdNI.GetOutNId(EdgeN);
27  int NextEId = FwdNI.GetOutEId(EdgeN);
28  if (!PredEdgeH.IsKey(NextNId) && Net->GetIntAttrIndDatE(NextEId, CapIndex) > Flow[NextEId]) {
29  PredEdgeH.AddDat(NextNId, NextEId);
30  if (SuccEdgeH.IsKey(NextNId)) {
31  return NextNId;
32  }
33  FwdNodeQ.Push(NextNId);
34  }
35  }
36  // Backward search
37  const TNEANet::TNodeI &BwdNI = Net->GetNI(BwdNodeQ.Top()); BwdNodeQ.Pop();
38  // Check all edges that point out of the current node for those over which flow can be returned.
39  for (int EdgeN = 0; EdgeN < BwdNI.GetOutDeg(); EdgeN++) {
40  int PrevNId = BwdNI.GetOutNId(EdgeN);
41  int PrevEId = BwdNI.GetOutEId(EdgeN);
42  if (!SuccEdgeH.IsKey(PrevNId) && Flow[PrevEId] > 0) {
43  SuccEdgeH.AddDat(PrevNId, PrevEId);
44  if (PredEdgeH.IsKey(PrevNId)) {
45  return PrevNId;
46  }
47  BwdNodeQ.Push(PrevNId);
48  }
49  }
50  // Check all edges that point into the current node for those over which flow can be added.
51  for (int EdgeN = 0; EdgeN < BwdNI.GetInDeg(); EdgeN++) {
52  int PrevNId = BwdNI.GetInNId(EdgeN);
53  int PrevEId = BwdNI.GetInEId(EdgeN);
54  if (!SuccEdgeH.IsKey(PrevNId) && Net->GetIntAttrIndDatE(PrevEId, CapIndex) > Flow[PrevEId]) {
55  SuccEdgeH.AddDat(PrevNId, PrevEId);
56  if (PredEdgeH.IsKey(PrevNId)) {
57  return PrevNId;
58  }
59  BwdNodeQ.Push(PrevNId);
60  }
61  }
62  }
63  return -1;
64 }
65 
67 
71 int FindAugV (const PNEANet &Net, const int& CapIndex, TIntV &Flow, TIntQ &FwdNodeQ, TIntH &PredEdgeH, TIntQ &BwdNodeQ, TIntH &SuccEdgeH, TIntV &MidToSrcAugV, TIntV &MidToSnkAugV, const int& SrcNId, const int& SnkNId) {
72  int MidPtNId = IntFlowBiDBFS(Net, CapIndex, Flow, FwdNodeQ, PredEdgeH, BwdNodeQ, SuccEdgeH, SrcNId, SnkNId);
73  if (MidPtNId == -1) { return 0; }
74  int MinAug = TInt::Mx, NId = MidPtNId, AugFlow = 0;
75  // Build the path from the midpoint back to the source by tracing through the PredEdgeH
76  for (int EId = PredEdgeH.GetDat(NId); NId != SrcNId; EId = PredEdgeH.GetDat(NId)) {
77  MidToSrcAugV.Add(EId);
78  const TNEANet::TEdgeI &EI = Net->GetEI(EId);
79  if (EI.GetSrcNId() == NId) {
80  NId = EI.GetDstNId();
81  AugFlow = Flow[EId];
82  } else {
83  NId = EI.GetSrcNId();
84  AugFlow = Net->GetIntAttrIndDatE(EId, CapIndex) - Flow[EId];
85  }
86  if (AugFlow < MinAug) { MinAug = AugFlow; }
87  }
88  NId = MidPtNId;
89  // Build the path from the midpoint back to the sink by tracing through the SuccEdgeH
90  for (int EId = SuccEdgeH.GetDat(NId); NId != SnkNId; EId = SuccEdgeH.GetDat(NId)) {
91  MidToSnkAugV.Add(EId);
92  const TNEANet::TEdgeI &EI = Net->GetEI(EId);
93  if (EI.GetDstNId() == NId) {
94  NId = EI.GetSrcNId();
95  AugFlow = Flow[EId];
96  } else {
97  NId = EI.GetDstNId();
98  AugFlow = Net->GetIntAttrIndDatE(EId, CapIndex) - Flow[EId];
99  }
100  if (AugFlow < MinAug) { MinAug = AugFlow; }
101  }
102  return MinAug;
103 }
104 
105 int GetMaxFlowIntEK (PNEANet &Net, const int &SrcNId, const int &SnkNId) {
106  IAssert(Net->IsNode(SrcNId));
107  IAssert(Net->IsNode(SnkNId));
108  if (SrcNId == SnkNId) { return 0; }
109  int CapIndex = Net->GetIntAttrIndE(CapAttrName);
110  TIntV Flow(Net->GetMxEId());
111  // Initialize flow values to 0, and make sure capacities are nonnegative
112  for (TNEANet::TEdgeI EI = Net->BegEI(); EI != Net->EndEI(); EI++) {
113  IAssert(Net->GetIntAttrIndDatE(EI, CapIndex) >= 0);
114  Flow[EI.GetId()] = 0;
115  }
116  // Return 0 if user attempts to flow from a node to itself.
117  if (SrcNId == SnkNId) { return 0; }
118  int MaxFlow = 0, MinAug, CurNId;
119  while (true) {
120  TIntV MidToSrcAugV; TIntV MidToSnkAugV;
121  TIntQ FwdNodeQ; TIntQ BwdNodeQ;
122  TIntH PredEdgeH; TIntH SuccEdgeH;
123  MinAug = FindAugV(Net, CapIndex, Flow, FwdNodeQ, PredEdgeH, BwdNodeQ, SuccEdgeH, MidToSrcAugV, MidToSnkAugV, SrcNId, SnkNId);
124  if (MinAug == 0) { break; }
125  MaxFlow += MinAug;
126  CurNId = SrcNId;
127  for (int i = MidToSrcAugV.Len() - 1; i >= 0; i--) {
128  int NextEId = MidToSrcAugV[i];
129  const TNEANet::TEdgeI &EI = Net->GetEI(NextEId);
130  if (EI.GetSrcNId() == CurNId) {
131  Flow[NextEId] += MinAug;
132  CurNId = EI.GetDstNId();
133  } else {
134  Flow[NextEId] -= MinAug;
135  CurNId = EI.GetSrcNId();
136  }
137  }
138  for (int i = 0; i < MidToSnkAugV.Len(); i++) {
139  int NextEId = MidToSnkAugV[i];
140  const TNEANet::TEdgeI &EI = Net->GetEI(NextEId);
141  if (EI.GetSrcNId() == CurNId) {
142  Flow[NextEId] += MinAug;
143  CurNId = EI.GetDstNId();
144  } else {
145  Flow[NextEId] -= MinAug;
146  CurNId = EI.GetSrcNId();
147  }
148  }
149  }
150  return MaxFlow;
151 }
152 
153 //#///////////////////////////////////////////////
155 
167 class TPRManager {
168 public:
169  TPRManager(PNEANet &Net) : Net(Net), CapIndex(0), FlowV(Net->GetMxEId()), ExcessV(Net->GetMxNId()), EdgeNumsV(Net->GetMxNId()), LabelsV(Net->GetMxNId()), LabelCounts(Net->GetNodes() + 1), LabelLimit(0), MaxLabel(Net->GetNodes()), ActiveNodeSet(Net->GetMxNId()), ActiveCount(0) {
170  CapIndex = Net->GetIntAttrIndE(CapAttrName);
171  for (int i = 0; i <= Net->GetNodes(); i++) { LabelCounts[i] = 0; }
172  for (TNEANet::TEdgeI EI = Net->BegEI(); EI != Net->EndEI(); EI++) {
173  int EId = EI.GetId();
174  IAssert(Capacity(EId) >= 0);
175  FlowV[EId] = 0;
176  }
177  for (TNEANet::TNodeI NI = Net->BegNI(); NI != Net->EndNI(); NI++) {
178  int NId = NI.GetId();
179  ExcessV[NId] = 0;
180  EdgeNumsV[NId] = 0;
181  ActiveNodeSet[NId] = 0;
182  }
183  LabelCounts[0] = Net->GetNodes();
184  }
185 
186  int Capacity (int EId) {
187  return Net->GetIntAttrIndDatE(EId, CapIndex);
188  }
189 
190  int &Flow (int EId) {
191  return FlowV[EId].Val;
192  }
193 
194  int Label (int NId) {
195  return LabelsV[NId];
196  }
197 
198  int &Excess (int NId) {
199  return ExcessV[NId].Val;
200  }
201 
202  int &EdgeNum (int NId) {
203  return EdgeNumsV[NId].Val;
204  }
205 
206  void SetLabel (int NId, int Label) {
207  if (Label > LabelLimit + 1) { Label = MaxLabel; }
208  int OldLabel = LabelsV[NId];
209  LabelsV[NId] = Label;
210  LabelCounts[OldLabel]--;
211  LabelCounts[Label]++;
212  if (Label != MaxLabel) { LabelLimit = MAX(LabelLimit, Label); }
213  if (LabelCounts[OldLabel] == 0) { CheckGap (OldLabel); }
214  }
215 
217 
221  void CheckGap (int GapLabel) {
222  for (TNEANet::TNodeI NI = Net->BegNI(); NI != Net->EndNI(); NI++) {
223  int NId = NI.GetId();
224  int OldLabel = LabelsV[NId];
225  if (OldLabel > GapLabel && OldLabel <= LabelLimit) {
226  LabelsV[NId] = MaxLabel;
227  LabelCounts[OldLabel]--;
229  if (IsActive(NId)) { RemoveActive(NId); }
230  }
231  }
232  LabelLimit = GapLabel - 1;
233  }
234 
235  bool HasActive() {
236  return ActiveCount > 0;
237  }
238 
239  int IsActive(int NId) {
240  return ActiveNodeSet[NId];
241  }
242 
243  int PopActive() {
244  while (true) {
246  int NId = ActiveNodeQ.Top();
247  ActiveNodeQ.Pop();
248  if (ActiveNodeSet[NId]) {
249  ActiveNodeSet[NId] = 0;
250  ActiveCount--;
251  return NId;
252  }
253  }
254  return -1;
255  }
256 
257  void PushActive(int NId) {
258  ActiveNodeSet[NId] = 1;
259  ActiveNodeQ.Push(NId);
260  ActiveCount++;
261  }
262 
263  void RemoveActive(int NId) {
264  ActiveNodeSet[NId] = 0;
265  ActiveCount--;
266  }
267 
268  int GetMaxLabel() { return MaxLabel; }
269 
270 private:
272  int CapIndex;
274 
277 
281  int MaxLabel;
282 
286 };
287 
289 void PushToOutNbr (TPRManager &PRM, const int &NId, const int &OutNId, const int &EId) {
290  int MinPush = MIN(PRM.Capacity(EId) - PRM.Flow(EId), PRM.Excess(NId));
291  PRM.Flow(EId) += MinPush;
292  PRM.Excess(NId) -= MinPush;
293  PRM.Excess(OutNId) += MinPush;
294 }
295 
297 void PushToInNbr (TPRManager &PRM, const int &NId, const int &InNId, const int &EId) {
298  int MinPush = MIN(PRM.Flow(EId), PRM.Excess(NId));
299  PRM.Flow(EId) -= MinPush;
300  PRM.Excess(NId) -= MinPush;
301  PRM.Excess(InNId) += MinPush;
302 }
303 
305 void Relabel (TPRManager &PRM, const int &NId, const TNEANet::TNodeI &NI) {
306  int MaxLabel = PRM.GetMaxLabel();
307  int MinLabel = MaxLabel;
308  for (int EdgeN = 0; EdgeN < NI.GetInDeg(); EdgeN++) {
309  if (PRM.Flow(NI.GetInEId(EdgeN)) > 0) {
310  int InLabel = PRM.Label(NI.GetInNId(EdgeN));
311  MinLabel = MIN(MinLabel, InLabel);
312  }
313  }
314  for (int EdgeN = 0; EdgeN < NI.GetOutDeg(); EdgeN++) {
315  if (PRM.Capacity(NI.GetOutEId(EdgeN)) > PRM.Flow(NI.GetOutEId(EdgeN))) {
316  int OutLabel = PRM.Label(NI.GetOutNId(EdgeN));
317  MinLabel = MIN(MinLabel, OutLabel);
318  }
319  }
320  if (MinLabel == MaxLabel) {
321  PRM.SetLabel(NId, MaxLabel);
322  } else {
323  PRM.SetLabel(NId, MinLabel + 1);
324  }
325 }
326 
328 int PushRelabel (TPRManager &PRM, const int &NId, const TNEANet::TNodeI &NI) {
329  int EdgeN = PRM.EdgeNum(NId);
330  int EId = -1, NbrNId = -1, ResFlow = 0;
331  int Cutoff = NI.GetInDeg();
332  if (EdgeN < Cutoff) {
333  EId = NI.GetInEId(EdgeN);
334  NbrNId = NI.GetInNId(EdgeN);
335  ResFlow = PRM.Flow(EId);
336  } else {
337  EId = NI.GetOutEId(EdgeN - Cutoff);
338  NbrNId = NI.GetOutNId(EdgeN - Cutoff);
339  ResFlow = PRM.Capacity(EId) - PRM.Flow(EId);
340  }
341  if (ResFlow > 0 && PRM.Label(NId) - 1 == PRM.Label(NbrNId)) {
342  if (EdgeN < Cutoff) {
343  PushToInNbr(PRM, NId, NbrNId, EId);
344  } else {
345  PushToOutNbr(PRM, NId, NbrNId, EId);
346  }
347  return NbrNId;
348  }
349  if (EdgeN + 1 == NI.GetDeg()) {
350  PRM.EdgeNum(NId) = 0;
351  Relabel(PRM, NId, NI);
352  } else {
353  PRM.EdgeNum(NId)++;
354  }
355  return -1;
356 }
357 
359 
363 void GlobalRelabel (PNEANet &Net, TPRManager &PRM, const int& SrcNId, const int& SnkNId) {
364  TIntQ NodeQ;
365  int size = Net->GetMxNId();
366  TIntV NodeV(size);
367  for (int i = 0; i < size; i++) { NodeV[i] = 0; }
368  NodeQ.Push(SnkNId);
369  NodeV[SnkNId] = 1;
370  int MaxLabel = PRM.GetMaxLabel();
371  while (!NodeQ.Empty()) {
372  // Backward search
373  int NId = NodeQ.Top(); NodeQ.Pop();
374  const TNEANet::TNodeI &NI = Net->GetNI(NId);
375  // Check all edges that point out of the current node for those over which flow can be returned.
376  for (int EdgeN = 0; EdgeN < NI.GetOutDeg(); EdgeN++) {
377  int OutNId = NI.GetOutNId(EdgeN);
378  int EId = NI.GetOutEId(EdgeN);
379  if (!NodeV[OutNId] && PRM.Flow(EId) > 0) {
380  NodeV[OutNId] = 1;
381  NodeQ.Push(OutNId);
382  PRM.SetLabel(OutNId, PRM.Label(NId) + 1);
383  }
384  }
385  // Check all edges that point into the current node for those over which flow can be added.
386  for (int EdgeN = 0; EdgeN < NI.GetInDeg(); EdgeN++) {
387  int InNId = NI.GetInNId(EdgeN);
388  int EId = NI.GetInEId(EdgeN);
389  if (!NodeV[InNId] && PRM.Capacity(EId) > PRM.Flow(EId)) {
390  NodeV[InNId] = 1;
391  NodeQ.Push(InNId);
392  PRM.SetLabel(InNId, PRM.Label(NId) + 1);
393  }
394  }
395  }
396 
397  for (TNEANet::TNodeI NI = Net->BegNI(); NI != Net->EndNI(); NI++) {
398  int NId = NI.GetId();
399  if (NodeV[NId]) {
400  if (PRM.Excess(NId) > 0 && PRM.Label(NId) < MaxLabel && NId != SnkNId) {
401  if (!PRM.IsActive(NId)) { PRM.PushActive(NId); }
402  }
403  } else {
404  if (PRM.IsActive(NId)) { PRM.RemoveActive(NId); }
405  PRM.SetLabel(NId, MaxLabel);
406  }
407  }
408 }
409 
410 int GetMaxFlowIntPR (PNEANet &Net, const int& SrcNId, const int& SnkNId) {
411  IAssert(Net->IsNode(SrcNId));
412  IAssert(Net->IsNode(SnkNId));
413  if (SrcNId == SnkNId) { return 0; }
414 
415  TPRManager PRM(Net);
416  int MaxLabel = PRM.GetMaxLabel();
417 
418  TNEANet::TNodeI SrcNI = Net->GetNI(SrcNId);
419  for (int EdgeN = 0; EdgeN < SrcNI.GetOutDeg(); EdgeN++) {
420  int EId = SrcNI.GetOutEId(EdgeN);
421  int OutNId = SrcNI.GetOutNId(EdgeN);
422  if (OutNId != SrcNId) {
423  int Capacity = PRM.Capacity(EId);
424  PRM.Flow(EId) = Capacity;
425  PRM.Excess(OutNId) = Capacity;
426  }
427  }
428  GlobalRelabel(Net, PRM, SrcNId, SnkNId);
429  PRM.SetLabel(SrcNId, MaxLabel);
430  int RelabelCount = 1;
431  int GRRate = Net->GetNodes();
432  while (PRM.HasActive()) {
433  int NId = PRM.PopActive();
434  const TNEANet::TNodeI &NI = Net->GetNI(NId);
435  int PrevLabel = MaxLabel;
436  while (PRM.Excess(NId) > 0 && PRM.Label(NId) <= PrevLabel) {
437  PrevLabel = PRM.Label(NId);
438  int NbrNId = PushRelabel(PRM, NId, NI);
439  if (NbrNId != -1 && NbrNId != SnkNId && PRM.Excess(NbrNId) > 0 && !PRM.IsActive(NbrNId)) {
440  PRM.PushActive(NbrNId);
441  }
442  }
443  if (PRM.Excess(NId) > 0 && PRM.Label(NId) < MaxLabel) {
444  PRM.PushActive(NId);
445  }
446  if (RelabelCount % GRRate == 0) { GlobalRelabel(Net, PRM, SrcNId, SnkNId); }
447  }
448  return PRM.Excess(SnkNId);
449 }
450 
451 
452 };
#define IAssert(Cond)
Definition: bd.h:262
int GetMaxLabel()
Definition: flow.cpp:268
Main namespace for all the Snap global entities.
Definition: alg.h:1
TPRManager(PNEANet &Net)
Definition: flow.cpp:169
void PushToOutNbr(TPRManager &PRM, const int &NId, const int &OutNId, const int &EId)
Pushes flow from a node NId to a neighbor OutNId over edge EId.
Definition: flow.cpp:289
int PushRelabel(TPRManager &PRM, const int &NId, const TNEANet::TNodeI &NI)
Returns the ID of the neighbor that NId pushes to, -1 if no push was made.
Definition: flow.cpp:328
int & EdgeNum(int NId)
Definition: flow.cpp:202
int GetOutNId(const int &EdgeN) const
Returns ID of EdgeN-th out-node (the node the current node points to).
Definition: network.h:1821
int GetOutDeg() const
Returns out-degree of the current node.
Definition: network.h:1813
bool Empty() const
Definition: ds.h:2646
const TStr CapAttrName
Definition: flow.h:4
static const int Mx
Definition: dt.h:1142
int GetInNId(const int &EdgeN) const
Returns ID of EdgeN-th in-node (the node pointing to the current node).
Definition: network.h:1817
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
void Relabel(TPRManager &PRM, const int &NId, const TNEANet::TNodeI &NI)
Increases the label of a node NId to allow valid pushes to some neighbor.
Definition: flow.cpp:305
int GetOutEId(const int &EdgeN) const
Returns ID of EdgeN-th out-edge.
Definition: network.h:1835
void PushActive(int NId)
Definition: flow.cpp:257
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
Node iterator. Only forward iteration (operator++) is supported.
Definition: network.h:1792
int GetDeg() const
Returns degree of the current node, the sum of in-degree and out-degree.
Definition: network.h:1809
int IsActive(int NId)
Definition: flow.cpp:239
int GetInEId(const int &EdgeN) const
Returns ID of EdgeN-th in-edge.
Definition: network.h:1833
int FindAugV(const PNEANet &Net, const int &CapIndex, TIntV &Flow, TIntQ &FwdNodeQ, TIntH &PredEdgeH, TIntQ &BwdNodeQ, TIntH &SuccEdgeH, TIntV &MidToSrcAugV, TIntV &MidToSnkAugV, const int &SrcNId, const int &SnkNId)
Returns the amount the flow can be augmented over the paths, 0 if no path can be found.
Definition: flow.cpp:71
int GetDstNId() const
Returns the destination of the edge.
Definition: network.h:1886
void GlobalRelabel(PNEANet &Net, TPRManager &PRM, const int &SrcNId, const int &SnkNId)
Implements the Global Relabeling heuristic.
Definition: flow.cpp:363
void Pop()
Definition: ds.h:2650
int PopActive()
Definition: flow.cpp:243
TIntQ ActiveNodeQ
Definition: flow.cpp:283
void SetLabel(int NId, int Label)
Definition: flow.cpp:206
#define MIN(a, b)
Definition: bd.h:346
TIntV EdgeNumsV
Definition: flow.cpp:276
TIntV ActiveNodeSet
Definition: flow.cpp:284
void CheckGap(int GapLabel)
Removes any gaps in node labels.
Definition: flow.cpp:221
int GetInDeg() const
Returns in-degree of the current node.
Definition: network.h:1811
int GetMaxFlowIntEK(PNEANet &Net, const int &SrcNId, const int &SnkNId)
Returns the maximum integer valued flow in the network Net from source SrcNId to sink SnkNId...
Definition: flow.cpp:105
int GetSrcNId() const
Returns the source of the edge.
Definition: network.h:1884
int Label(int NId)
Definition: flow.cpp:194
const TVal & Top() const
Definition: ds.h:2648
void RemoveActive(int NId)
Definition: flow.cpp:263
int Capacity(int EId)
Definition: flow.cpp:186
int GetMaxFlowIntPR(PNEANet &Net, const int &SrcNId, const int &SnkNId)
Returns the maximum integer valued flow in the network Net from source SrcNId to sink SnkNId...
Definition: flow.cpp:410
bool HasActive()
Definition: flow.cpp:235
TIntV LabelCounts
Definition: flow.cpp:279
int IntFlowBiDBFS(const PNEANet &Net, const int &CapIndex, TIntV &Flow, TIntQ &FwdNodeQ, TIntH &PredEdgeH, TIntQ &BwdNodeQ, TIntH &SuccEdgeH, const int &SrcNId, const int &SnkNId)
Definition: flow.cpp:4
Edge iterator. Only forward iteration (operator++) is supported.
Definition: network.h:1867
PNEANet & Net
Definition: flow.cpp:271
int & Flow(int EId)
Definition: flow.cpp:190
Definition: hash.h:97
int & Excess(int NId)
Definition: flow.cpp:198
Definition: bd.h:196
void Push(const TVal &Val)
Definition: ds.h:2653
Push relabel attr manager.
Definition: flow.cpp:167
void PushToInNbr(TPRManager &PRM, const int &NId, const int &InNId, const int &EId)
Returns flow from a node NId to a neighbor InNId over edge EId.
Definition: flow.cpp:297
bool IsKey(const TKey &Key) const
Definition: hash.h:258
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
#define MAX(a, b)
Definition: bd.h:350
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430