Colouring

Data Structures
class	branchColour
	Branch & bound implementation for node colouring. More...
Functions
virtual TNode	abstractMixedGraph::NodeColouring (TNode k=NoNode) throw ()
bool	abstractMixedGraph::NCKempeExchange (TNode *nodeColour, TNode r, TNode x) throw (ERRange,ERRejected)
TNode	abstractMixedGraph::CliqueCover (TNode k=NoNode) throw ()
TArc	abstractMixedGraph::EdgeColouring (TArc k=NoNode) throw (ERRange)

---

Function Documentation

TNode CliqueCover (  TNode  k = NoNode  )  throw () [inherited]

Partition the node set into cliques. Parameters: k  The accepted number of cliques Returns: The achieved number of cliques

TArc EdgeColouring (  TArc  k = NoNode  )  throw (ERRange) [inherited]

Partition the edge set into independent sets. Parameters: k  The accepted number of independent sets Returns: The achieved number of independent sets

bool NCKempeExchange (  TNode *  nodeColour, TNode  r, TNode  x )  throw (ERRange,ERRejected) [inherited]

Modify a given colouring by alternating two colours in a Kempe component. Parameters: nodeColour  A pointer to an arry of node colours r  A node which is recoloured x  A node which should not be recoloured Return values: true  r and x are in different Kempe components This takes the colours of r and x and flips the colours in the Kempe component (the connected component spanned by both colours) of r.

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

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