Push relabel attr manager. More...

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.

                            : 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();
   }

Member Function Documentation

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

inline

Definition at line 186 of file flow.cpp.

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

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.

                                {
     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;
   }

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

inline

Definition at line 202 of file flow.cpp.

                          {
     return EdgeNumsV[NId].Val;
   }

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

inline

Definition at line 198 of file flow.cpp.

                         {
     return ExcessV[NId].Val;
   }

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

inline

Definition at line 190 of file flow.cpp.

                       {
     return FlowV[EId].Val;
   }

int TSnap::TPRManager::GetMaxLabel ( )

inline

Definition at line 268 of file flow.cpp.

268 { return MaxLabel; }

TSnap::TPRManager::MaxLabel

int MaxLabel

Definition: flow.cpp:281

bool TSnap::TPRManager::HasActive ( )

inline

Definition at line 235 of file flow.cpp.

                    {
     return ActiveCount > 0;
   }

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

inline

Definition at line 239 of file flow.cpp.

                         {
     return ActiveNodeSet[NId];
   }

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

inline

Definition at line 194 of file flow.cpp.

                       {
     return LabelsV[NId];
   }

int TSnap::TPRManager::PopActive ( )

inline

Definition at line 243 of file flow.cpp.

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

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

inline

Definition at line 257 of file flow.cpp.

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

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

inline

Definition at line 263 of file flow.cpp.

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

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

inline

Definition at line 206 of file flow.cpp.

                                      {
     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); }
   }

Member Data Documentation

int TSnap::TPRManager::ActiveCount

private

Definition at line 285 of file flow.cpp.

TIntQ TSnap::TPRManager::ActiveNodeQ

private

Definition at line 283 of file flow.cpp.

TIntV TSnap::TPRManager::ActiveNodeSet

private

Definition at line 284 of file flow.cpp.

int TSnap::TPRManager::CapIndex

private

Definition at line 272 of file flow.cpp.

TIntV TSnap::TPRManager::EdgeNumsV

private

Definition at line 276 of file flow.cpp.

TIntV TSnap::TPRManager::ExcessV

private

Definition at line 275 of file flow.cpp.

TIntV TSnap::TPRManager::FlowV

private

Definition at line 273 of file flow.cpp.

TIntV TSnap::TPRManager::LabelCounts

private

Definition at line 279 of file flow.cpp.

int TSnap::TPRManager::LabelLimit

private

Definition at line 280 of file flow.cpp.

TIntV TSnap::TPRManager::LabelsV

private

Definition at line 278 of file flow.cpp.

int TSnap::TPRManager::MaxLabel

private

Definition at line 281 of file flow.cpp.

PNEANet& TSnap::TPRManager::Net

private

Definition at line 271 of file flow.cpp.

The documentation for this class was generated from the following file:

snap-core/flow.cpp

Public Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation