Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::steiner_tree::FullComponentWithLossStore< T > Class Template Reference

A data structure to store full components with additional "loss" functionality. More...

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

+ Inheritance diagram for ogdf::steiner_tree::FullComponentWithLossStore< T >:

Public Member Functions

void computeAllLosses ()
 Compute the loss, both edge set and value, of all full components. More...
 
loss (int id) const
 Returns the loss value of full component with given id. More...
 
const List< edge > & lossBridges (int id) const
 Returns a list of non-loss edges (that are bridges between the Loss components) of full component with given id. More...
 
node lossTerminal (node v) const
 Returns the terminal (in the original graph) that belongs to a given node v (in the store) according to the Loss of the component. More...
 
- Public Member Functions inherited from ogdf::steiner_tree::FullComponentWithExtraStore< T, LossMetadata< T > >
LossMetadata< T > & extra (int i)
 Returns a reference to the extra data of this full component. More...
 
const LossMetadata< T > & extra (int i) const
 Returns a const reference to the extra data of this full component. More...
 
- Public Member Functions inherited from ogdf::steiner_tree::FullComponentStore< T, LossMetadata< T > >
 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...
 
void foreachAdjEntry (int i, Fun f) const
 
void foreachEdge (int id, const NodeArray< NodeArray< edge >> &pred, Fun f) const
 
void foreachNode (int id, const NodeArray< NodeArray< edge >> &pred, Fun f) const
 
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

node findLossTerminal (const node u, const NodeArray< edge > &pred)
 Starting from a Steiner node find the nearest terminal along a shortest path. More...
 
- Protected Member Functions inherited from ogdf::steiner_tree::FullComponentStore< T, LossMetadata< T > >
void copyEdges (Metadata< LossMetadata< T > > &data, const EdgeWeightedGraphCopy< T > &comp)
 Copy edges from comp into our representation. More...
 
void copyEdgesWithSimplifiedPaths (Metadata< LossMetadata< T > > &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

NodeArray< nodem_lossTerminal
 Indicates which Steiner node is connected to which terminal through the loss edges, indexed by the Steiner node. More...
 
- Protected Attributes inherited from ogdf::steiner_tree::FullComponentStore< T, LossMetadata< T > >
ArrayBuffer< Metadata< LossMetadata< T > > > 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>
class ogdf::steiner_tree::FullComponentWithLossStore< T >

A data structure to store full components with additional "loss" functionality.

Definition at line 418 of file FullComponentStore.h.

Member Function Documentation

◆ computeAllLosses()

template<typename T >
void ogdf::steiner_tree::FullComponentWithLossStore< T >::computeAllLosses ( )
inline

Compute the loss, both edge set and value, of all full components.

Definition at line 443 of file FullComponentStore.h.

◆ findLossTerminal()

template<typename T >
node ogdf::steiner_tree::FullComponentWithLossStore< T >::findLossTerminal ( const node  u,
const NodeArray< edge > &  pred 
)
inlineprotected

Starting from a Steiner node find the nearest terminal along a shortest path.

Parameters
uSteiner node to start from
predThe shortest path predecessor data structure
Returns
first terminal on a shortest path starting from a Steiner node

Definition at line 429 of file FullComponentStore.h.

◆ loss()

template<typename T >
T ogdf::steiner_tree::FullComponentWithLossStore< T >::loss ( int  id) const
inline

Returns the loss value of full component with given id.

Definition at line 486 of file FullComponentStore.h.

◆ lossBridges()

template<typename T >
const List<edge>& ogdf::steiner_tree::FullComponentWithLossStore< T >::lossBridges ( int  id) const
inline

Returns a list of non-loss edges (that are bridges between the Loss components) of full component with given id.

Definition at line 492 of file FullComponentStore.h.

◆ lossTerminal()

template<typename T >
node ogdf::steiner_tree::FullComponentWithLossStore< T >::lossTerminal ( node  v) const
inline

Returns the terminal (in the original graph) that belongs to a given node v (in the store) according to the Loss of the component.

A terminal and a Steiner node are linked if the terminal is the first one on the shortest loss path starting from the Steiner node.

Definition at line 503 of file FullComponentStore.h.

Member Data Documentation

◆ m_lossTerminal

template<typename T >
NodeArray<node> ogdf::steiner_tree::FullComponentWithLossStore< T >::m_lossTerminal
protected

Indicates which Steiner node is connected to which terminal through the loss edges, indexed by the Steiner node.

Definition at line 421 of file FullComponentStore.h.


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