abstractBiGraph Class Reference

The base class for all kinds of bipartite graph objects. More...

#include <abstractBigraph.h>

Inheritance diagram for abstractBiGraph:

Public Member Functions
	abstractBiGraph (TNode _n1=0, TNode _n2=0, TArc _m=0) throw (ERRange)
virtual	~abstractBiGraph () throw ()
unsigned long	Allocated () const throw ()
void	CheckLimits () throw (ERRange)
bool	IsBipartite () const throw ()
TNode	N1 () const throw ()
TNode	N2 () const throw ()
void	RandomArcs (TArc _m) throw (ERRejected)
virtual void	ReadNNodes (goblinImport &F) throw (ERParse)
bool	MaximumAssignment () throw ()
bool	MaximumAssignment (TCap cDeg) throw ()
bool	MaximumAssignment (TCap *pLower, TCap *pDeg=NULL) throw ()
bool	MinCAssignment () throw ()
bool	MinCAssignment (TCap cDeg) throw ()
bool	MinCAssignment (TCap *pLower, TCap *pDeg=NULL) throw ()
bool	MaximumMatching () throw ()
bool	MaximumMatching (TCap cDeg) throw ()
bool	MaximumMatching (TCap *pLower, TCap *pDeg=NULL) throw ()
bool	MinCMatching () throw ()
bool	MinCMatching (TCap cDeg) throw ()
bool	MinCMatching (TCap *pLower, TCap *pDeg=NULL) throw ()
TNode	StableSet () throw ()
TNode	NodeColouring (TNode k=NoNode) throw ()
Protected Attributes
TNode	n1
TNode	n2

---

Detailed Description

The base class for all kinds of bipartite graph objects.

---

Constructor & Destructor Documentation

abstractBiGraph (  TNode  _n1 = 0, TNode  _n2 = 0, TArc  _m = 0 )  throw (ERRange)

~abstractBiGraph (   )  throw () [virtual]

---

Member Function Documentation

unsigned long Allocated (   )  const throw ()

Reimplemented from abstractGraph. Reimplemented in denseBiGraph, and sparseBiGraph.

void CheckLimits (   )  throw (ERRange)

Reimplemented from abstractMixedGraph.

bool MaximumAssignment (  TCap *  pLower, TCap *  pDeg = NULL )  throw ()

bool MaximumAssignment (  TCap  cDeg  )  throw ()

bool MaximumAssignment (   )  throw ()

bool MaximumMatching (  TCap *  pLower, TCap *  pDeg = NULL )  throw () [virtual]

Determine a minimum defect (b,c)-matching. Parameters: pLower  A pointer to an array of lower degree bounds pDeg  A pointer to an array of upper degree bounds or NULL Return values: true  A perfect matching has been found Reimplemented from abstractGraph.

bool MaximumMatching (  TCap  cDeg  )  throw () [virtual]

Determine a maximum k-factor. Parameters: cDeg  The desired constant node degree Return values: true  A perfect matching has been found Reimplemented from abstractGraph.

bool MaximumMatching (   )  throw () [virtual]

Determine a maximum b-matching or f-factor. Return values: true  A perfect matching has been found The desired node degrees are defined implicitly by the Demand() values. Reimplemented from abstractGraph.

bool MinCAssignment (  TCap *  pLower, TCap *  pDeg = NULL )  throw ()

bool MinCAssignment (  TCap  cDeg  )  throw ()

bool MinCAssignment (   )  throw ()

bool MinCMatching (  TCap *  pLower, TCap *  pDeg = NULL )  throw () [virtual]

Determine a minimum-cost perfect (b,c)-matching. Parameters: pLower  A pointer to an array of lower degree bounds pDeg  A pointer to an array of upper degree bounds or NULL Return values: true  A perfect matching has been found Reimplemented from abstractGraph.

bool MinCMatching (  TCap  cDeg  )  throw () [virtual]

Determine a minimum-cost perfect k-factor. Parameters: cDeg  The desired constant node degree Return values: true  A perfect matching has been found Reimplemented from abstractGraph.

bool MinCMatching (   )  throw () [virtual]

Determine a minimum-cost perfect b-matching or f-factor. Return values: true  A perfect matching has been found The desired node degrees are defined implicitly by the Demand() values. Other than the overloaded methods which take explicit degree information, this allows for the candidate graph heuristic if the graph is dense and if methCandidates >= 0. Reimplemented from abstractGraph.

TNode NodeColouring (  TNode  k = NoNode  )  throw () [virtual]

Partition the node set into independent sets. Parameters: k  The accepted number of independent sets Returns: The achieved number of independent sets Reimplemented from abstractMixedGraph.

void RandomArcs (  TArc  _m  )  throw (ERRejected) [virtual]

Extend a graph by random arcs. Parameters: _m  The number of arcs to be added Reimplemented from abstractMixedGraph.

void ReadNNodes (  goblinImport &  F  )  throw (ERParse) [virtual]

Read the number of nodes from file. Parameters: F  An input file stream This reads the number of graph nodes, the number of layout points and, if the graph is bipartite, the number of left-hand nodes. This operation must occur prior to all attribute read attempts. Reimplemented from abstractMixedGraph. Reimplemented in denseBiGraph.

TNode StableSet (   )  throw () [virtual]

Compute a maximum independent node set. Returns: The achieved stable set cardinality Reimplemented from abstractMixedGraph.

---

Field Documentation

TNode n1 [protected]

Number of left-hand nodes.

TNode n2 [protected]

Number of right-hand nodes.