Tree packing


Functions

TCap abstractDiGraph::TreePacking (TNode root) throw (ERRange)
abstractDiGraph * abstractDiGraph::TreePKGInit (TCap *totalMulti, TNode root) throw ()
TCap abstractDiGraph::TreePKGStripTree (abstractDiGraph *G, TCap *multi, TNode root) throw (ERRange)

Function Documentation

TCap TreePacking (  TNode  root  )  throw (ERRange) [inherited]
 

Determine a maximum arborescence packing.

Parameters:
root The root node index in the range [0,1,..,n-1]
If the arc capacity bounds are all one, this determines a maximum number of disjoint spanning arborescences rooted at r, and this number matches the minimum cut capacity returned by StrongEdgeConnectivity(r).

In the general setting with non-trivial arc capacities, the constructed arborescences are not edge disjoint and hence cannot be completely saved to the edge colours. The particular spanning trees can be obtained either by the predecessor labels of the trace objects (set traceLevel>=3), or by calling TreePKGInit() and TreePKGStripTree() directly (and then using the predecessor trees of the manipulated digraph).

abstractDiGraph * TreePKGInit (  TCap *  totalMulti,
TNode  root
)  throw () [inherited]
 

Generate a digraph copy to be manipulated during the tree packing method and determine the total tree multiplicity.

Parameters:
totalMulti The multiplicity of all arborescences to be determined
root The root node index in range [0,1,..,n-1]
Returns:
Pointer to a digraph to be manipulated by TreePKGStripTree()

TCap TreePKGStripTree (  abstractDiGraph *  G,
TCap *  multi,
TNode  root
)  throw (ERRange) [inherited]
 

Reduce the arc capacities in the digraph copy according to the current arborescence and construct another arborescence if one exists.

Parameters:
G Pointer to the digraph to be manipulated
multi The remaining multiplicity
root The root node index in range [0,1,..,n-1]
Returns:
The capacity of the newly found arborescence