Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::steiner_tree::FullComponentGeneratorDreyfusWagner< T > Class Template Reference

A generator for restricted full components (for Steiner tree approximations) based on the Dreyfus-Wagner algorithm. More...

#include <ogdf/graphalg/steiner_tree/FullComponentGeneratorDreyfusWagner.h>

Classes

struct  DWMData
 Subgraphs (given by other subgraphs and additional node pairs) and their cost for a partial solution. More...
 
struct  DWMSplit
 A collection of two subgraphs and their total cost. More...
 
class  SortedNodeListHashFunc
 

Public Member Functions

 FullComponentGeneratorDreyfusWagner (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, const NodeArray< NodeArray< T >> &distance, const NodeArray< NodeArray< edge >> &pred)
 The constructor. More...
 
void call (int restricted)
 
getSteinerTreeFor (const List< node > &terminals, EdgeWeightedGraphCopy< T > &tree) const
 Constructs a Steiner tree for the given set of terminals if it is valid, otherwise an empty tree is returned. More...
 
bool isValidComponent (const EdgeWeightedGraphCopy< T > &graph) const
 Checks if a given graph is a valid full component. More...
 

Private Types

using NodePairs = ArrayBuffer< NodePair >
 

Private Member Functions

void computePartialSolution (NodeArray< DWMSplit > &split, node v, SubsetEnumerator< node > &subset, const List< node > &terminals)
 Computes a partial solution for given terminals and node v. More...
 
template<typename CONTAINER >
void computePartialSolutions (const CONTAINER &nodeContainer)
 Computes all partial solutions for given m_terminalSubset. More...
 
void computeSplit (NodeArray< DWMSplit > &split, node v, SubsetEnumerator< node > &subset) const
 Populates split that contains a partial solution for an included nonterminal v in m_G. More...
 
costOf (const List< node > &key) const
 Returns the cost of the partial solution given by key. More...
 
const DWMDatadataOf (const List< node > &key) const
 Returns a pointer to the relevant data of the partial solution given by key. More...
 
getSteinerTreeFor (const DWMData &data, EdgeWeightedGraphCopy< T > &tree) const
 Adds edges to construct a Steiner tree from the given data (recursively) if the data is valid. More...
 
void initializeMap ()
 Initializes the hash array with all node-terminal-pairs. More...
 
void makeKey (List< node > &newSubset, List< node > &newComplement, const SubsetEnumerator< node > &subset, node v) const
 Makes a list from subset and its complement, each including an correctly inserted node v. More...
 
void makeKey (List< node > &newSubset, node v) const
 Makes a list from the current terminal subset including an correctly inserted node v. More...
 
bool safeIfSumSmaller (const T summand1, const T summand2, const T compareValue) const
 Checks overflow-safe if summand1 plus summand2 is less than compareValue. More...
 

Static Private Member Functions

static void sortedInserter (node w, List< node > &list, bool &inserted, node newNode)
 Is being used as a callback to ogdf::SubsetEnumerator's forEach* methods to get the subset plus a correctly inserted newNode (ie, sorted by index) into list. More...
 

Private Attributes

const NodeArray< NodeArray< T > > & m_distance
 A reference to the full distance matrix. More...
 
const EdgeWeightedGraph< T > & m_G
 A reference to the graph instance. More...
 
const NodeArray< bool > & m_isTerminal
 A reference to the terminal incidence vector. More...
 
Hashing< List< node >, DWMData, SortedNodeListHashFuncm_map
 A hash array for keys of size > 2. More...
 
const NodeArray< NodeArray< edge > > & m_pred
 A reference to the full predecessor matrix. More...
 
const List< node > & m_terminals
 A reference to the index-sorted list of terminals. More...
 
SubsetEnumerator< nodem_terminalSubset
 Handling subsets of terminals. More...
 

Detailed Description

template<typename T>
class ogdf::steiner_tree::FullComponentGeneratorDreyfusWagner< T >

A generator for restricted full components (for Steiner tree approximations) based on the Dreyfus-Wagner algorithm.

This generator can handle (and exploit) predecessor matrices that use nullptr instead of resembling shortest paths over terminals. (See the terminal-preferring shortest path algorithms in ogdf::MinSteinerTreeModule<T>.)

