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:

abstractDiGraph abstractMixedGraph managedObject goblinRootObject layeredShrNetwork

Public Member Functions

 layeredAuxNetwork (abstractDiGraph &GC, TNode ss) throw ()
 ~layeredAuxNetwork () throw ()
unsigned long Size () const throw ()
unsigned long Allocated () const throw ()
investigatorNewInvestigator () 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

abstractDiGraphG
TNode s
TArcpred
investigatorI
char Phase
char * align
TArcoutDegree
TArc ** successor
TArcinDegree
TArccurrentDegree
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]