Spanning tree methods


Enumerations

enum  abstractMixedGraph::TMethMST {
  abstractMixedGraph::MST_DEFAULT = -1,
  abstractMixedGraph::MST_PRIM = 0,
  abstractMixedGraph::MST_PRIM2 = 1,
  abstractMixedGraph::MST_KRUSKAL = 2,
  abstractMixedGraph::MST_EDMONDS = 3
}
enum  abstractMixedGraph::TOptMST {
  abstractMixedGraph::MST_PLAIN = 0,
  abstractMixedGraph::MST_ONE_CYCLE = 1,
  abstractMixedGraph::MST_UNDIRECTED = 2,
  abstractMixedGraph::MST_DIRECTED = 4,
  abstractMixedGraph::MST_REDUCED = 8,
  abstractMixedGraph::MST_ONE_CYCLE_REDUCED = 9,
  abstractMixedGraph::MST_MAX = 16
}

Functions

TFloat abstractMixedGraph::MinTree (TNode root=NoNode) throw (ERRange,ERRejected)
TFloat abstractMixedGraph::MinTree (TMethMST method, TOptMST characteristic, TNode root=NoNode) throw (ERRange,ERRejected)
bool abstractMixedGraph::ExtractTree (TNode root, TOptMST characteristic=MST_PLAIN) throw (ERRejected)
bool abstractMixedGraph::ExtractTree (TArc *const pred, TNode root, TOptMST characteristic=MST_PLAIN) throw (ERRejected)
TFloat abstractMixedGraph::MST_Prim (TMethMST method, TOptMST characteristic, TNode root=NoNode) throw (ERRange,ERRejected)
TFloat abstractMixedGraph::MST_Edmonds (TOptMST characteristic, TNode root=NoNode) throw (ERRange,ERRejected)
TFloat abstractMixedGraph::MST_Kruskal (TOptMST characteristic, TNode root=NoNode) throw (ERRange,ERRejected)

Enumeration Type Documentation

enum TMethMST [inherited]
 

Alternative methods for the spanning tree solver.

Enumerator:
MST_DEFAULT  Apply the default method set in goblinController::methMST.
MST_PRIM  Apply the Prim method.
MST_PRIM2  Apply the enhanced Prim method.
MST_KRUSKAL  Apply the Kruskal greedy method.
MST_EDMONDS  Apply the Edmonds arborescence method.

enum TOptMST [inherited]
 

Modifiers for the objective of spanning tree optimization.

Enumerator:
MST_PLAIN  Run solver in the default mode.
MST_ONE_CYCLE  Determine a subgraph with exactly one cycle, exposing the root node.
MST_UNDIRECTED  Ignore the arc orientations.
MST_DIRECTED  Take care of the arc orientations.
MST_REDUCED  Take care of the node potentials, optimize w.r.t. the reduced length labels.
MST_ONE_CYCLE_REDUCED  Combination of MST_ONE_CYCLE and MST_ONE_CYCLE_REDUCED.
MST_MAX  Maximize the total edge length instead of minimizing it.

Function Documentation

bool ExtractTree (  TArc *const   pred,
TNode  root,
TOptMST  characteristic = MST_PLAIN
)  throw (ERRejected) [inherited]
 

Check if the current subgraph encodes a spanning tree and save it to an array.

Parameters:
pred The array where predecessor labels are stored
root The desired root node
characteristic Valid options are MST_ONE_CYCLE and MST_DIRECTED
Return values:
true The current subgraph could be validated

bool ExtractTree (  TNode  root,
TOptMST  characteristic = MST_PLAIN
)  throw (ERRejected) [inherited]
 

Check if the current subgraph encodes a spanning tree and save it to the predecessor labels.

Parameters:
root The root node of the arborescence
characteristic Valid options are MST_ONE_CYCLE and MST_DIRECTED
Return values:
true The current subgraph could be validated

TFloat MinTree (  TMethMST  method,
TOptMST  characteristic,
TNode  root = NoNode
)  throw (ERRange,ERRejected) [inherited]
 

Compute a minimum spanning tree or a related subgraph structure.

Parameters:
method A TMethMST value specifying the applied method
characteristic A bit combination of TOptMST values
root The root node of the arborescence
Returns:
The total arc length of the derived subgraph
This is the public interface to all spanning tree methods. By specifying methods and characteristics, the properties of the subgraph can be varied

TFloat MinTree (  TNode  root = NoNode  )  throw (ERRange,ERRejected) [inherited]
 

Compute a minimum spanning tree or a related subgraph structure.

Parameters:
root The intended root node
Returns:
The total arc length of the derived subgraph
This is the public interface to all spanning tree methods.

TFloat MST_Edmonds (  TOptMST  characteristic,
TNode  root = NoNode
)  throw (ERRange,ERRejected) [protected, inherited]
 

Edmonds' minimum spanning arborescence method.

Parameters:
characteristic A bit combination of TOptMST modifiers
root The root node of the arborescence
Returns:
The total arc length of the derived subgraph
This method saves the spanning tree to the predecessor labels. Other than the Prim and the Kruskal method, arc directions are considered.

TFloat MST_Kruskal (  TOptMST  characteristic,
TNode  root = NoNode
)  throw (ERRange,ERRejected) [protected, inherited]
 

Kruskals minimum spanning tree method.

Parameters:
characteristic A bit combination of TOptMST modifiers
root The root node of the arborescence
Returns:
The total arc length of the derived subgraph
This method saves the spanning tree to the subgraph data structure. If the graph is disconnected, the connected components are saved to the partition data structure.

TFloat MST_Prim (  TMethMST  method,
TOptMST  characteristic,
TNode  root = NoNode
)  throw (ERRange,ERRejected) [protected, inherited]
 

Prims minimum spanning tree method.

Parameters:
method Either MST_PRIM or MST_PRIM2
characteristic A bit combination of TOptMST modifiers
root The root node of the arborescence
Returns:
The total arc length of the derived subgraph
This method saves the spanning tree to the predecessor labels.