SNAP Library 4.0, Developer Reference  2017-07-27 13:18:06
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
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
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:2645
const TStr CapAttrName
Definition: flow.h:4
static const int Mx
Definition: dt.h:1139
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:2649
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:2647
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:2652
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