Push relabel attr manager. More...

Collaboration diagram for TSnap::TPRManager:

[legend]

Public Member Functions
	TPRManager (PNEANet &Net)

int	Capacity (int EId)

int &	Flow (int EId)

int	Label (int NId)

int &	Excess (int NId)

int &	EdgeNum (int NId)

void	SetLabel (int NId, int Label)

void	CheckGap (int GapLabel)
	Removes any gaps in node labels. More...

bool	HasActive ()

int	IsActive (int NId)

int	PopActive ()

void	PushActive (int NId)

void	RemoveActive (int NId)

int	GetMaxLabel ()

Private Attributes
PNEANet &	Net

int	CapIndex

TIntV	FlowV

TIntV	ExcessV

TIntV	EdgeNumsV

TIntV	LabelsV

TIntV	LabelCounts

int	LabelLimit

int	MaxLabel

TIntQ	ActiveNodeQ

TIntV	ActiveNodeSet

int	ActiveCount

Detailed Description

Push relabel attr manager.

Flow algorithms require 2 attributes to be defined on each edge: Capacity: The maximum amount of flow over the edge. Flow: The current amount of flow over the edge. Push Relabel requires 3 attributes to be defined on each node: Label: An estimate of the distance from this node to the sink. Push Relabel pushes flow from nodes of higher labels to those of lower labels. Excess: Sum of flows into the node minus sum of flows leaving the nodes. Push Relabel finds nodes with positive excess and pushes flow out of them. These values will never be negative. EdgeNum: Push Relabel needs to cycle through the edges of a node; this attribute keeps track of which edge the cycle is at. The TPRManager class keeps maintains all of these attributes over the course of the algorithm, mostly to make the code easier to understand. It also maintains a queue of active nodes, which are nodes with positive excess and label < N, where N is the number of nodes. Each iteration of the Push Relabel algorithm pops an active node form the queue and tries to push flow from it. The current implementation of the active queue is a FIFO queue. A highest label first scheme for the active queue is also very common.

Definition at line 167 of file flow.cpp.

Constructor & Destructor Documentation

TSnap::TPRManager::TPRManager ( PNEANet & Net )

inline

Definition at line 169 of file flow.cpp.

References ActiveNodeSet, Capacity(), TSnap::CapAttrName, CapIndex, EdgeNumsV, ExcessV, FlowV, IAssert, and LabelCounts.

                            : 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) {
     CapIndex = Net->GetIntAttrIndE(CapAttrName);
     for (int i = 0; i <= Net->GetNodes(); i++) { LabelCounts[i] = 0; }
     for (TNEANet::TEdgeI EI = Net->BegEI(); EI != Net->EndEI(); EI++) {
       int EId = EI.GetId();
       IAssert(Capacity(EId) >= 0);
       FlowV[EId] = 0;
     }
     for (TNEANet::TNodeI NI = Net->BegNI(); NI != Net->EndNI(); NI++) {
       int NId = NI.GetId();
       ExcessV[NId] = 0;
       EdgeNumsV[NId] = 0;
       ActiveNodeSet[NId] = 0;
     }
     LabelCounts[0] = Net->GetNodes();
   }

Here is the call graph for this function:

Member Function Documentation

int TSnap::TPRManager::Capacity ( int EId )

inline

Definition at line 186 of file flow.cpp.

References CapIndex, and Net.

Referenced by TSnap::GetMaxFlowIntPR(), TSnap::GlobalRelabel(), TSnap::PushRelabel(), TSnap::PushToOutNbr(), TSnap::Relabel(), and TPRManager().

                          {
     return Net->GetIntAttrIndDatE(EId, CapIndex);
   }

Here is the caller graph for this function:

void TSnap::TPRManager::CheckGap ( int GapLabel )

inline

Removes any gaps in node labels.

This method implements the gap heuristic. During the algorithm, if some label L no longer has any nodes of that label, but there are nodes with labels K > L, then all of these nodes with labels K > L will not be able to push. Mark these nodes to no longer participate in pushing flow by setting their label to N, where N is the number of nodes.

Definition at line 221 of file flow.cpp.

References IsActive(), LabelCounts, LabelLimit, LabelsV, MaxLabel, Net, and RemoveActive().

Referenced by SetLabel().

                                {
     for (TNEANet::TNodeI NI = Net->BegNI(); NI != Net->EndNI(); NI++) {
       int NId = NI.GetId();
       int OldLabel = LabelsV[NId];
       if (OldLabel > GapLabel && OldLabel <= LabelLimit) {
         LabelsV[NId] = MaxLabel;
         LabelCounts[OldLabel]--;
         LabelCounts[MaxLabel]++;
         if (IsActive(NId)) { RemoveActive(NId); }
       }
     }
     LabelLimit = GapLabel - 1;
   }

Here is the call graph for this function:

Here is the caller graph for this function:

int& TSnap::TPRManager::EdgeNum ( int NId )

inline

