abstractBalancedFNW Class Reference

The base class for all kinds of balanced (skew-symmetric) digraph objects. More...

#include <abstractBalanced.h>

Inheritance diagram for abstractBalancedFNW:

abstractDiGraph abstractMixedGraph managedObject goblinRootObject balancedFNW balancedToBalanced graphToBalanced surfaceGraph splitGraph

Public Member Functions

 abstractBalancedFNW (TNode _n1=0, TArc _m1=0) throw ()
virtual ~abstractBalancedFNW () throw ()
unsigned long Allocated () const throw ()
bool IsBalanced () const throw ()
virtual void Symmetrize ()=0 throw ()
virtual void Relax ()=0 throw ()
TNode N1 () const throw ()
TNode ComplNode (TNode v) throw (ERRange)
TArc ComplArc (TArc a) throw (ERRange)
void InitCycles () throw ()
void ReleaseCycles () throw ()
void InitBlossoms () throw ()
void ReleaseBlossoms () throw ()
TNode Base (TNode v) throw (ERRange)
TNode Pred (TNode v) throw (ERRange)
void Bud (TNode v) throw (ERRange)
void Shrink (TNode u, TNode v) throw (ERRange)
void InitPartition () throw ()
void ReleasePartition () throw ()
void Merge (TNode u, TNode v) throw (ERRange)
TNode Find (TNode v) throw (ERRange)
void InitProps () throw ()
void ReleaseProps () throw ()
void InitPetals () throw ()
void ReleasePetals () throw ()
TFloat FindBalCap (TArc *, TNode u, TNode v) throw (ERRange,ERRejected)
virtual void BalPush (TArc a, TFloat lambda)=0 throw (ERRange,ERRejected)
virtual TFloat BalFlow (TArc a) const =0 throw (ERRange,ERRejected)
virtual TFloat BalCap (TArc a) const throw (ERRange,ERRejected)
void BalAugment (TArc *, TNode, TNode, TFloat) throw (ERRange,ERRejected)
void CancelEven () throw ()
void MakeIntegral (TArc *, TNode, TNode) throw (ERRange)
TFloat MaxBalFlow (TNode s) throw (ERRange)
TFloat Anstee (TNode s) throw (ERRange)
virtual TFloat CancelOdd () throw ()
TFloat MicaliVazirani (TNode s, TNode t=NoNode) throw (ERRange)
TFloat BNSAndAugment (TNode s) throw (ERRange)
TFloat BalancedScaling (TNode s) throw (ERRange)
bool BNS (TNode s, TNode t=NoNode) throw (ERRange,ERRejected)
void Expand (TNode *dist, TArc *, TNode, TNode) throw (ERRange)
void CoExpand (TNode *dist, TArc *, TNode, TNode) throw (ERRange)
bool BNSKocayStone (TNode s, TNode t=NoNode) throw (ERRange)
bool BNSKamedaMunro (TNode s, TNode t=NoNode) throw (ERRange)
bool BNSHeuristicsBF (TNode s, TNode t=NoNode) throw (ERRange)
bool BNSMicaliVazirani (TNode s, TNode t=NoNode) throw (ERRange)
TFloat MinCBalFlow (TNode s) throw (ERRange,ERRejected)
TFloat PrimalDual (TNode s) throw (ERRange,ERRejected)
TFloat EnhancedPD (TNode s) throw (ERRange,ERRejected)
TFloat CancelPD () throw ()

Protected Attributes

TNode n1
TArc * Q
TArc * prop
TArc * petal
TNode * base

Detailed Description

The base class for all kinds of balanced (skew-symmetric) digraph objects.

Constructor & Destructor Documentation

abstractBalancedFNW (  TNode  _n1 = 0,
TArc  _m1 = 0
)  throw ()
 

~abstractBalancedFNW (   )  throw () [virtual]
 

Member Function Documentation

unsigned long Allocated (   )  const throw ()
 

Reimplemented from abstractDiGraph.

Reimplemented in balancedFNW, balancedToBalanced, graphToBalanced, and surfaceGraph.

TFloat Anstee (  TNode  s  )  throw (ERRange)
 

TFloat BalancedScaling (  TNode  s  )  throw (ERRange)
 

void BalAugment (  TArc *  ,
TNode  ,
TNode  ,
TFloat 
)  throw (ERRange,ERRejected)
 

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

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

Implemented in balancedFNW, balancedToBalanced, graphToBalanced, and surfaceGraph.

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

Implemented in balancedFNW, balancedToBalanced, graphToBalanced, and surfaceGraph.

TNode Base (  TNode  v  )  throw (ERRange)
 

bool BNS (  TNode  s,
TNode  t = NoNode
)  throw (ERRange,ERRejected)
 

TFloat BNSAndAugment (  TNode  s  )  throw (ERRange)
 

bool BNSHeuristicsBF (  TNode  s,
TNode  t = NoNode
)  throw (ERRange)
 

bool BNSKamedaMunro (  TNode  s,
TNode  t = NoNode
)  throw (ERRange)
 

bool BNSKocayStone (  TNode  s,
TNode  t = NoNode
)  throw (ERRange)
 

bool BNSMicaliVazirani (  TNode  s,
TNode  t = NoNode
)  throw (ERRange)
 

void Bud (  TNode  v  )  throw (ERRange) [virtual]
 

Start a single node set.

Parameters:
v A node index ranged [0,1,..,n-1]
After this operation, it is Find(v)==v.

Reimplemented from abstractMixedGraph.

void CancelEven (   )  throw ()
 

TFloat CancelOdd (   )  throw () [virtual]
 

Reimplemented in graphToBalanced.

TFloat CancelPD (   )  throw ()
 

void CoExpand (  TNode *  dist,
TArc *  ,
TNode  ,
TNode 
)  throw (ERRange)
 

TArc ComplArc (  TArc  a  )  throw (ERRange)
 

TNode ComplNode (  TNode  v  )  throw (ERRange)
 

TFloat EnhancedPD (  TNode  s  )  throw (ERRange,ERRejected)
 

void Expand (  TNode *  dist,
TArc *  ,
TNode  ,
TNode 
)  throw (ERRange)
 

TNode Find (  TNode  v  )  throw (ERRange) [virtual]
 

Retrieve the set containing a given node.

Parameters:
v A node index ranged [0,1,..,n-1]
Returns:
A node index ranged [0,1,..,n-1] or NoNode
This returns the index of an arbitrary but fixed node in the same set, the so-called canonical element in this set. Only when sets are merged, the canonical element changes.

In order to check if two nodes x,y are in the same set, it is sufficient to evaluate Find(x)==Find(y) and Find(u)!=NoNode. If the context parameter methDSU is set, Find() does not only lookup the canonical element, but also performs some path compression to reduce the future lookup times.

Reimplemented from abstractMixedGraph.

TFloat FindBalCap (  TArc *  ,
TNode  u,
TNode  v
)  throw (ERRange,ERRejected)
 

void InitBlossoms (   )  throw ()
 

void InitCycles (   )  throw ()
 

void InitPartition (   )  throw () [virtual]
 

Initialize the disjoint node set structure.

If not already present, the disjoint node set structure is allocated. After this operation, it is Find(v)==NoNode for every node v.

Reimplemented from abstractMixedGraph.

void InitPetals (   )  throw ()
 

void InitProps (   )  throw ()
 

bool IsBalanced (   )  const throw () [virtual]
 

Query if this a balanced graph object.

Return values:
true This graph is balanced (skew-symmetric)

Reimplemented from abstractMixedGraph.

void MakeIntegral (  TArc *  ,
TNode  ,
TNode 
)  throw (ERRange)
 

TFloat MaxBalFlow (  TNode  s  )  throw (ERRange)
 

void Merge (  TNode  u,
TNode  v
)  throw (ERRange) [virtual]
 

Merge two disjoint node sets represented by arbitrary members.

Parameters:
u A node index ranged [0,1,..,n-1]
v A node index ranged [0,1,..,n-1]
After this operation, it is Find(u)==Find(v).

Reimplemented from abstractMixedGraph.

TFloat MicaliVazirani (  TNode  s,
TNode  t = NoNode
)  throw (ERRange)
 

TFloat MinCBalFlow (  TNode  s  )  throw (ERRange,ERRejected)
 

TNode N1 (   )  const throw ()
 

TNode Pred (  TNode  v  )  throw (ERRange)
 

TFloat PrimalDual (  TNode  s  )  throw (ERRange,ERRejected)
 

virtual void Relax (   )  throw () [pure virtual]
 

Implemented in balancedFNW, balancedToBalanced, graphToBalanced, and surfaceGraph.

void ReleaseBlossoms (   )  throw ()
 

void ReleaseCycles (   )  throw ()
 

void ReleasePartition (   )  throw () [virtual]
 

Release the disjoint set structure.

After this operation, it is Find(v)==v for every node v, and the disjoint node set structure is deallocated.

Reimplemented from abstractMixedGraph.

void ReleasePetals (   )  throw ()
 

void ReleaseProps (   )  throw ()
 

void Shrink (  TNode  u,
TNode  v
)  throw (ERRange)
 

virtual void Symmetrize (   )  throw () [pure virtual]
 

Implemented in balancedFNW, balancedToBalanced, graphToBalanced, and surfaceGraph.

Field Documentation

TNode* base [protected]
 

An array of blossom bases.

TNode n1 [protected]
 

Number of outer nodes.

TArc* petal [protected]
 

An array of node petals.

TArc* prop [protected]
 

An array of node props.

TArc* Q [protected]
 

An array for encoding of odd cycles.