A data structure to store full components. More...

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

Inheritance diagram for ogdf::steiner_tree::FullComponentStore< T, ExtraDataType >:

Classes
struct	Metadata

struct	Metadata< Y, typename std::enable_if<!std::is_void< Y >::value >::type >

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

T	cost (int i) const
	Returns the sum of edge costs of this full component.

template<typename Fun >
void	foreachAdjEntry (int i, Fun f) const

template<typename Fun >
void	foreachEdge (int id, const NodeArray< NodeArray< edge > > &pred, Fun f) const

template<typename Fun >
void	foreachNode (int id, const NodeArray< NodeArray< edge > > &pred, Fun f) const

template<typename Fun >
void	foreachNode (int id, Fun f) const

const EdgeWeightedGraph< T > &	graph () const

void	insert (const EdgeWeightedGraphCopy< T > &comp)
	Inserts a component. Note that `comp` is copied and degree-2 nodes are removed.

bool	isEmpty () const
	Checks if the store does not contain any full components.

bool	isTerminal (int id, node t) const
	checks if a given node t is a terminal in the full component with given id

bool	isTerminal (node v) const

node	original (node v) const

void	remove (int id)
	Removes a component by its `id`.

int	size () const
	Returns the number of full components in the store.

adjEntry	start (int i) const

const Array< node > &	terminals (int id) const
	Returns the list of terminals in the full component with given id.

Protected Member Functions
void	copyEdges (Metadata< ExtraDataType > &data, const EdgeWeightedGraphCopy< T > &comp)
	Copy edges from `comp` into our representation.

void	copyEdgesWithSimplifiedPaths (Metadata< ExtraDataType > &data, const EdgeWeightedGraphCopy< T > &comp, const ArrayBuffer< node > &nonterminals)
	Copy edges from `comp` into our representation, traversing variant to ignore degree-2 nodes.

void	traverseOverDegree2Nonterminals (node &uO, T &weight, EdgeArray< bool > &marked, adjEntry adj, const EdgeWeightedGraphCopy< T > &comp) const
	Traverse over degree-2 nonterminals.

Protected Attributes
ArrayBuffer< Metadata< ExtraDataType > >	m_components
	List of full components (based on metadata)

EdgeWeightedGraph< T >	m_graph
	Our graph representation for the full component store.

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

NodeArray< node >	m_nodeCopy
	Mapping of original terminals to m_graph nodes.

NodeArray< node >	m_nodeOrig
	Mapping of m_graph nodes to original nodes.

const EdgeWeightedGraph< T > &	m_originalGraph
	The original Steiner instance.

const List< node > &	m_terminals
	The terminal list of the original Steiner instance.

Detailed Description

template<typename T, typename ExtraDataType = void>
class ogdf::steiner_tree::FullComponentStore< T, ExtraDataType >

A data structure to store full components.

Definition at line 44 of file FullComponentStore.h.

Constructor & Destructor Documentation

◆ FullComponentStore()

template<typename T , typename ExtraDataType = void>

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

inline

Definition at line 136 of file FullComponentStore.h.

Member Function Documentation

◆ copyEdges()

template<typename T , typename ExtraDataType = void>

void ogdf::steiner_tree::FullComponentStore< T, ExtraDataType >::copyEdges	(	Metadata< ExtraDataType > &	data,
		const EdgeWeightedGraphCopy< T > &	comp
	)

inlineprotected

Copy edges from comp into our representation.

Definition at line 120 of file FullComponentStore.h.

◆ copyEdgesWithSimplifiedPaths()

template<typename T , typename ExtraDataType = void>

void ogdf::steiner_tree::FullComponentStore< T, ExtraDataType >::copyEdgesWithSimplifiedPaths	(	Metadata< ExtraDataType > &	data,
		const EdgeWeightedGraphCopy< T > &	comp,
		const ArrayBuffer< node > &	nonterminals
	)

inlineprotected

Copy edges from comp into our representation, traversing variant to ignore degree-2 nodes.

Definition at line 89 of file FullComponentStore.h.

◆ cost()

template<typename T , typename ExtraDataType = void>

T ogdf::steiner_tree::FullComponentStore< T, ExtraDataType >::cost ( int i ) const

inline

Returns the sum of edge costs of this full component.

Definition at line 259 of file FullComponentStore.h.

◆ foreachAdjEntry()

template<typename T , typename ExtraDataType = void>

template<typename Fun >

