Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

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

A generator for restricted full components (for Steiner tree approximations) based on the Dreyfus-Wagner algorithm that does not need a precomputed all-pair-shortest-paths matrix because single-source-shortest-path are used within. More...

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

Classes

class  AuxiliaryGraph
 Necessary because ogdf::EdgeWeightedGraphCopy<T> is rubbish. More...
 
struct  DWMData
 Subgraphs (given by other subgraphs and additional edges) and their cost for a partial solution. More...
 
struct  DWMSplit
 A collection of two subgraphs and their total cost. More...
 
class  SortedNodeListHashFunc
 

Public Member Functions

 FullComponentGeneratorDreyfusWagnerWithoutMatrix (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal)
 The constructor. More...
 
void call (int restricted)
 
getSteinerTreeFor (const List< node > &terminals, EdgeWeightedGraphCopy< T > &tree) const
 Constructs a Steiner tree for the given set of terminals if it is valid, otherwise an empty tree is returned. More...
 
bool isValidComponent (const EdgeWeightedGraphCopy< T > &tree) const
 Checks if a given tree is a valid full component. More...
 

Private Member Functions

edge addNewPath (DWMData &result, node curr, const NodeArray< edge > &pred) const
 Adds the shortest path from the source to curr into result. More...
 
template<typename CONTAINER >
void computePartialSolutions (const CONTAINER &targets)
 Computes all partial solutions for given m_terminalSubset. More...
 
void computeSplit (NodeArray< DWMSplit > &split, node v, SubsetEnumerator< node > &subset) const
 Populates split that contains a partial solution for an included nonterminal v in m_G. More...
 
costOf (const List< node > &key) const
 Returns the cost of the partial solution given by key. More...
 
const DWMDatadataOf (const List< node > &key) const
 Returns a pointer to the relevant data of the partial solution given by key. More...
 
getSteinerTreeFor (const DWMData &data, EdgeWeightedGraphCopy< T > &tree) const
 Adds edges to construct a Steiner tree from the given data (recursively) if the data is valid. More...
 
void initializeMap ()
 Initializes the hash array with all node-terminal-pairs. More...
 
template<typename CONTAINER >
void insertBestSubtrees (const CONTAINER &targets, const NodeArray< DWMSplit > &split, const NodeArray< edge > &pred, const NodeArray< T > &distance, const List< node > &terminals)
 Inserts the best subtrees into the hash map. More...
 
void insertInvalidBestSubtree (node v, const NodeArray< T > &distance, const List< node > &newSubset)
 Inserts the invalid best subtree (based on the SSSP computation) into the hash map. More...
 
void insertValidBestSubtree (node v, const NodeArray< DWMSplit > &split, const NodeArray< edge > &pred, const List< node > &newSubset, const List< node > &terminals)
 Inserts the valid best subtree (based on the SSSP computation) into the hash map. More...
 
void makeKey (List< node > &newSubset, List< node > &newComplement, const SubsetEnumerator< node > &subset, node v) const
 Makes a list from subset and its complement, each including an correctly inserted node v. More...
 
void makeKey (List< node > &newSubset, node v) const
 Makes a list from the current terminal subset including an correctly inserted node v. More...
 
bool safeIfSumSmaller (const T summand1, const T summand2, const T compareValue) const
 Checks overflow-safe if summand1 plus summand2 is less than compareValue. More...
 
void updateAuxGraph (NodeArray< DWMSplit > &split, SubsetEnumerator< node > &subset, T oldCost)
 Updates the auxiliary graph. More...
 

Static Private Member Functions

static void sortedInserter (node w, List< node > &list, bool &inserted, node newNode)
 Is being used as a callback to ogdf::SubsetEnumerator's forEach* methods to get the subset plus a correctly inserted newNode (ie, sorted by index) into list. More...
 

Private Attributes

AuxiliaryGraph m_auxG
 An auxiliary graph to compute partial solutions. More...
 
const EdgeWeightedGraph< T > & m_G
 A reference to the graph instance. More...
 
const NodeArray< bool > & m_isTerminal
 A reference to the terminal incidence vector. More...
 
Hashing< List< node >, DWMData, SortedNodeListHashFuncm_map
 A hash array for keys of size > 2. More...
 
const List< node > & m_terminals
 A reference to the index-sorted list of terminals. More...
 
SubsetEnumerator< nodem_terminalSubset
 Handling subsets of terminals. More...
 

Detailed Description

template<typename T>
class ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >

A generator for restricted full components (for Steiner tree approximations) based on the Dreyfus-Wagner algorithm that does not need a precomputed all-pair-shortest-paths matrix because single-source-shortest-path are used within.

See also R. E. Erickson, C. L. Monma, A. F. Veinott: Send-and-split method for minimum-concave-cost network flows. Math. Oper. Res. 12 (1987) 634-664.

Definition at line 55 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

Constructor & Destructor Documentation

◆ FullComponentGeneratorDreyfusWagnerWithoutMatrix()

template<typename T >
ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >::FullComponentGeneratorDreyfusWagnerWithoutMatrix ( const EdgeWeightedGraph< T > &  G,
const List< node > &  terminals,
const NodeArray< bool > &  isTerminal 
)
inline

The constructor.

Precondition
The list of terminals has to be sorted by index (use MinSteinerTreeModule<T>::sortTerminals)

Definition at line 480 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

Member Function Documentation

◆ addNewPath()

template<typename T >
edge ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >::addNewPath ( DWMData result,
node  curr,
const NodeArray< edge > &  pred 
) const
inlineprivate

Adds the shortest path from the source to curr into result.

