surfaceGraph Class Reference

Encapsulates the primal-dual code for weighted balanced network flows. More...

#include <surfaceGraph.h>

Inheritance diagram for surfaceGraph:

Public Member Functions
	surfaceGraph (abstractBalancedFNW &GC) throw ()
	~surfaceGraph () throw ()
void	Init () throw ()
unsigned long	Size () const throw ()
unsigned long	Allocated () const throw ()
investigator *	NewInvestigator () const throw ()
TNode	StartNode (TArc a) const throw (ERRange)
TNode	EndNode (TArc a) const throw (ERRange)
TArc	First (TNode v) const throw (ERRange,ERRejected)
TArc	Right (TArc a, TNode v) const throw (ERRange,ERRejected)
TCap	LCap (TArc a) const throw (ERRange)
bool	CLCap () const throw ()
TCap	UCap (TArc a) const throw (ERRange)
bool	CUCap () const throw ()
TFloat	Length (TArc a) const throw (ERRange)
bool	CLength () const throw ()
bool	Blocking (TArc a) const throw ()
TFloat	C (TNode v, TDim i) const throw (ERRange)
TFloat	CMax (TDim i) const throw (ERRange)
TDim	Dim () const throw ()
bool	HiddenNode (TNode v) const throw (ERRange)
bool	HiddenArc (TArc a) const throw (ERRange)
TFloat	Flow (TArc a) const throw (ERRange)
TFloat	BalFlow (TArc a) const throw (ERRange,ERRejected)
void	Push (TArc a, TFloat lambda) throw (ERRange,ERRejected)
void	BalPush (TArc a, TFloat lambda) throw (ERRange,ERRejected)
TFloat	Sub (TArc a) const throw (ERRange)
void	Symmetrize () throw ()
void	Relax () throw ()
TNode	MakeBlossom (TNode b, TArc a) throw (ERRange)
bool	Top (TNode v) const throw (ERRange)
TFloat	ModLength (TArc a) const throw (ERRange)
TFloat	RModLength (TArc a) const throw (ERRange)
TFloat	RedLength (const TFloat *pi, TArc a) const throw (ERRange)
void	ShiftPotential (TNode v, TFloat epsilon) throw (ERRange)
void	ShiftModLength (TArc a, TFloat epsilon) throw (ERRange)
bool	Compatible () throw ()
void	CheckDual () throw ()
TArc	FindSupport (TFloat *dist, TNode s, TArc a, dynamicStack< TNode > &Support) throw ()
void	Traverse (TArc *pred, TArc aIn, TArc aOut) throw ()
void	Expand (TArc *pred, TArc aIn, TArc aOut) throw ()
TCap	ExpandAndAugment (TArc aIn, TArc aOut) throw ()
TFloat	ComputeEpsilon (TFloat *dist) throw ()
void	PrimalDual0 (TNode s) throw (ERRange)
void	Explore (TFloat *dist, goblinQueue< TArc, TFloat > &Q, investigator &I, TNode v) throw ()
TFloat	ComputeEpsilon1 (TFloat *dist) throw ()
void	PrimalDual1 (TNode s) throw (ERRange)
Protected Attributes
abstractBalancedFNW &	G
nestedFamily< TNode >	S
TNode	n0
TNode	nr
TNode	nv
TFloat *	piG
TFloat *	pi
TFloat *	modlength
TArc *	bprop
bool	real

---

Detailed Description

Encapsulates the primal-dual code for weighted balanced network flows.

---

Constructor & Destructor Documentation

surfaceGraph (  abstractBalancedFNW &  GC  )  throw ()

~surfaceGraph (   )  throw ()

---

Member Function Documentation

unsigned long Allocated (   )  const throw ()

Reimplemented from abstractBalancedFNW.

TFloat BalFlow (  TArc  a  )  const throw (ERRange,ERRejected) [virtual]

Implements abstractBalancedFNW.

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

Implements abstractBalancedFNW.

bool Blocking (  TArc  a  )  const throw () [virtual]

Sort out backward arcs. Parameters: a  The index of the considered arc ranged [0,1,..,2m-1] Return values: true  The arc is the reverse of a directed arc Reimplemented from abstractMixedGraph.

TFloat C (  TNode  v, TDim  i )  const throw (ERRange) [virtual]

Retrieve a node coordinate value. Parameters: v  A node index ranged [0,1,..,n+ni-1] i  A coordinate index Returns: The i-th coordinate value of node v Reimplemented from abstractMixedGraph.

void CheckDual (   )  throw ()

bool CLCap (   )  const throw () [virtual]

Check if the lower capacity bounds are all the same. Return values: true  All lower capacity bounds coincide Reimplemented from abstractMixedGraph.

bool CLength (   )  const throw () [virtual]

Check if the arc length labels are all the same. Return values: true  All arc length labels coincide Reimplemented from abstractMixedGraph.

TFloat CMax (  TDim  i  )  const throw (ERRange)

Retrieve the maximum coordinate value for a given coordinate index. Parameters: i  A coordinate index Returns: The maximum i-th coordinate value among all nodes Reimplemented from abstractMixedGraph.

bool Compatible (   )  throw ()

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 from abstractDiGraph.

TFloat ComputeEpsilon (  TFloat *  dist  )  throw ()

TFloat ComputeEpsilon1 (  TFloat *  dist  )  throw ()

bool CUCap (   )  const throw () [virtual]

Check if the upper capacity bounds are all the same. Return values: true  All upper capacity bounds coincide Reimplemented from abstractMixedGraph.

TDim Dim (   )  const throw () [virtual]

Retrieve the coordinate representational dimension. Returns: The coordinate representational dimension Reimplemented from abstractMixedGraph.

TNode EndNode (  TArc  a  )  const throw (ERRange) [virtual]

Query the end node of a given arc. Parameters: a  An arc index ranged [0,1,..,2*mAct-1] Returns: The index of the end node Reimplemented from abstractMixedGraph.

void Expand (  TArc *  pred, TArc  aIn, TArc  aOut )  throw ()

TCap ExpandAndAugment (  TArc  aIn, TArc  aOut )  throw ()

void Explore (  TFloat *  dist, goblinQueue< TArc, TFloat > &  Q, investigator &  I, TNode  v )  throw ()

TArc FindSupport (  TFloat *  dist, TNode  s, TArc  a, dynamicStack< TNode > &  Support )  throw ()

TArc First (  TNode  v  )  const throw (ERRange,ERRejected) [virtual]

Retrieve an arc with a given start node. The First(v) incidence is somewhat arbitrary, since icidence lists are cyclic. But when an arc is inserted, it is inserted into the incidence lists right after the First() incidence. If the graph is planely represented, and v is an exterior node, the first two incidences are usually exterior arcs, and inserting an arc with two exterior end nodes preserves the planar representation. Parameters: v  A node index ranged [0,1,..,nAct-1] Returns: The index of an outgoing arc Implements abstractMixedGraph.

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

Return a flow value. Parameters: a  An arc index Returns: The flow on this arc (the subgraph multiplicity) Reimplemented from abstractDiGraph.

bool HiddenArc (  TArc  a  )  const throw (ERRange) [virtual]

Check wether a given arc shall be visualized or not. Parameters: a  An arc index ranged [0,1,..,2m-1] Return values: true  This arc is not visualized Reimplemented from abstractMixedGraph.

bool HiddenNode (  TNode  v  )  const throw (ERRange) [virtual]

Check wether a given graph node shall be visualized or not. Parameters: v  A node index ranged [0,1,..,n-1] Return values: true  This node is not visualized If the node v is not visualized, none of the incident arcs are visualized Reimplemented from abstractMixedGraph.

void Init (   )  throw ()

