balancedToBalanced Class Reference

Balanced digraphs obtained as a simplification of balanced network flow problems. More...

#include <balancedToBalanced.h>

Inheritance diagram for balancedToBalanced:

abstractBalancedFNW abstractDiGraph abstractMixedGraph managedObject goblinRootObject

Public Member Functions

 balancedToBalanced (abstractBalancedFNW &GC) throw ()
 ~balancedToBalanced () throw ()
unsigned long Size () const throw ()
unsigned long Allocated () const throw ()
bool Perfect () const throw ()
void Relax () throw ()
void Symmetrize () throw ()
TNode DefaultSourceNode () const throw ()
TNode DefaultTargetNode () const throw ()
TNode StartNode (TArc a) const throw (ERRange)
TNode EndNode (TArc a) const throw (ERRange)
TArc First (TNode v) const throw (ERRange)
TArc Right (TArc a, TNode v) const throw (ERRange,ERRejected)
TCap Demand (TNode v) const throw (ERRange)
bool CDemand () const throw ()
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)
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)

Protected Attributes

abstractBalancedFNW & G
TNode n0
TArc m0
TNode k2
TNode k1
TNode s1
TNode t1
TNode s2
TNode t2
TArc ret1
TArc ret2
TArc art1
TArc art2
TFloat * flow
TArc * artifical
TNode * repr
bool symm

Detailed Description

Balanced digraphs obtained as a simplification of balanced network flow problems.

Any object in this class results from another balanced digraph and an according fixed balanced pseudo-flow. By that transformation, lower capacity bounds and node imbalances are eliminated. Circulation and b-flow problems map to single source / target flow problems. This is analogous to the digraphToDigraph class for ordinary network flow probleme.

Constructor & Destructor Documentation

balancedToBalanced (  abstractBalancedFNW &  GC  )  throw ()
 

~balancedToBalanced (   )  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.

bool CDemand (   )  const throw () [virtual]
 

Check if the node demands are all the same.

Return values:
true All node demands coincide

Reimplemented from abstractMixedGraph.

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

TNode DefaultSourceNode (   )  const throw () [virtual]
 

Retrieve the default source node.

Returns:
The index of the default source node

Reimplemented from abstractMixedGraph.

TNode DefaultTargetNode (   )  const throw () [virtual]
 

Retrieve the default target node.

Returns:
The index of the default target node

Reimplemented from abstractMixedGraph.

TCap Demand (  TNode  v  )  const throw (ERRange) [virtual]
 

Retrieve a node demand.

Parameters:
v A node index ranged [0,1,..,n-1]
Returns:
The demand of node v

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.

TArc First (  TNode  v  )  const throw (ERRange) [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 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.

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.

bool Perfect (   )  const throw ()
 

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.

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.

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.

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 art1 [protected]
 

Artifical arc with end nodes s1 and t2.

TArc art2 [protected]
 

Artifical arc with end nodes s2 and t1.

TArc* artifical [protected]
 

TFloat* flow [protected]
 

Flow values on the artifical arcs.

abstractBalancedFNW& G [protected]
 

Original network.

TNode k1 [protected]
 

k1 == k2/2

TNode k2 [protected]
 

Number of odd cycles.

TArc m0 [protected]
 

Number of arcs in the original network.

TNode n0 [protected]
 

Number of nodes in the original network.

TNode* repr [protected]
 

Canonical elements of the odd cycles.

TArc ret1 [protected]
 

Return arc with end nodes t1 and s1.

TArc ret2 [protected]
 

Return arc with end nodes t2 and s2.

TNode s1 [protected]
 

Source node, s1 == DefaultSourceNode().

TNode s2 [protected]
 

Additional source node.

bool symm [protected]
 

Is flow balanced?

TNode t1 [protected]
 

Target node, t1 == DefaultTargetNode().

TNode t2 [protected]
 

Additional target node.