Steiner trees

Functions
TFloat	abstractGraph::STT_Heuristic (const indexSet< TNode > &Terminals, TNode root) throw (ERRange)
TFloat	abstractGraph::STT_Enumerate (const indexSet< TNode > &Terminals, TNode root) throw (ERRange)
TFloat	abstractMixedGraph::SteinerTree (const indexSet< TNode > &Terminals, TNode root=NoNode) throw (ERRange,ERRejected)
TFloat	abstractMixedGraph::STT_TrimLeaves (const indexSet< TNode > &Terminals, TArc *pred) throw ()
virtual TFloat	abstractMixedGraph::STT_Heuristic (const indexSet< TNode > &Terminals, TNode root) throw (ERRange)
virtual TFloat	abstractMixedGraph::STT_Enumerate (const indexSet< TNode > &Terminals, TNode root) throw (ERRange)

---

Function Documentation

TFloat SteinerTree (  const indexSet< TNode > &  Terminals, TNode  root = NoNode )  throw (ERRange,ERRejected) [inherited]

Determine a minimum length discrete Steiner tree. Parameters: Terminals  An index set of terminal nodes in the range [0,1,..,n] root  A node in the range [0,1,..,n] Returns: The length of the found Steiner tree

virtual TFloat STT_Enumerate (  const indexSet< TNode > &  Terminals, TNode  root )  throw (ERRange) [protected, virtual, inherited]

Brute force enumeration of discrete Steiner trees. Parameters: Terminals  An index set of terminal nodes in the range [0,1,..,n] root  A node in the range [0,1,..,n] Returns: The length of the found Steiner tree This iterates over all Steiner node subsets and computes a spanning tree of the complementary subgraph. Only the applied spanning tree method differs between undirected and general graphs. Reimplemented in abstractGraph.

TFloat STT_Enumerate (  const indexSet< TNode > &  Terminals, TNode  root )  throw (ERRange) [protected, virtual, inherited]

Brute force enumeration of discrete Steiner trees. Parameters: Terminals  An index set of terminal nodes in the range [0,1,..,n] root  A node in the range [0,1,..,n] Returns: The length of the found Steiner tree This iterates over all Steiner node subsets and computes a spanning tree of the complementary subgraph. Only the applied spanning tree method differs between undirected and general graphs. Reimplemented from abstractMixedGraph.

virtual TFloat STT_Heuristic (  const indexSet< TNode > &  Terminals, TNode  root )  throw (ERRange) [protected, virtual, inherited]

Steiner tree construction heuristic. Parameters: Terminals  An index set of terminal nodes in the range [0,1,..,n] root  A node in the range [0,1,..,n] Returns: The length of the found Steiner tree This simply determines a minimum spanning tree and then calls STT_TrimLeaves(). Reimplemented in abstractGraph.

TFloat STT_Heuristic (  const indexSet< TNode > &  Terminals, TNode  root )  throw (ERRange) [protected, virtual, inherited]

Compute a Steiner tree by the Mehlhorn heuristic. Parameters: Terminals  An index set of terminal nodes in the range [0,1,..,n] root  A node in the range [0,1,..,n] Returns: The length of the found Steiner tree This uses a discrete Voronoi diagram which is obtained by simultaneous search for shortest path trees from all terminal nodes. The found partial trees are shrunk, and on the resulting graph a minimum spanning tree is computed. This tree maps back to a Steiner tree in the original graph. The procedure requires non-negative edge length. It is 1-approximative, that is, the constructed tree is twice as long as an optimal Steiner tree in the worst case. Reimplemented from abstractMixedGraph.

TFloat STT_TrimLeaves (  const indexSet< TNode > &  Terminals, TArc *  pred )  throw () [protected, inherited]

Turn a given spanning tree into a Steiner tree by successively deleting all Steiner nodes. Parameters: Terminals  An index set of terminal nodes in the range [0,1,..,n] pred  An array of predecessor arcs Returns: The sum of lengths of the deleted arcs This turns a spanning tree given by the predecessor arcs in pred[] into a Steiner tree by successively deleting all Steiner nodes which are leaves.