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)

T	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.

T	costOf (const List< node > &key) const
	Returns the cost of the partial solution given by `key`.

const DWMData *	dataOf (const List< node > &key) const
	Returns a pointer to the relevant data of the partial solution given by `key`.

T	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, SortedNodeListHashFunc >	m_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< node >	m_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 61 of file FullComponentGeneratorDreyfusWagner.h.

Member Typedef Documentation

◆ NodePairs

template<typename T >

using ogdf::steiner_tree::FullComponentGeneratorDreyfusWagner< T >::NodePairs = ArrayBuffer<NodePair>

private

Definition at line 69 of file FullComponentGeneratorDreyfusWagner.h.

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

Member Function Documentation

◆ call()

template<typename T >

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

inline

Definition at line 377 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 240 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 283 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 222 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 145 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 138 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 325 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 393 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 296 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 401 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 201 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 192 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 163 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

w	Node argument for the callback
list	Resulting list
inserted	Whether `newNode` was inserted; must be initialized to `false`
newNode	New node to be inserted into the list