Low level operations

Functions
virtual TFloat	abstractDiGraph::Flow (TArc a) const throw (ERRange)
virtual void	abstractDiGraph::Push (TArc a, TFloat lambda) throw (ERRange,ERRejected)
void	abstractDiGraph::AdjustDivergence (TArc a, TFloat lambda) throw (ERRange,ERRejected)
TFloat	abstractDiGraph::FindCap (TArc *pred, TNode source, TNode target) throw (ERRange,ERRejected)
void	abstractDiGraph::Augment (TArc *pred, TNode source, TNode target, TFloat lambda) throw (ERRange,ERRejected)
TFloat	abstractDiGraph::FlowValue (TNode source, TNode target) throw (ERRange,ERCheck)
bool	abstractDiGraph::Compatible () throw ()
TFloat	abstractDiGraph::MCF_DualObjective () throw ()

---

Function Documentation

void AdjustDivergence (  TArc  a, TFloat  lambda )  throw (ERRange,ERRejected) [inherited]

Update the degree labels after a push operation. Parameters: a  An arc index lambda  An amount of flow

void Augment (  TArc *  pred, TNode  source, TNode  target, TFloat  lambda )  throw (ERRange,ERRejected) [inherited]

Augment along a given path. Parameters: pred[]  An array of predecessor arcs assigned with the graph nodes source  The path start node target  The path end node lambda  An amount of flow

bool Compatible (   )  throw () [inherited]

Complementary slackness optimality test. Return values: true  Both the flow and the node potentials are optimal Checks wether the flow labels and the node potentials satisfy the complementary slackness conditions, that is, for every arc, either the residual capacity is zero, or the reduced length is non-negative. This procedure does not verify that the flow is feasible! Reimplemented in surfaceGraph.

TFloat FindCap (  TArc *  pred, TNode  source, TNode  target )  throw (ERRange,ERRejected) [inherited]

Compute the residual path capacity. Parameters: pred[]  An array of predecessor arcs assigned with the graph nodes source  The path start node target  The path end node Returns: The minimal residual capacity on the described path

TFloat Flow (  TArc  a  )  const throw (ERRange) [virtual, inherited]

Return a flow value. Parameters: a  An arc index Returns: The flow on this arc (the subgraph multiplicity) Reimplemented in balancedToBalanced, bigraphToDigraph, digraphToDigraph, graphToBalanced, and surfaceGraph.

TFloat FlowValue (  TNode  source, TNode  target )  throw (ERRange,ERCheck) [inherited]

Checks wether the flow labels define an st-flow and, if so, returns the flow value. Parameters: source  The path start node target  The path end node Returns: The flow value, that is the divergence at the target node

TFloat MCF_DualObjective (   )  throw () [inherited]

Computes a min-cost flow "dual" objective value from the node potentials. Returns: The dual objective value This applies to arbitrary node potentials and gives a lower bound on the minimal flow objective

void Push (  TArc  a, TFloat  lambda )  throw (ERRange,ERRejected) [virtual, inherited]

Increase or decrease the flow value of the arc a by an amount Lambda. Parameters: a  An arc index lambda  An amount of flow Reimplemented from abstractMixedGraph. Reimplemented in balancedToBalanced, bigraphToDigraph, digraphToDigraph, graphToBalanced, and surfaceGraph.