void ogdf::steiner_tree::FullComponentStore< T, ExtraDataType >::foreachAdjEntry	(	int	i,
		Fun	f
	)		const

inline

Definition at line 279 of file FullComponentStore.h.

◆ foreachEdge()

template<typename T , typename ExtraDataType = void>

template<typename Fun >

void ogdf::steiner_tree::FullComponentStore< T, ExtraDataType >::foreachEdge	(	int	id,
		const NodeArray< NodeArray< edge > > &	pred,
		Fun	f
	)		const

inline

Definition at line 309 of file FullComponentStore.h.

◆ foreachNode() [1/2]

template<typename T , typename ExtraDataType = void>

template<typename Fun >

void ogdf::steiner_tree::FullComponentStore< T, ExtraDataType >::foreachNode	(	int	id,
		const NodeArray< NodeArray< edge > > &	pred,
		Fun	f
	)		const

inline

Definition at line 320 of file FullComponentStore.h.

◆ foreachNode() [2/2]

template<typename T , typename ExtraDataType = void>

template<typename Fun >

void ogdf::steiner_tree::FullComponentStore< T, ExtraDataType >::foreachNode	(	int	id,
		Fun	f
	)		const

inline

Definition at line 302 of file FullComponentStore.h.

◆ graph()

template<typename T , typename ExtraDataType = void>

const EdgeWeightedGraph< T > & ogdf::steiner_tree::FullComponentStore< T, ExtraDataType >::graph ( ) const

inline

Definition at line 271 of file FullComponentStore.h.

◆ insert()

template<typename T , typename ExtraDataType = void>

void ogdf::steiner_tree::FullComponentStore< T, ExtraDataType >::insert ( const EdgeWeightedGraphCopy< T > & comp )

inline

Inserts a component. Note that comp is copied and degree-2 nodes are removed.

Definition at line 151 of file FullComponentStore.h.

◆ isEmpty()

template<typename T , typename ExtraDataType = void>

bool ogdf::steiner_tree::FullComponentStore< T, ExtraDataType >::isEmpty ( ) const

inline

Checks if the store does not contain any full components.

Definition at line 240 of file FullComponentStore.h.

◆ isTerminal() [1/2]

template<typename T , typename ExtraDataType = void>

bool ogdf::steiner_tree::FullComponentStore< T, ExtraDataType >::isTerminal	(	int	id,
		node	t
	)		const

inline

checks if a given node t is a terminal in the full component with given id

Definition at line 250 of file FullComponentStore.h.

◆ isTerminal() [2/2]

template<typename T , typename ExtraDataType = void>

bool ogdf::steiner_tree::FullComponentStore< T, ExtraDataType >::isTerminal ( node v ) const

inline

Definition at line 256 of file FullComponentStore.h.

◆ original()

template<typename T , typename ExtraDataType = void>

node ogdf::steiner_tree::FullComponentStore< T, ExtraDataType >::original ( node v ) const

inline

Definition at line 273 of file FullComponentStore.h.

◆ remove()

template<typename T , typename ExtraDataType = void>

void ogdf::steiner_tree::FullComponentStore< T, ExtraDataType >::remove ( int id )

inline

Removes a component by its id.

Definition at line 209 of file FullComponentStore.h.

◆ size()

template<typename T , typename ExtraDataType = void>

int ogdf::steiner_tree::FullComponentStore< T, ExtraDataType >::size ( ) const

inline

Returns the number of full components in the store.

Definition at line 237 of file FullComponentStore.h.

◆ start()

template<typename T , typename ExtraDataType = void>

adjEntry ogdf::steiner_tree::FullComponentStore< T, ExtraDataType >::start ( int i ) const

inline

Definition at line 265 of file FullComponentStore.h.

◆ terminals()

template<typename T , typename ExtraDataType = void>

const Array< node > & ogdf::steiner_tree::FullComponentStore< T, ExtraDataType >::terminals ( int id ) const

inline

Returns the list of terminals in the full component with given id.

Definition at line 243 of file FullComponentStore.h.

◆ traverseOverDegree2Nonterminals()

template<typename T , typename ExtraDataType = void>

void ogdf::steiner_tree::FullComponentStore< T, ExtraDataType >::traverseOverDegree2Nonterminals	(	node &	uO,
		T &	weight,
		EdgeArray< bool > &	marked,
		adjEntry	adj,
		const EdgeWeightedGraphCopy< T > &	comp
	)		const