Definition at line 202 of file flow.cpp.

References EdgeNumsV.

Referenced by TSnap::PushRelabel().

                          {
     return EdgeNumsV[NId].Val;
   }

Here is the caller graph for this function:

int& TSnap::TPRManager::Excess ( int NId )

inline

Definition at line 198 of file flow.cpp.

References ExcessV.

Referenced by TSnap::GetMaxFlowIntPR(), TSnap::GlobalRelabel(), TSnap::PushToInNbr(), and TSnap::PushToOutNbr().

                         {
     return ExcessV[NId].Val;
   }

Here is the caller graph for this function:

int& TSnap::TPRManager::Flow ( int EId )

inline

Definition at line 190 of file flow.cpp.

References FlowV.

Referenced by TSnap::GetMaxFlowIntPR(), TSnap::GlobalRelabel(), TSnap::PushRelabel(), TSnap::PushToInNbr(), TSnap::PushToOutNbr(), and TSnap::Relabel().

                       {
     return FlowV[EId].Val;
   }

Here is the caller graph for this function:

int TSnap::TPRManager::GetMaxLabel ( )

inline

Definition at line 268 of file flow.cpp.

References MaxLabel.

Referenced by TSnap::GetMaxFlowIntPR(), TSnap::GlobalRelabel(), and TSnap::Relabel().

268 { return MaxLabel; }

TSnap::TPRManager::MaxLabel

int MaxLabel

Definition: flow.cpp:281

Here is the caller graph for this function:

bool TSnap::TPRManager::HasActive ( )

inline

Definition at line 235 of file flow.cpp.

References ActiveCount.

Referenced by TSnap::GetMaxFlowIntPR().

                    {
     return ActiveCount > 0;
   }

Here is the caller graph for this function:

int TSnap::TPRManager::IsActive ( int NId )

inline

Definition at line 239 of file flow.cpp.

References ActiveNodeSet.

Referenced by CheckGap(), TSnap::GetMaxFlowIntPR(), and TSnap::GlobalRelabel().

                         {
     return ActiveNodeSet[NId];
   }

Here is the caller graph for this function:

int TSnap::TPRManager::Label ( int NId )

inline

Definition at line 194 of file flow.cpp.

References LabelsV.

Referenced by TSnap::GetMaxFlowIntPR(), TSnap::GlobalRelabel(), TSnap::PushRelabel(), TSnap::Relabel(), and SetLabel().

                       {
     return LabelsV[NId];
   }

Here is the caller graph for this function:

int TSnap::TPRManager::PopActive ( )

inline

Definition at line 243 of file flow.cpp.

References ActiveCount, ActiveNodeQ, ActiveNodeSet, TQQueue< TVal >::Empty(), IAssert, TQQueue< TVal >::Pop(), and TQQueue< TVal >::Top().

Referenced by TSnap::GetMaxFlowIntPR().

                   {
     while (true) {
       IAssert (!ActiveNodeQ.Empty());
       int NId = ActiveNodeQ.Top();
       ActiveNodeQ.Pop();
       if (ActiveNodeSet[NId])  {
         ActiveNodeSet[NId] = 0;
         ActiveCount--;
         return NId;
       }
     }
     return -1;
   }

Here is the call graph for this function:

Here is the caller graph for this function:

void TSnap::TPRManager::PushActive ( int NId )

inline

Definition at line 257 of file flow.cpp.

References ActiveCount, ActiveNodeQ, ActiveNodeSet, and TQQueue< TVal >::Push().

Referenced by TSnap::GetMaxFlowIntPR(), and TSnap::GlobalRelabel().

                            {
     ActiveNodeSet[NId] = 1;
     ActiveNodeQ.Push(NId);
     ActiveCount++;
   }

Here is the call graph for this function:

Here is the caller graph for this function:

void TSnap::TPRManager::RemoveActive ( int NId )

inline

Definition at line 263 of file flow.cpp.

References ActiveCount, and ActiveNodeSet.

Referenced by CheckGap(), and TSnap::GlobalRelabel().

                              {
     ActiveNodeSet[NId] = 0;
     ActiveCount--;
   }

Here is the caller graph for this function:

void TSnap::TPRManager::SetLabel	(	int	NId,
		int	Label
	)

inline

Definition at line 206 of file flow.cpp.

References CheckGap(), Label(), LabelCounts, LabelLimit, LabelsV, MAX, and MaxLabel.

Referenced by TSnap::GetMaxFlowIntPR(), TSnap::GlobalRelabel(), and TSnap::Relabel().

                                      {
     if (Label > LabelLimit + 1) { Label = MaxLabel; }
     int OldLabel = LabelsV[NId];
     LabelsV[NId] = Label;
     LabelCounts[OldLabel]--;
     LabelCounts[Label]++;
     if (Label != MaxLabel) { LabelLimit = MAX(LabelLimit, Label); }
     if (LabelCounts[OldLabel] == 0) { CheckGap (OldLabel); }
   }