Returns
the edge of that path that is incident to the source

Definition at line 371 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ call()

template<typename T >
void ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >::call ( int  restricted)
inline

◆ computePartialSolutions()

template<typename T >
template<typename CONTAINER >
void ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >::computePartialSolutions ( const CONTAINER &  targets)
inlineprivate

Computes all partial solutions for given m_terminalSubset.

Definition at line 306 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ computeSplit()

template<typename T >
void ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >::computeSplit ( NodeArray< DWMSplit > &  split,
node  v,
SubsetEnumerator< node > &  subset 
) const
inlineprivate

Populates split that contains a partial solution for an included nonterminal v in m_G.

Note that it is not guaranteed that any resulting collection of edges represents a tree.

Definition at line 288 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ costOf()

template<typename T >
T ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >::costOf ( const List< node > &  key) const
inlineprivate

Returns the cost of the partial solution given by key.

Definition at line 223 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ dataOf()

template<typename T >
const DWMData* ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >::dataOf ( const List< node > &  key) const
inlineprivate

Returns a pointer to the relevant data of the partial solution given by key.

Definition at line 216 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ getSteinerTreeFor() [1/2]

template<typename T >
T ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >::getSteinerTreeFor ( const DWMData data,
EdgeWeightedGraphCopy< T > &  tree 
) const
inlineprivate

Adds edges to construct a Steiner tree from the given data (recursively) if the data is valid.

Definition at line 441 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ getSteinerTreeFor() [2/2]

template<typename T >
T ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >::getSteinerTreeFor ( const List< node > &  terminals,
EdgeWeightedGraphCopy< T > &  tree 
) const
inline

Constructs a Steiner tree for the given set of terminals if it is valid, otherwise an empty tree is returned.

Definition at line 504 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ initializeMap()

template<typename T >
void ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >::initializeMap ( )
inlineprivate

Initializes the hash array with all node-terminal-pairs.

Definition at line 327 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ insertBestSubtrees()

template<typename T >
template<typename CONTAINER >
void ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >::insertBestSubtrees ( const CONTAINER &  targets,
const NodeArray< DWMSplit > &  split,
const NodeArray< edge > &  pred,
const NodeArray< T > &  distance,
const List< node > &  terminals 
)
inlineprivate

Inserts the best subtrees into the hash map.

Definition at line 422 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ insertInvalidBestSubtree()

template<typename T >
void ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >::insertInvalidBestSubtree ( node  v,
const NodeArray< T > &  distance,
const List< node > &  newSubset 
)
inlineprivate

Inserts the invalid best subtree (based on the SSSP computation) into the hash map.

Definition at line 393 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ insertValidBestSubtree()

template<typename T >
void ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >::insertValidBestSubtree ( node  v,
const NodeArray< DWMSplit > &  split,
const NodeArray< edge > &  pred,
const List< node > &  newSubset,
const List< node > &  terminals 
)
inlineprivate

Inserts the valid best subtree (based on the SSSP computation) into the hash map.

Definition at line 402 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ isValidComponent()

template<typename T >
bool ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >::isValidComponent ( const EdgeWeightedGraphCopy< T > &  tree) const
inline

Checks if a given tree is a valid full component.

Definition at line 512 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ makeKey() [1/2]

template<typename T >
void ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >::makeKey ( List< node > &  newSubset,
List< node > &  newComplement,
const SubsetEnumerator< node > &  subset,
node  v 
) const
inlineprivate

Makes a list from subset and its complement, each including an correctly inserted node v.

Definition at line 268 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ makeKey() [2/2]

template<typename T >
void ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >::makeKey ( List< node > &  newSubset,
node  v 
) const
inlineprivate

Makes a list from the current terminal subset including an correctly inserted node v.

Definition at line 259 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ safeIfSumSmaller()

template<typename T >
bool ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >::safeIfSumSmaller ( const T  summand1,
const T  summand2,
const T  compareValue 
) const
inlineprivate

Checks overflow-safe if summand1 plus summand2 is less than compareValue.

Definition at line 229 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ sortedInserter()

template<typename T >
static void ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >::sortedInserter ( node  w,
List< node > &  list,
bool &  inserted,
node  newNode 
)
inlinestaticprivate

Is being used as a callback to ogdf::SubsetEnumerator's forEach* methods to get the subset plus a correctly inserted newNode (ie, sorted by index) into list.

This takes linear time in comparison to copy, insert, sort which takes average case O(n log n) time.

Parameters
wNode argument for the callback
listResulting list
insertedWhether newNode was inserted; must be initialized to false
newNodeNew node to be inserted into the list

Definition at line 250 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ updateAuxGraph()

template<typename T >
void ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >::updateAuxGraph ( NodeArray< DWMSplit > &  split,
SubsetEnumerator< node > &  subset,
oldCost 
)
inlineprivate

Updates the auxiliary graph.

Definition at line 357 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

Member Data Documentation

◆ m_auxG

An auxiliary graph to compute partial solutions.

Definition at line 146 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ m_G

A reference to the graph instance.

Definition at line 56 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ m_isTerminal

template<typename T >
const NodeArray<bool>& ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >::m_isTerminal
private

A reference to the terminal incidence vector.

Definition at line 58 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ m_map

A hash array for keys of size > 2.

Definition at line 210 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ m_terminals

template<typename T >
const List<node>& ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix< T >::m_terminals
private

A reference to the index-sorted list of terminals.

Definition at line 57 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.

◆ m_terminalSubset

Handling subsets of terminals.

Definition at line 147 of file FullComponentGeneratorDreyfusWagnerWithoutMatrix.h.


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