Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::steiner_tree::FullComponentStore< T, ExtraDataType > Class Template Reference

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)
 
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< nodem_nodeCopy
 Mapping of original terminals to m_graph nodes. More...
 
NodeArray< nodem_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 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 143 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 126 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 96 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 278 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 304 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 338 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 350 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 328 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 292 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 158 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 265 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 272 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 297 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 216 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 245 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 285 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 257 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 83 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 80 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 50 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 49 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 52 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 53 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 47 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 48 of file FullComponentStore.h.


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