Definition at line 51 of file FullComponentGeneratorDreyfusWagner.h.

Member Typedef Documentation

◆ NodePairs

Constructor & Destructor Documentation

◆ FullComponentGeneratorDreyfusWagner()

template<typename T >
ogdf::steiner_tree::FullComponentGeneratorDreyfusWagner< T >::FullComponentGeneratorDreyfusWagner ( const EdgeWeightedGraph< T > &  G,
const List< node > &  terminals,
const NodeArray< bool > &  isTerminal,
const NodeArray< NodeArray< T >> &  distance,
const NodeArray< NodeArray< edge >> &  pred 
)
inline

The constructor.

Precondition
The list of terminals has to be sorted by index (use MinSteinerTreeModule<T>::sortTerminals)

Definition at line 360 of file FullComponentGeneratorDreyfusWagner.h.

Member Function Documentation

◆ call()

template<typename T >
void ogdf::steiner_tree::FullComponentGeneratorDreyfusWagner< T >::call ( int  restricted)
inline

Definition at line 374 of file FullComponentGeneratorDreyfusWagner.h.

◆ computePartialSolution()

template<typename T >
void ogdf::steiner_tree::FullComponentGeneratorDreyfusWagner< T >::computePartialSolution ( NodeArray< DWMSplit > &  split,
node  v,
SubsetEnumerator< node > &  subset,
const List< node > &  terminals 
)
inlineprivate

Computes a partial solution for given terminals and node v.

Definition at line 234 of file FullComponentGeneratorDreyfusWagner.h.

◆ computePartialSolutions()

template<typename T >
template<typename CONTAINER >
void ogdf::steiner_tree::FullComponentGeneratorDreyfusWagner< T >::computePartialSolutions ( const CONTAINER &  nodeContainer)
inlineprivate

Computes all partial solutions for given m_terminalSubset.

Definition at line 280 of file FullComponentGeneratorDreyfusWagner.h.

◆ computeSplit()

template<typename T >
void ogdf::steiner_tree::FullComponentGeneratorDreyfusWagner< T >::computeSplit ( NodeArray< DWMSplit > &  split,
node  v,
SubsetEnumerator< node > &  subset 
) const
inlineprivate

Populates split that contains a partial solution for an included nonterminal v in m_G.

Note that it is not guaranteed that any resulting collection of node pairs represents a tree.

Definition at line 217 of file FullComponentGeneratorDreyfusWagner.h.

◆ costOf()

template<typename T >
T ogdf::steiner_tree::FullComponentGeneratorDreyfusWagner< T >::costOf ( const List< node > &  key) const
inlineprivate

Returns the cost of the partial solution given by key.

Definition at line 136 of file FullComponentGeneratorDreyfusWagner.h.

◆ dataOf()

template<typename T >
const DWMData* ogdf::steiner_tree::FullComponentGeneratorDreyfusWagner< T >::dataOf ( const List< node > &  key) const
inlineprivate

Returns a pointer to the relevant data of the partial solution given by key.

Definition at line 129 of file FullComponentGeneratorDreyfusWagner.h.

◆ getSteinerTreeFor() [1/2]

template<typename T >
T ogdf::steiner_tree::FullComponentGeneratorDreyfusWagner< T >::getSteinerTreeFor ( const DWMData data,
EdgeWeightedGraphCopy< T > &  tree 
) const
inlineprivate

Adds edges to construct a Steiner tree from the given data (recursively) if the data is valid.

Definition at line 322 of file FullComponentGeneratorDreyfusWagner.h.

◆ getSteinerTreeFor() [2/2]

template<typename T >
T ogdf::steiner_tree::FullComponentGeneratorDreyfusWagner< T >::getSteinerTreeFor ( const List< node > &  terminals,
EdgeWeightedGraphCopy< T > &  tree 
) const
inline

Constructs a Steiner tree for the given set of terminals if it is valid, otherwise an empty tree is returned.

Definition at line 390 of file FullComponentGeneratorDreyfusWagner.h.

◆ initializeMap()

template<typename T >
void ogdf::steiner_tree::FullComponentGeneratorDreyfusWagner< T >::initializeMap ( )
inlineprivate

Initializes the hash array with all node-terminal-pairs.

Definition at line 293 of file FullComponentGeneratorDreyfusWagner.h.

