Matchings & T-Joins

Functions
virtual bool	abstractGraph::MaximumMatching () throw ()
virtual bool	abstractGraph::MaximumMatching (TCap cDeg) throw ()
virtual bool	abstractGraph::MaximumMatching (TCap *pLower, TCap *pDeg=NULL) throw ()
virtual bool	abstractGraph::MinCMatching () throw ()
virtual bool	abstractGraph::MinCMatching (TCap cDeg) throw ()
virtual bool	abstractGraph::MinCMatching (TCap *pLower, TCap *pDeg=NULL) throw ()
TFloat	abstractGraph::PMHeuristicsRandom () throw ()
TFloat	abstractGraph::MinCEdgeCover () throw (ERRejected)
void	abstractGraph::ComputeTJoin (const indexSet< TNode > &Terminals) throw (ERRejected)
void	abstractGraph::MinCTJoin (const indexSet< TNode > &Terminals) throw ()
bool	abstractGraph::SPX_TJoin (TNode s, TNode t) throw (ERRange)

---

Function Documentation

void ComputeTJoin (  const indexSet< TNode > &  Terminals  )  throw (ERRejected) [protected, inherited]

Compute a T-join for a given node set T. Parameters: Terminals  A set of terminal nodes. Must have even cardinality This is the working procedure for all kinds of T-join solvers. It requires non-negative edge lengths.

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

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

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

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

bool MaximumMatching (   )  throw () [virtual, inherited]

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

TFloat MinCEdgeCover (   )  throw (ERRejected) [inherited]

Provide a minimum length edge cover by the edge colour register. Returns: The total edge length

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

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

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

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

bool MinCMatching (   )  throw () [virtual, inherited]

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

void MinCTJoin (  const indexSet< TNode > &  Terminals  )  throw () [inherited]

Compute a T-join for a given node set T. Parameters: Terminals  A set of terminal nodes. Must have even cardinality Other than ComputeTJoin(), this can deal with negative length arcs.

TFloat PMHeuristicsRandom (   )  throw () [protected, inherited]

Determine a minimum-cost perfect (b,c)-matching by a random heuristic. Returns: The weight of the constructed matching This step-by-step chooses random nodes and add adjacent arcs increasing by their lenght.

bool SPX_TJoin (  TNode  s, TNode  t )  throw (ERRange) [inherited]

Compute a shortest path connecting a given node pair. Parameters: s  The start node of the path to be generated t  The end node of the path to be generated Return values: true  A shortest st-path has been found Other than general shortest path methods applied to undirected graphs, this can deal with negative length arcs. The found path is provided by the subgraph labels.