#include <ogdf/graphalg/MinSteinerTreeRZLoss.h>

Public Member Functions
	Main (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, int restricted)

T	getApproximation (EdgeWeightedGraphCopy< T > *&finalSteinerTree) const

long	numberOfComponentLookUps ()
	Returns the number of components lookups during execution time.

long	numberOfContractedComponents ()
	Returns the number of contracted components.

long	numberOfGeneratedComponents ()
	Returns the number of generated components.

Private Types
template<typename TYPE >
using	SaveStatic = steiner_tree::SaveStatic< TYPE >

Private Member Functions
void	contractLoss (EdgeWeightedGraphCopy< T > &steinerTree, int compId)
	Contracts the loss of a full component and integrates it into the given terminal-spanning tree.

double	extractMaxComponent (const EdgeWeightedGraphCopy< T > &steinerTree, int &maxCompId)
	Traverses over all full components and finds the one with the highest win-objective.

template<typename TERMINAL_CONTAINER >
T	gain (const TERMINAL_CONTAINER &terminals, const EdgeWeightedGraphCopy< T > &steinerTree)

void	generateInitialTerminalSpanningTree (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< NodeArray< T > > &distance, const NodeArray< NodeArray< edge > > &pred)
	Builds a minimum terminal spanning tree (via a MST call on the complete terminal graph)

void	multiPass (EdgeWeightedGraphCopy< T > &steinerTree)
	Contraction phase of the algorithm.

void	setup (EdgeWeightedGraphCopy< T > &tree)
	Setup (build initial terminal-spanning tree, its save data structure, and find all components)

Finding full components
void	findFullComponentsDW (const EdgeWeightedGraphCopy< T > &tree, const NodeArray< NodeArray< T > > &distance, const NodeArray< NodeArray< edge > > &pred)
	Find full components using algorithm by Dreyfus-Wagner.

void	findFullComponentsEMV (const EdgeWeightedGraphCopy< T > &tree)
	Find full components using algorithm by Erickson et al.

void	findFull3Components (const EdgeWeightedGraphCopy< T > &tree, const NodeArray< NodeArray< T > > &distance, const NodeArray< NodeArray< edge > > &pred)
	Find full components of size 3.

template<typename FCG >
void	retrieveComponents (const FCG &fcg, const EdgeWeightedGraphCopy< T > &tree)
	Auxiliary function to retrieve components by Dreyfus-Wagner/Erickson et al implementation.

Private Attributes
long	m_componentsContracted
	Number of contracted components.

long	m_componentsGenerated
	Number of generated components.

long	m_componentsLookUps
	Number of components lookups.

steiner_tree::FullComponentWithLossStore< T >	m_fullCompStore
	All generated full components.

const EdgeWeightedGraph< T > &	m_G
	The original edge-weighted graph.

NodeArray< bool >	m_isNewTerminal
	Incidence vector for nonterminal nodes marked as terminals for improvement.

const NodeArray< bool > &	m_isTerminal
	Incidence vector for terminal nodes.

int	m_restricted
	Parameter for the number of terminals in a full component.

std::unique_ptr< steiner_tree::SaveStatic< T > >	m_save
	The save data structure.

List< node >	m_terminals
	List of terminal nodes (will be copied and sorted)

Detailed Description

template<typename T>
class ogdf::MinSteinerTreeRZLoss< T >::Main

Definition at line 140 of file MinSteinerTreeRZLoss.h.

Member Typedef Documentation

◆ SaveStatic

template<typename T >

template<typename TYPE >

using ogdf::MinSteinerTreeRZLoss< T >::Main::SaveStatic = steiner_tree::SaveStatic<TYPE>

private

Definition at line 142 of file MinSteinerTreeRZLoss.h.

Constructor & Destructor Documentation

◆ Main()

template<typename T >

ogdf::MinSteinerTreeRZLoss< T >::Main::Main	(	const EdgeWeightedGraph< T > &	G,
		const List< node > &	terminals,
		const NodeArray< bool > &	isTerminal,
		int	restricted
	)

Definition at line 269 of file MinSteinerTreeRZLoss.h.

Member Function Documentation

◆ contractLoss()

template<typename T >

void ogdf::MinSteinerTreeRZLoss< T >::Main::contractLoss	(	EdgeWeightedGraphCopy< T > &	steinerTree,
		int	compId
	)

private

Contracts the loss of a full component and integrates it into the given terminal-spanning tree.

Parameters

steinerTree	The Steiner tree into which the full component is integrated
compId	The full component to be contracted and inserted

Definition at line 460 of file MinSteinerTreeRZLoss.h.

◆ extractMaxComponent()

template<typename T >

double ogdf::MinSteinerTreeRZLoss< T >::Main::extractMaxComponent	(	const EdgeWeightedGraphCopy< T > &	steinerTree,
		int &	maxCompId
	)

private

Traverses over all full components and finds the one with the highest win-objective.

Parameters

steinerTree	Current Steiner tree
maxCompId	The index of the full component with highest win-objective

Returns: the win-objective of the returned full component

Definition at line 410 of file MinSteinerTreeRZLoss.h.

◆ findFull3Components()

template<typename T >

void ogdf::MinSteinerTreeRZLoss< T >::Main::findFull3Components	(	const EdgeWeightedGraphCopy< T > &	tree,
		const NodeArray< NodeArray< T > > &	distance,
		const NodeArray< NodeArray< edge > > &	pred
	)

private

Find full components of size 3.

Definition at line 323 of file MinSteinerTreeRZLoss.h.

◆ findFullComponentsDW()

template<typename T >

void ogdf::MinSteinerTreeRZLoss< T >::Main::findFullComponentsDW	(	const EdgeWeightedGraphCopy< T > &	tree,
		const NodeArray< NodeArray< T > > &	distance,
		const NodeArray< NodeArray< edge > > &	pred
	)

private

Find full components using algorithm by Dreyfus-Wagner.

Parameters

tree	Current minimal terminal spanning tree
distance	The distance matrix
pred	The predecessor matrix for shortest paths

Definition at line 370 of file MinSteinerTreeRZLoss.h.

◆ findFullComponentsEMV()

template<typename T >

void ogdf::MinSteinerTreeRZLoss< T >::Main::findFullComponentsEMV ( const EdgeWeightedGraphCopy< T > & tree )

private

Find full components using algorithm by Erickson et al.

Definition at line 379 of file MinSteinerTreeRZLoss.h.

◆ gain()

template<typename T >

template<typename TERMINAL_CONTAINER >

T ogdf::MinSteinerTreeRZLoss< T >::Main::gain	(	const TERMINAL_CONTAINER &	terminals,
		const EdgeWeightedGraphCopy< T > &	steinerTree
	)

private

   \brief Calculates the gain for a full component

*
Parameters

terminals The terminals of the full component

steinerTree Current Steiner tree

Returns
the gain (cost of save edges) of the returned full component

Definition at line 438 of file MinSteinerTreeRZLoss.h.

◆ generateInitialTerminalSpanningTree()

template<typename T >

void ogdf::MinSteinerTreeRZLoss< T >::Main::generateInitialTerminalSpanningTree	(	EdgeWeightedGraphCopy< T > &	steinerTree,
		const NodeArray< NodeArray< T > > &	distance,
		const NodeArray< NodeArray< edge > > &	pred
	)

private

Builds a minimum terminal spanning tree (via a MST call on the complete terminal graph)

Parameters

steinerTree	The resulting minimum terminal spanning tree
distance	The distance matrix
pred	The predecessor matrix for shortest paths

Definition at line 299 of file MinSteinerTreeRZLoss.h.

◆ getApproximation()

template<typename T >

T ogdf::MinSteinerTreeRZLoss< T >::Main::getApproximation ( EdgeWeightedGraphCopy< T > *& finalSteinerTree ) const

inline

Definition at line 252 of file MinSteinerTreeRZLoss.h.

◆ multiPass()

template<typename T >

void ogdf::MinSteinerTreeRZLoss< T >::Main::multiPass ( EdgeWeightedGraphCopy< T > & steinerTree )

private

Contraction phase of the algorithm.

Parameters

steinerTree the terminal-spanning tree to be modified

Definition at line 387 of file MinSteinerTreeRZLoss.h.

◆ numberOfComponentLookUps()

template<typename T >

long ogdf::MinSteinerTreeRZLoss< T >::Main::numberOfComponentLookUps ( )

inline

Returns the number of components lookups during execution time.

Definition at line 265 of file MinSteinerTreeRZLoss.h.

◆ numberOfContractedComponents()

template<typename T >

long ogdf::MinSteinerTreeRZLoss< T >::Main::numberOfContractedComponents ( )

inline

Returns the number of contracted components.

Definition at line 262 of file MinSteinerTreeRZLoss.h.

◆ numberOfGeneratedComponents()

template<typename T >

long ogdf::MinSteinerTreeRZLoss< T >::Main::numberOfGeneratedComponents ( )

inline

Returns the number of generated components.

Definition at line 259 of file MinSteinerTreeRZLoss.h.

◆ retrieveComponents()

template<typename T >

template<typename FCG >

void ogdf::MinSteinerTreeRZLoss< T >::Main::retrieveComponents	(	const FCG &	fcg,
		const EdgeWeightedGraphCopy< T > &	tree
	)

private

Auxiliary function to retrieve components by Dreyfus-Wagner/Erickson et al implementation.

Definition at line 348 of file MinSteinerTreeRZLoss.h.

◆ setup()

template<typename T >

void ogdf::MinSteinerTreeRZLoss< T >::Main::setup ( EdgeWeightedGraphCopy< T > & tree )

inlineprivate

Setup (build initial terminal-spanning tree, its save data structure, and find all components)

Definition at line 176 of file MinSteinerTreeRZLoss.h.

Member Data Documentation

◆ m_componentsContracted

template<typename T >

long ogdf::MinSteinerTreeRZLoss< T >::Main::m_componentsContracted

private

Number of contracted components.

Definition at line 245 of file MinSteinerTreeRZLoss.h.

◆ m_componentsGenerated

template<typename T >

long ogdf::MinSteinerTreeRZLoss< T >::Main::m_componentsGenerated

private

Number of generated components.

Definition at line 244 of file MinSteinerTreeRZLoss.h.

◆ m_componentsLookUps

template<typename T >

long ogdf::MinSteinerTreeRZLoss< T >::Main::m_componentsLookUps

private

Number of components lookups.

Definition at line 246 of file MinSteinerTreeRZLoss.h.

◆ m_fullCompStore

template<typename T >

steiner_tree::FullComponentWithLossStore<T> ogdf::MinSteinerTreeRZLoss< T >::Main::m_fullCompStore

private

All generated full components.

Definition at line 241 of file MinSteinerTreeRZLoss.h.

◆ m_G

template<typename T >

const EdgeWeightedGraph<T>& ogdf::MinSteinerTreeRZLoss< T >::Main::m_G

private

The original edge-weighted graph.

Definition at line 236 of file MinSteinerTreeRZLoss.h.

◆ m_isNewTerminal

template<typename T >

NodeArray<bool> ogdf::MinSteinerTreeRZLoss< T >::Main::m_isNewTerminal

private

Incidence vector for nonterminal nodes marked as terminals for improvement.

Definition at line 242 of file MinSteinerTreeRZLoss.h.

◆ m_isTerminal

template<typename T >

const NodeArray<bool>& ogdf::MinSteinerTreeRZLoss< T >::Main::m_isTerminal

private

Incidence vector for terminal nodes.

Definition at line 237 of file MinSteinerTreeRZLoss.h.

◆ m_restricted

template<typename T >

int ogdf::MinSteinerTreeRZLoss< T >::Main::m_restricted

private

Parameter for the number of terminals in a full component.

Definition at line 239 of file MinSteinerTreeRZLoss.h.

◆ m_save

template<typename T >

std::unique_ptr<steiner_tree::SaveStatic<T> > ogdf::MinSteinerTreeRZLoss< T >::Main::m_save

private

The save data structure.

Definition at line 240 of file MinSteinerTreeRZLoss.h.

◆ m_terminals

template<typename T >

List<node> ogdf::MinSteinerTreeRZLoss< T >::Main::m_terminals

private

List of terminal nodes (will be copied and sorted)

Definition at line 238 of file MinSteinerTreeRZLoss.h.

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

include/ogdf/graphalg/MinSteinerTreeRZLoss.h

terminals	The terminals of the full component
steinerTree	Current Steiner tree

OpenGraph DrawingFramework

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ SaveStatic

Constructor & Destructor Documentation

◆ Main()

Member Function Documentation

◆ contractLoss()

◆ extractMaxComponent()

◆ findFull3Components()

◆ findFullComponentsDW()

◆ findFullComponentsEMV()

◆ gain()

◆ generateInitialTerminalSpanningTree()

◆ getApproximation()

◆ multiPass()

◆ numberOfComponentLookUps()

◆ numberOfContractedComponents()

◆ numberOfGeneratedComponents()

◆ retrieveComponents()

◆ setup()

Member Data Documentation

◆ m_componentsContracted

◆ m_componentsGenerated

◆ m_componentsLookUps

◆ m_fullCompStore

◆ m_G

◆ m_isNewTerminal

◆ m_isTerminal

◆ m_restricted

◆ m_save

◆ m_terminals

Open
Graph Drawing
Framework