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

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

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

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

bool	isTerminal (node v) const

node	original (node v) const

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

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

adjEntry	start (int i) const

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

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

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

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

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

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

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

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

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

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

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

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 55 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 147 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 131 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 100 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 270 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 290 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 320 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 331 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 313 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 282 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 162 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 251 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 261 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 267 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 284 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 220 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 248 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 276 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 254 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

inlineprotected

Traverse over degree-2 nonterminals.

Definition at line 86 of file FullComponentStore.h.

Member Data Documentation

◆ m_components

template<typename T , typename ExtraDataType = void>

ArrayBuffer<Metadata<ExtraDataType> > ogdf::steiner_tree::FullComponentStore< T, ExtraDataType >::m_components

protected

List of full components (based on metadata)

Definition at line 83 of file FullComponentStore.h.

◆ m_graph

template<typename T , typename ExtraDataType = void>

EdgeWeightedGraph<T> ogdf::steiner_tree::FullComponentStore< T, ExtraDataType >::m_graph

protected

Our graph representation for the full component store.

Definition at line 60 of file FullComponentStore.h.

◆ m_isTerminal

template<typename T , typename ExtraDataType = void>

const NodeArray<bool>& ogdf::steiner_tree::FullComponentStore< T, ExtraDataType >::m_isTerminal

protected

Incidence vector for terminal nodes.

Definition at line 59 of file FullComponentStore.h.

◆ m_nodeCopy

template<typename T , typename ExtraDataType = void>

NodeArray<node> ogdf::steiner_tree::FullComponentStore< T, ExtraDataType >::m_nodeCopy

protected

Mapping of original terminals to m_graph nodes.

Definition at line 61 of file FullComponentStore.h.

◆ m_nodeOrig

template<typename T , typename ExtraDataType = void>

NodeArray<node> ogdf::steiner_tree::FullComponentStore< T, ExtraDataType >::m_nodeOrig

protected

Mapping of m_graph nodes to original nodes.

Definition at line 62 of file FullComponentStore.h.

◆ m_originalGraph

template<typename T , typename ExtraDataType = void>

const EdgeWeightedGraph<T>& ogdf::steiner_tree::FullComponentStore< T, ExtraDataType >::m_originalGraph

protected

The original Steiner instance.

Definition at line 57 of file FullComponentStore.h.

◆ m_terminals

template<typename T , typename ExtraDataType = void>

const List<node>& ogdf::steiner_tree::FullComponentStore< T, ExtraDataType >::m_terminals

protected

The terminal list of the original Steiner instance.

Definition at line 58 of file FullComponentStore.h.

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

include/ogdf/graphalg/steiner_tree/FullComponentStore.h

OpenGraph DrawingFramework

Classes

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

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

Constructor & Destructor Documentation

◆ FullComponentStore()

Member Function Documentation

◆ copyEdges()

◆ copyEdgesWithSimplifiedPaths()

◆ cost()

◆ foreachAdjEntry()

◆ foreachEdge()

◆ foreachNode() [1/2]

◆ foreachNode() [2/2]

◆ graph()

◆ insert()

◆ isEmpty()

◆ isTerminal() [1/2]

◆ isTerminal() [2/2]

◆ original()

◆ remove()

◆ size()

◆ start()

◆ terminals()

◆ traverseOverDegree2Nonterminals()

Member Data Documentation

◆ m_components

◆ m_graph

◆ m_isTerminal

◆ m_nodeCopy

◆ m_nodeOrig

◆ m_originalGraph

◆ m_terminals

Open
Graph Drawing
Framework

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