TCap LCap (  TArc  a  )  const throw (ERRange) [virtual]

Retrieve a lower capacity bound. Parameters: a  An arc index ranged [0,1,..,2m-1] Returns: The lower capacity bound of arc a Reimplemented from abstractMixedGraph.

TFloat Length (  TArc  a  )  const throw (ERRange) [virtual]

Retrieve an arc length. Parameters: a  An arc index ranged [0,1,..,2m-1] Returns: The length of arc a Reimplemented from abstractMixedGraph.

TNode MakeBlossom (  TNode  b, TArc  a )  throw (ERRange)

TFloat ModLength (  TArc  a  )  const throw (ERRange)

investigator * NewInvestigator (   )  const throw () [virtual]

Allocate an investigator object for this graph. Returns: A pointer to the new investigator object Graphs work as factories for their own investigators. This is the factory method, and it is reimplemented in several subclasses. Reimplemented from abstractMixedGraph.

void PrimalDual0 (  TNode  s  )  throw (ERRange)

void PrimalDual1 (  TNode  s  )  throw (ERRange)

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

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 abstractDiGraph.

TFloat RedLength (  const TFloat *  pi, TArc  a )  const throw (ERRange) [virtual]

Retrieve a reduced arc length. Parameters: pi  A pointer to an array of node potentials a  An arc index ranged [0,1,..,2m-1] Returns: The reduced length of arc a This used by several optimization codes to derive benefit from dual solutions (the node potentials) which have been computed in advance. For undirected edges: RedLength(u,v) = RedLength(v,u) = Length(u,v) + pi[u] + pi[v] For directed arcs: RedLength(u,v) = -RedLength(v,u) = Length(u,v) + pi[u] - pi[v] Reimplemented from abstractMixedGraph.

void Relax (   )  throw () [virtual]

Implements abstractBalancedFNW.

TArc Right (  TArc  a, TNode  v )  const throw (ERRange,ERRejected) [virtual]

Query the successor of a given arc in the incidence list of its start node. Parameters: a  An arc index ranged [0,1,..,2*mAct-1] v  The index of the start node of a (only to reduce lookup times) Returns: The index of the right-hand incident arc Implements abstractMixedGraph.

TFloat RModLength (  TArc  a  )  const throw (ERRange)

void ShiftModLength (  TArc  a, TFloat  epsilon )  throw (ERRange)

void ShiftPotential (  TNode  v, TFloat  epsilon )  throw (ERRange)

unsigned long Size (   )  const throw () [virtual]

Implements goblinRootObject.

TNode StartNode (  TArc  a  )  const throw (ERRange) [virtual]

Query the start node of a given arc. Parameters: a  An arc index ranged [0,1,..,2*mAct-1] Returns: The index of the start node Implements abstractMixedGraph.

TFloat Sub (  TArc  a  )  const throw (ERRange) [virtual]

Retrieve the subgraph multiplicity of a given arc. Parameters: a  An arc index ranged [0,1,..,2*mAct-1] Returns: The multiplicity of a Implements abstractMixedGraph.

void Symmetrize (   )  throw () [virtual]

Implements abstractBalancedFNW.

bool Top (  TNode  v  )  const throw (ERRange)

void Traverse (  TArc *  pred, TArc  aIn, TArc  aOut )  throw ()

TCap UCap (  TArc  a  )  const throw (ERRange) [virtual]

Retrieve an upper capacity bound. Parameters: a  An arc index ranged [0,1,..,2m-1] Returns: The upper capacity bound of arc a Reimplemented from abstractMixedGraph.

---

Field Documentation

TArc* bprop [protected]

abstractBalancedFNW& G [protected]

TFloat* modlength [protected]

TNode n0 [protected]

TNode nr [protected]

TNode nv [protected]

TFloat* pi [protected]

TFloat* piG [protected]

bool real [protected]

nestedFamily<TNode> S [protected]