A generator for restricted full components (for Steiner tree approximations) based on the Dreyfus-Wagner algorithm that does not need a precomputed all-pair-shortest-paths matrix because single-source-shortest-path are used within. More...

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

Classes
class	AuxiliaryGraph
	Necessary because ogdf::EdgeWeightedGraphCopy<T> is rubbish. More...

struct	DWMData
	Subgraphs (given by other subgraphs and additional edges) 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
	FullComponentGeneratorDreyfusWagnerWithoutMatrix (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal)
	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 > &tree) const
	Checks if a given `tree` is a valid full component.

Private Member Functions
edge	addNewPath (DWMData &result, node curr, const NodeArray< edge > &pred) const
	Adds the shortest path from the source to `curr` into `result`.

template<typename CONTAINER >
void	computePartialSolutions (const CONTAINER &targets)
	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.

template<typename CONTAINER >
void	insertBestSubtrees (const CONTAINER &targets, const NodeArray< DWMSplit > &split, const NodeArray< edge > &pred, const NodeArray< T > &distance, const List< node > &terminals)
	Inserts the best subtrees into the hash map.

void	insertInvalidBestSubtree (node v, const NodeArray< T > &distance, const List< node > &newSubset)
	Inserts the invalid best subtree (based on the SSSP computation) into the hash map.

void	insertValidBestSubtree (node v, const NodeArray< DWMSplit > &split, const NodeArray< edge > &pred, const List< node > &newSubset, const List< node > &terminals)
	Inserts the valid best subtree (based on the SSSP computation) into the hash map.

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

void	updateAuxGraph (NodeArray< DWMSplit > &split, SubsetEnumerator< node > &subset, T oldCost)
	Updates the auxiliary graph.

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
AuxiliaryGraph	m_auxG
	An auxiliary graph to compute partial solutions.

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 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::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >

A generator for restricted full components (for Steiner tree approximations) based on the Dreyfus-Wagner algorithm that does not need a precomputed all-pair-shortest-paths matrix because single-source-shortest-path are used within.

See also R. E. Erickson, C. L. Monma, A. F. Veinott: Send-and-split method for minimum-concave-cost network flows. Math. Oper. Res. 12 (1987) 634-664.

Definition at line 55 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

Constructor & Destructor Documentation

◆ FullComponentGeneratorDreyfusWagnerWithoutMatrix()

template<typename T >

ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >::FullComponentGeneratorDreyfusWagnerWithoutMatrix	(	const EdgeWeightedGraph< T > &	G,
		const List< node > &	terminals,
		const NodeArray< bool > &	isTerminal
	)

inline

The constructor.

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

Definition at line 481 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

Member Function Documentation

◆ addNewPath()

template<typename T >

edge ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >::addNewPath	(	DWMData &	result,
		node	curr,
		const NodeArray< edge > &	pred
	)		const

inlineprivate

Adds the shortest path from the source to curr into result.

Returns: the edge of that path that is incident to the source

Definition at line 370 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ call()

template<typename T >

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

inline

Definition at line 491 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ computePartialSolutions()

template<typename T >

template<typename CONTAINER >

void ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >::computePartialSolutions ( const CONTAINER & targets )

inlineprivate

Computes all partial solutions for given m_terminalSubset.

Definition at line 304 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ computeSplit()

template<typename T >

void ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< 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 edges represents a tree.

Definition at line 285 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ costOf()

template<typename T >

T ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >::costOf ( const List< node > & key ) const

inlineprivate

Returns the cost of the partial solution given by key.

Definition at line 220 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ dataOf()

template<typename T >

const DWMData * ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< 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 213 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ getSteinerTreeFor() [1/2]

template<typename T >

T ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< 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 442 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ getSteinerTreeFor() [2/2]

template<typename T >

T ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< 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 508 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ initializeMap()

template<typename T >

void ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >::initializeMap ( )

inlineprivate

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

Definition at line 326 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ insertBestSubtrees()

template<typename T >

template<typename CONTAINER >

void ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >::insertBestSubtrees	(	const CONTAINER &	targets,
		const NodeArray< DWMSplit > &	split,
		const NodeArray< edge > &	pred,
		const NodeArray< T > &	distance,
		const List< node > &	terminals
	)

inlineprivate

Inserts the best subtrees into the hash map.

Definition at line 422 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ insertInvalidBestSubtree()

template<typename T >

void ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >::insertInvalidBestSubtree	(	node	v,
		const NodeArray< T > &	distance,
		const List< node > &	newSubset
	)

inlineprivate

Inserts the invalid best subtree (based on the SSSP computation) into the hash map.

Definition at line 392 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ insertValidBestSubtree()

template<typename T >

void ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >::insertValidBestSubtree	(	node	v,
		const NodeArray< DWMSplit > &	split,
		const NodeArray< edge > &	pred,
		const List< node > &	newSubset,
		const List< node > &	terminals
	)

inlineprivate

Inserts the valid best subtree (based on the SSSP computation) into the hash map.

Definition at line 401 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ isValidComponent()

template<typename T >

bool ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >::isValidComponent ( const EdgeWeightedGraphCopy< T > & tree ) const

inline

Checks if a given tree is a valid full component.

Definition at line 516 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ makeKey() [1/2]

template<typename T >

void ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< 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 264 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ makeKey() [2/2]

template<typename T >

void ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< 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 255 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ safeIfSumSmaller()

template<typename T >

bool ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< 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 226 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ sortedInserter()

template<typename T >

static void ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< 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

Definition at line 246 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ updateAuxGraph()

template<typename T >

void ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >::updateAuxGraph	(	NodeArray< DWMSplit > &	split,
		SubsetEnumerator< node > &	subset,
		T	oldCost
	)