Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
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.
 
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.
 
bool isValidComponent (const EdgeWeightedGraphCopy< T > &graph) const
 Checks if a given graph is a valid full component.
 

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.
 
template<typename CONTAINER >
void computePartialSolutions (const CONTAINER &nodeContainer)
 Computes all partial solutions for given m_terminalSubset.
 
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.
 
costOf (const List< node > &key) const
 Returns the cost of the partial solution given by key.
 
const DWMDatadataOf (const List< node > &key) const
 Returns a pointer to the relevant data of the partial solution given by key.
 
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.
 
void initializeMap ()
 Initializes the hash array with all node-terminal-pairs.
 
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.
 
void makeKey (List< node > &newSubset, node v) const
 Makes a list from the current terminal subset including an correctly inserted node v.
 
bool safeIfSumSmaller (const T summand1, const T summand2, const T compareValue) const
 Checks overflow-safe if summand1 plus summand2 is less than compareValue.
 

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.
 

Private Attributes

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

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 353 of file FullComponentGeneratorDreyfusWagner.h.

Member Function Documentation

◆ call()

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

Definition at line 367 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 230 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 273 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 212 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 135 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 128 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 315 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 383 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 286 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 391 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 191 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 182 of file FullComponentGeneratorDreyfusWagner.h.

◆ safeIfSumSmaller()

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

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

Definition at line 153 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 173 of file FullComponentGeneratorDreyfusWagner.h.

Member Data Documentation

◆ m_distance

A reference to the full distance matrix.

Definition at line 55 of file FullComponentGeneratorDreyfusWagner.h.

◆ m_G

A reference to the graph instance.

Definition at line 52 of file FullComponentGeneratorDreyfusWagner.h.

◆ m_isTerminal

A reference to the terminal incidence vector.

Definition at line 54 of file FullComponentGeneratorDreyfusWagner.h.

◆ m_map

A hash array for keys of size > 2.

Definition at line 125 of file FullComponentGeneratorDreyfusWagner.h.

◆ m_pred

A reference to the full predecessor matrix.

Definition at line 56 of file FullComponentGeneratorDreyfusWagner.h.

◆ m_terminals

A reference to the index-sorted list of terminals.

Definition at line 53 of file FullComponentGeneratorDreyfusWagner.h.

◆ m_terminalSubset

Handling subsets of terminals.

Definition at line 57 of file FullComponentGeneratorDreyfusWagner.h.


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