layeredAuxNetwork Class Reference
[Maximum st-flow]

A class for supporting supporting network flow methods which use layered augmentation. More...

#include <auxiliaryNetwork.h>

Inheritance diagram for layeredAuxNetwork:

Public Member Functions
	layeredAuxNetwork (abstractDiGraph &GC, TNode ss) throw ()
	~layeredAuxNetwork () 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	UCap (TArc a) const throw (ERRange)
bool	CUCap () const throw ()
bool	Blocking (TArc a) const throw (ERRange)
char	Orientation (TArc a) throw (ERRange)
bool	COrientation () throw ()
void	WriteIncidences (goblinExport *F) throw ()
TFloat	Dist (TNode v) throw (ERRange)
TFloat	Length (TArc a) const throw ()
bool	CLength () const throw ()
TFloat	C (TNode v, char i) const throw (ERRange)
TFloat	CMax (char i) const throw (ERRange)
TDim	Dim () const throw ()
bool	HiddenNode (TNode v) const throw (ERRange)
void	Phase1 () throw (ERRejected)
void	Init () throw ()
void	InsertProp (TArc a) throw (ERRange,ERRejected)
void	Phase2 () throw (ERRejected)
bool	Blocked (TNode v) const throw (ERRange)
TFloat	FindPath (TNode t) throw (ERRange,ERRejected)
void	TopErasure (TArc a) throw (ERRange,ERRejected)
TFloat	Sub (TArc a) const throw ()
Protected Attributes
abstractDiGraph &	G
TNode	s
TArc *	pred
investigator *	I
char	Phase
char *	align
TArc *	outDegree
TArc **	successor
TArc *	inDegree
TArc *	currentDegree
TArc **	prop
staticQueue< TNode > *	blocked

---

Detailed Description

A class for supporting supporting network flow methods which use layered augmentation.

An auxiliary network is a sparely represented DAG and defined relative to a flow network G (a digraph with fixed arc capacities) and a pair of nodes s, t for which a flow has to be maximized (t is not specified in the constructor, but only in augmenation phases).

The incidence structure of the auxiliary network is manipulated in phases. In the odd phases, incidences are generated for the arcs which occur on a shortest residual path. In the even phases (the augmentation phases), arcs are deleted when no further residual capacity is available.

---

Constructor & Destructor Documentation

layeredAuxNetwork (  abstractDiGraph &  GC, TNode  ss )  throw ()

~layeredAuxNetwork (   )  throw ()

---

Member Function Documentation

unsigned long Allocated (   )  const throw ()

Reimplemented from abstractDiGraph. Reimplemented in layeredShrNetwork.

bool Blocked (  TNode  v  )  const throw (ERRange)

bool Blocking (  TArc  a  )  const throw (ERRange) [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, char  i )  const throw (ERRange)

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 (  char  i  )  const throw (ERRange)

bool COrientation (   )  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.

TFloat Dist (  TNode  v  )  throw (ERRange)

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.

TFloat FindPath (  TNode  t  )  throw (ERRange,ERRejected)

Reimplemented in layeredShrNetwork.

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.

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 ()

Reimplemented in layeredShrNetwork.

void InsertProp (  TArc  a  )  throw (ERRange,ERRejected)

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

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

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.

char Orientation (  TArc  a  )  throw (ERRange)

void Phase1 (   )  throw (ERRejected)

void Phase2 (   )  throw (ERRejected)

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.

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

Implements goblinRootObject. Reimplemented in layeredShrNetwork.

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. Reimplemented in layeredShrNetwork.

TFloat Sub (  TArc  a  )  const throw () [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 TopErasure (  TArc  a  )  throw (ERRange,ERRejected)

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. Reimplemented in layeredShrNetwork.

void WriteIncidences (  goblinExport *  F  )  throw ()

---

Field Documentation

char* align [protected]

staticQueue<TNode>* blocked [protected]

TArc* currentDegree [protected]

abstractDiGraph& G [protected]

investigator* I [protected]

TArc* inDegree [protected]

TArc* outDegree [protected]

char Phase [protected]

TArc* pred [protected]

TArc** prop [protected]

TNode s [protected]

TArc** successor [protected]