Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
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.
 
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< nodem_nodeCopy
 Mapping of original terminals to m_graph nodes.
 
NodeArray< nodem_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()

Definition at line 271 of file FullComponentStore.h.

◆ insert()

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
inlineprotected

Traverse over degree-2 nonterminals.

Definition at line 75 of file FullComponentStore.h.

Member Data Documentation

◆ m_components

List of full components (based on metadata)

Definition at line 72 of file FullComponentStore.h.

◆ m_graph

Our graph representation for the full component store.

Definition at line 49 of file FullComponentStore.h.

◆ m_isTerminal

Incidence vector for terminal nodes.

Definition at line 48 of file FullComponentStore.h.

◆ m_nodeCopy

Mapping of original terminals to m_graph nodes.

Definition at line 50 of file FullComponentStore.h.

◆ m_nodeOrig

Mapping of m_graph nodes to original nodes.

Definition at line 51 of file FullComponentStore.h.

◆ m_originalGraph

The original Steiner instance.

Definition at line 46 of file FullComponentStore.h.

◆ m_terminals

The terminal list of the original Steiner instance.

Definition at line 47 of file FullComponentStore.h.


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