◆ isValidComponent()

template<typename T >
bool ogdf::steiner_tree::FullComponentGeneratorDreyfusWagner< T >::isValidComponent ( const EdgeWeightedGraphCopy< T > &  graph) const
inline

Checks if a given graph is a valid full component.

Definition at line 398 of file FullComponentGeneratorDreyfusWagner.h.

◆ makeKey() [1/2]

template<typename T >
void ogdf::steiner_tree::FullComponentGeneratorDreyfusWagner< T >::makeKey ( List< node > &  newSubset,
List< node > &  newComplement,
const SubsetEnumerator< node > &  subset,
node  v 
) const
inlineprivate

Makes a list from subset and its complement, each including an correctly inserted node v.

Definition at line 196 of file FullComponentGeneratorDreyfusWagner.h.

◆ makeKey() [2/2]

template<typename T >
void ogdf::steiner_tree::FullComponentGeneratorDreyfusWagner< T >::makeKey ( List< node > &  newSubset,
node  v 
) const
inlineprivate

Makes a list from the current terminal subset including an correctly inserted node v.

Definition at line 186 of file FullComponentGeneratorDreyfusWagner.h.

◆ safeIfSumSmaller()

template<typename T >
bool ogdf::steiner_tree::FullComponentGeneratorDreyfusWagner< T >::safeIfSumSmaller ( const T  summand1,
const T  summand2,
const T  compareValue 
) const
inlineprivate

Checks overflow-safe if summand1 plus summand2 is less than compareValue.

Definition at line 154 of file FullComponentGeneratorDreyfusWagner.h.

◆ sortedInserter()

template<typename T >
static void ogdf::steiner_tree::FullComponentGeneratorDreyfusWagner< T >::sortedInserter ( node  w,
List< node > &  list,
bool &  inserted,
node  newNode 
)
inlinestaticprivate

Is being used as a callback to ogdf::SubsetEnumerator's forEach* methods to get the subset plus a correctly inserted newNode (ie, sorted by index) into list.

This takes linear time in comparison to copy, insert, sort which takes average case O(n log n) time.

Parameters
wNode argument for the callback
listResulting list
insertedWhether newNode was inserted; must be initialized to false
newNodeNew node to be inserted into the list

Definition at line 176 of file FullComponentGeneratorDreyfusWagner.h.

Member Data Documentation

◆ m_distance

template<typename T >
const NodeArray<NodeArray<T> >& ogdf::steiner_tree::FullComponentGeneratorDreyfusWagner< T >::m_distance
private

A reference to the full distance matrix.

Definition at line 56 of file FullComponentGeneratorDreyfusWagner.h.

◆ m_G

template<typename T >
const EdgeWeightedGraph<T>& ogdf::steiner_tree::FullComponentGeneratorDreyfusWagner< T >::m_G
private

A reference to the graph instance.

Definition at line 53 of file FullComponentGeneratorDreyfusWagner.h.

◆ m_isTerminal

template<typename T >
const NodeArray<bool>& ogdf::steiner_tree::FullComponentGeneratorDreyfusWagner< T >::m_isTerminal
private

A reference to the terminal incidence vector.

Definition at line 55 of file FullComponentGeneratorDreyfusWagner.h.

◆ m_map

A hash array for keys of size > 2.

Definition at line 123 of file FullComponentGeneratorDreyfusWagner.h.

◆ m_pred

template<typename T >
const NodeArray<NodeArray<edge> >& ogdf::steiner_tree::FullComponentGeneratorDreyfusWagner< T >::m_pred
private

A reference to the full predecessor matrix.

Definition at line 57 of file FullComponentGeneratorDreyfusWagner.h.

◆ m_terminals

template<typename T >
const List<node>& ogdf::steiner_tree::FullComponentGeneratorDreyfusWagner< T >::m_terminals
private

A reference to the index-sorted list of terminals.

Definition at line 54 of file FullComponentGeneratorDreyfusWagner.h.

◆ m_terminalSubset

template<typename T >
SubsetEnumerator<node> ogdf::steiner_tree::FullComponentGeneratorDreyfusWagner< T >::m_terminalSubset
private

Handling subsets of terminals.

Definition at line 58 of file FullComponentGeneratorDreyfusWagner.h.


The documentation for this class was generated from the following file: