Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::MinSteinerTreeDirectedCut< T > Class Template Reference

This class implements the Directed Cut Integer Linear Program for the Steiner tree problem. More...

#include <ogdf/graphalg/MinSteinerTreeDirectedCut.h>

+ Inheritance diagram for ogdf::MinSteinerTreeDirectedCut< T >:

Classes

class  DegreeConstraint
 Constraint for nodes, e.g., in/outdegree stuff. More...
 
class  DegreeEdgeConstraint
 Constraint for relating the indegree and one outgoing edge of a node. More...
 
class  DirectedCutConstraint
 Class for directed cuts (i.e., separated Steiner cuts) More...
 
class  EdgeConstraint
 Constraint for edges, e.g., subtour elimination constraints of size 2 ((G)SEC2) More...
 
class  EdgeVariable
 Variable for directed edges. More...
 
class  Master
 Master problem of Steiner tree branch&cut algorithm More...
 
class  Sub
 Subproblem of Steiner tree algorithm. More...
 

Public Member Functions

 MinSteinerTreeDirectedCut ()
 
void setConfigFile (const char *configfile)
 Set a configuration file to use. The contents of the configuration file can override all other used options. More...
 
void setEpsilon (double eps)
 Set the epsilon for the LP. More...
 
void setMaxFlowModule (MaxFlowModule< double > *module)
 Set the maximum flow module to be used for separation. More...
 
void setMaxNumberAddedCuttingPlanes (int b)
 Set maximum number of added cutting planes per iteration. More...
 
void setPoolSizeInitFactor (int b)
 Set factor for the initial size of the cutting pool. More...
 
void setPrimalHeuristic (MinSteinerTreeModule< double > *b)
 Set the module option for the primal heuristic (use MinSteinerTreeModule<double> types). Default: MinSteinerTreeModuleTakahashi. More...
 
void setPrimalHeuristicCallStrategy (int b)
 Set primal heuristic call strategy. More...
 
void setSaturationStrategy (int b)
 Set saturation strategy for nested cuts. More...
 
void setSeparationStrategy (int b)
 Set separation strategy for nested cuts. More...
 
void useBackCuts (bool b)
 Switch computation of back-cuts on or off. More...
 
void useDegreeConstraints (bool b)
 Switch usage of degree constraints (like indeg <= 1) on or off. More...
 
void useFlowBalanceConstraints (bool b)
 Switch usage of flow balance constraints on or off. More...
 
void useGSEC2Constraints (bool b)
 Switch usage of constraints x_uv + x_vu <= 1 on or off. More...
 
void useIndegreeEdgeConstraints (bool b)
 Switch usage of indegree edge constraints (indeg(v) >= outgoing edge(v,x) for all x) on or off. More...
 
void useMinCardinalityCuts (bool b)
 Switch usage of the cardinality heuristic (minimum-cardinality cuts) on or off. More...
 
void useNestedCuts (bool b)
 Switch computation of nested cuts on or off. More...
 
void useTerminalShuffle (bool b)
 Switch terminal shuffling before separation on or off. More...
 
- Public Member Functions inherited from ogdf::MinSteinerTreeModule< T >
virtual ~MinSteinerTreeModule ()
 Do nothing on destruction. More...
 
virtual T call (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree)
 Calls the Steiner tree algorithm for nontrivial cases but handles trivial cases directly. More...
 

Protected Member Functions

virtual T computeSteinerTree (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree) override
 Computes the actual Steiner tree. More...
 

Protected Attributes

bool m_addDegreeConstraints
 
bool m_addFlowBalanceConstraints
 
bool m_addGSEC2Constraints
 
bool m_addIndegreeEdgeConstraints
 
bool m_backCutComputation
 
int m_callPrimalHeuristic
 
const char * m_configFile
 
double m_eps
 
std::unique_ptr< MaxFlowModule< double > > m_maxFlowModuleOption
 
int m_maxNrAddedCuttingPlanes
 
bool m_minCardinalityCuts
 
bool m_nestedCutComputation
 
int m_poolSizeInitFactor
 
MinSteinerTreeModule< double > * m_primalHeuristic
 
int m_saturationStrategy
 
int m_separationStrategy
 
bool m_shuffleTerminals
 

Additional Inherited Members

- Static Public Member Functions inherited from ogdf::MinSteinerTreeModule< T >
static void getNonterminals (ArrayBuffer< node > &nonterminals, const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal)
 Generates a list (as ArrayBuffer<node>) of all nonterminals. More...
 
static void getTerminals (List< node > &terminals, const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal)
 Generates a list (as List<node>) of all terminals. More...
 
static bool isQuasiBipartite (const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal)
 Checks in O(n + m) time if a given Steiner tree problem instance is quasi-bipartite. More...
 
static bool isSteinerTree (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, const EdgeWeightedGraphCopy< T > &steinerTree)
 Checks in O(n) time if a given tree is acually a Steiner Tree. More...
 
static void sortTerminals (List< node > &terminals)
 Sort terminals by index. More...
 
static T pruneAllDanglingSteinerPaths (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal)
 Prunes nonterminal leaves and their paths to terminal or branching nodes. More...
 
static T pruneDanglingSteinerPathFrom (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, node start)
 Prunes the dangling Steiner path beginning at a given nonterminal leaf only. More...
 
static T pruneDanglingSteinerPathsFrom (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, const List< node > &start)
 Prunes dangling Steiner paths beginning at given nonterminal leaves only. More...
 
static T removeCyclesFrom (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal)
 Remove remaining cycles from a Steiner "almost" tree. More...
 
static void singleSourceShortestPathsPreferringTerminals (const EdgeWeightedGraph< T > &G, node source, const NodeArray< bool > &isTerminal, NodeArray< T > &distance, NodeArray< edge > &pred)
 Modified single-source-shortest-paths (Dijkstra) with heuristic to prefer paths over terminals. More...
 
static void singleSourceShortestPathsStandard (const EdgeWeightedGraph< T > &G, node source, const NodeArray< bool > &, NodeArray< T > &distance, NodeArray< edge > &pred)
 Standard single-source-shortest-paths algoritm (Dijkstra) More...
 
static void singleSourceShortestPaths (const EdgeWeightedGraph< T > &G, node source, const NodeArray< bool > &isTerminal, NodeArray< T > &distance, NodeArray< edge > &pred)
 The default single-source-shortest-paths algorithm. More...
 
static void allTerminalShortestPathsStandard (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T >> &distance, NodeArray< NodeArray< edge >> &pred)
 Runs singleSourceShortestPathsStandard from all terminals. More...
 
static void allTerminalShortestPathsPreferringTerminals (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T >> &distance, NodeArray< NodeArray< edge >> &pred)
 Runs singleSourceShortestPathsPreferringTerminals from all terminals. More...
 
static void allTerminalShortestPaths (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T >> &distance, NodeArray< NodeArray< edge >> &pred, std::function< void(const EdgeWeightedGraph< T > &, node, const NodeArray< bool > &, NodeArray< T > &, NodeArray< edge > &)> ssspFunc=singleSourceShortestPaths)
 Runs a given (or the default) single-source-shortest-paths function from all terminals. More...
 
static void allNodeShortestPathsStandard (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T >> &distance, NodeArray< NodeArray< edge >> &pred)
 Runs singleSourceShortestPathsStandard from all nodes. More...
 
static void allNodeShortestPathsPreferringTerminals (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T >> &distance, NodeArray< NodeArray< edge >> &pred)
 Runs singleSourceShortestPathsPreferringTerminals from all nodes. More...
 
static void allNodeShortestPaths (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T >> &distance, NodeArray< NodeArray< edge >> &pred, std::function< void(const EdgeWeightedGraph< T > &, node, const NodeArray< bool > &, NodeArray< T > &, NodeArray< edge > &)> ssspFunc=singleSourceShortestPaths)
 Runs a given (or the default) single-source-shortest-paths function from all nodes. More...
 
static void allPairShortestPathsPreferringTerminals (const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T >> &distance, NodeArray< NodeArray< edge >> &pred)
 Modified all-pair-shortest-paths algorithm (Floyd-Warshall) with heuristic to prefer paths over terminals. More...
 
static void allPairShortestPathsStandard (const EdgeWeightedGraph< T > &G, const NodeArray< bool > &, NodeArray< NodeArray< T >> &distance, NodeArray< NodeArray< edge >> &pred)
 Standard all-pair-shortest-paths algorithm (Floyd-Warshall) More...
 
static void allPairShortestPaths (const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T >> &distance, NodeArray< NodeArray< edge >> &pred)
 The default all-pair-shortest-paths algorithm. More...
 
static void drawSVG (const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, const EdgeWeightedGraphCopy< T > &steinerTree, const char *filename)
 Writes an SVG file of a minimum Steiner tree in the original graph. More...
 
static void drawSVG (const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, const char *filename)
 Writes an SVG file of the instance graph. More...
 
static void drawSteinerTreeSVG (const EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, const char *filename)
 Writes a SVG that shows only the given Steiner tree. More...
 

Detailed Description

template<typename T>
class ogdf::MinSteinerTreeDirectedCut< T >

This class implements the Directed Cut Integer Linear Program for the Steiner tree problem.

Definition at line 71 of file MinSteinerTreeDirectedCut.h.

Constructor & Destructor Documentation

◆ MinSteinerTreeDirectedCut()

template<typename T >
ogdf::MinSteinerTreeDirectedCut< T >::MinSteinerTreeDirectedCut ( )
inline

Definition at line 199 of file MinSteinerTreeDirectedCut.h.

Member Function Documentation

◆ computeSteinerTree()

template<typename T >
T ogdf::MinSteinerTreeDirectedCut< T >::computeSteinerTree ( const EdgeWeightedGraph< T > &  G,
const List< node > &  terminals,
const NodeArray< bool > &  isTerminal,
EdgeWeightedGraphCopy< T > *&  finalSteinerTree 
)
overrideprotectedvirtual

Computes the actual Steiner tree.

Returns
The total cost of the final Steiner tree

Implements ogdf::MinSteinerTreeModule< T >.

Definition at line 2183 of file MinSteinerTreeDirectedCut.h.

◆ setConfigFile()

template<typename T >
void ogdf::MinSteinerTreeDirectedCut< T >::setConfigFile ( const char *  configfile)
inline

Set a configuration file to use. The contents of the configuration file can override all other used options.

Definition at line 112 of file MinSteinerTreeDirectedCut.h.

◆ setEpsilon()

template<typename T >
void ogdf::MinSteinerTreeDirectedCut< T >::setEpsilon ( double  eps)
inline

Set the epsilon for the LP.

Definition at line 108 of file MinSteinerTreeDirectedCut.h.

◆ setMaxFlowModule()

template<typename T >
void ogdf::MinSteinerTreeDirectedCut< T >::setMaxFlowModule ( MaxFlowModule< double > *  module)
inline

Set the maximum flow module to be used for separation.

Definition at line 123 of file MinSteinerTreeDirectedCut.h.

◆ setMaxNumberAddedCuttingPlanes()

template<typename T >
void ogdf::MinSteinerTreeDirectedCut< T >::setMaxNumberAddedCuttingPlanes ( int  b)
inline

Set maximum number of added cutting planes per iteration.

Definition at line 148 of file MinSteinerTreeDirectedCut.h.

◆ setPoolSizeInitFactor()

template<typename T >
void ogdf::MinSteinerTreeDirectedCut< T >::setPoolSizeInitFactor ( int  b)
inline

Set factor for the initial size of the cutting pool.

Definition at line 194 of file MinSteinerTreeDirectedCut.h.

◆ setPrimalHeuristic()

template<typename T >
void ogdf::MinSteinerTreeDirectedCut< T >::setPrimalHeuristic ( MinSteinerTreeModule< double > *  b)
inline

Set the module option for the primal heuristic (use MinSteinerTreeModule<double> types). Default: MinSteinerTreeModuleTakahashi.

Definition at line 183 of file MinSteinerTreeDirectedCut.h.

◆ setPrimalHeuristicCallStrategy()

template<typename T >
void ogdf::MinSteinerTreeDirectedCut< T >::setPrimalHeuristicCallStrategy ( int  b)
inline

Set primal heuristic call strategy.

Definition at line 187 of file MinSteinerTreeDirectedCut.h.

◆ setSaturationStrategy()

template<typename T >
void ogdf::MinSteinerTreeDirectedCut< T >::setSaturationStrategy ( int  b)
inline

Set saturation strategy for nested cuts.

Definition at line 173 of file MinSteinerTreeDirectedCut.h.

◆ setSeparationStrategy()

template<typename T >
void ogdf::MinSteinerTreeDirectedCut< T >::setSeparationStrategy ( int  b)
inline

Set separation strategy for nested cuts.

Definition at line 168 of file MinSteinerTreeDirectedCut.h.

◆ useBackCuts()

template<typename T >
void ogdf::MinSteinerTreeDirectedCut< T >::useBackCuts ( bool  b)
inline

Switch computation of back-cuts on or off.

Definition at line 158 of file MinSteinerTreeDirectedCut.h.

◆ useDegreeConstraints()

template<typename T >
void ogdf::MinSteinerTreeDirectedCut< T >::useDegreeConstraints ( bool  b)
inline

Switch usage of degree constraints (like indeg <= 1) on or off.

Definition at line 128 of file MinSteinerTreeDirectedCut.h.

◆ useFlowBalanceConstraints()

template<typename T >
void ogdf::MinSteinerTreeDirectedCut< T >::useFlowBalanceConstraints ( bool  b)
inline

Switch usage of flow balance constraints on or off.

Definition at line 143 of file MinSteinerTreeDirectedCut.h.

◆ useGSEC2Constraints()

template<typename T >
void ogdf::MinSteinerTreeDirectedCut< T >::useGSEC2Constraints ( bool  b)
inline

Switch usage of constraints x_uv + x_vu <= 1 on or off.

Definition at line 138 of file MinSteinerTreeDirectedCut.h.

◆ useIndegreeEdgeConstraints()

template<typename T >
void ogdf::MinSteinerTreeDirectedCut< T >::useIndegreeEdgeConstraints ( bool  b)
inline

Switch usage of indegree edge constraints (indeg(v) >= outgoing edge(v,x) for all x) on or off.

Definition at line 133 of file MinSteinerTreeDirectedCut.h.

◆ useMinCardinalityCuts()

template<typename T >
void ogdf::MinSteinerTreeDirectedCut< T >::useMinCardinalityCuts ( bool  b)
inline

Switch usage of the cardinality heuristic (minimum-cardinality cuts) on or off.

Definition at line 178 of file MinSteinerTreeDirectedCut.h.

◆ useNestedCuts()

template<typename T >
void ogdf::MinSteinerTreeDirectedCut< T >::useNestedCuts ( bool  b)
inline

Switch computation of nested cuts on or off.

Definition at line 163 of file MinSteinerTreeDirectedCut.h.

◆ useTerminalShuffle()

template<typename T >
void ogdf::MinSteinerTreeDirectedCut< T >::useTerminalShuffle ( bool  b)
inline

Switch terminal shuffling before separation on or off.

Definition at line 153 of file MinSteinerTreeDirectedCut.h.

Member Data Documentation

◆ m_addDegreeConstraints

template<typename T >
bool ogdf::MinSteinerTreeDirectedCut< T >::m_addDegreeConstraints
protected

Definition at line 80 of file MinSteinerTreeDirectedCut.h.

◆ m_addFlowBalanceConstraints

template<typename T >
bool ogdf::MinSteinerTreeDirectedCut< T >::m_addFlowBalanceConstraints
protected

Definition at line 83 of file MinSteinerTreeDirectedCut.h.

◆ m_addGSEC2Constraints

template<typename T >
bool ogdf::MinSteinerTreeDirectedCut< T >::m_addGSEC2Constraints
protected

Definition at line 82 of file MinSteinerTreeDirectedCut.h.

◆ m_addIndegreeEdgeConstraints

template<typename T >
bool ogdf::MinSteinerTreeDirectedCut< T >::m_addIndegreeEdgeConstraints
protected

Definition at line 81 of file MinSteinerTreeDirectedCut.h.

◆ m_backCutComputation

template<typename T >
bool ogdf::MinSteinerTreeDirectedCut< T >::m_backCutComputation
protected

Definition at line 86 of file MinSteinerTreeDirectedCut.h.

◆ m_callPrimalHeuristic

template<typename T >
int ogdf::MinSteinerTreeDirectedCut< T >::m_callPrimalHeuristic
protected

Definition at line 91 of file MinSteinerTreeDirectedCut.h.

◆ m_configFile

template<typename T >
const char* ogdf::MinSteinerTreeDirectedCut< T >::m_configFile
protected

Definition at line 74 of file MinSteinerTreeDirectedCut.h.

◆ m_eps

template<typename T >
double ogdf::MinSteinerTreeDirectedCut< T >::m_eps
protected

Definition at line 75 of file MinSteinerTreeDirectedCut.h.

◆ m_maxFlowModuleOption

template<typename T >
std::unique_ptr<MaxFlowModule<double> > ogdf::MinSteinerTreeDirectedCut< T >::m_maxFlowModuleOption
protected

Definition at line 79 of file MinSteinerTreeDirectedCut.h.

◆ m_maxNrAddedCuttingPlanes

template<typename T >
int ogdf::MinSteinerTreeDirectedCut< T >::m_maxNrAddedCuttingPlanes
protected

Definition at line 84 of file MinSteinerTreeDirectedCut.h.

◆ m_minCardinalityCuts

template<typename T >
bool ogdf::MinSteinerTreeDirectedCut< T >::m_minCardinalityCuts
protected

Definition at line 90 of file MinSteinerTreeDirectedCut.h.

◆ m_nestedCutComputation

template<typename T >
bool ogdf::MinSteinerTreeDirectedCut< T >::m_nestedCutComputation
protected

Definition at line 87 of file MinSteinerTreeDirectedCut.h.

◆ m_poolSizeInitFactor

template<typename T >
int ogdf::MinSteinerTreeDirectedCut< T >::m_poolSizeInitFactor
protected

Definition at line 93 of file MinSteinerTreeDirectedCut.h.

◆ m_primalHeuristic

template<typename T >
MinSteinerTreeModule<double>* ogdf::MinSteinerTreeDirectedCut< T >::m_primalHeuristic
protected

Definition at line 92 of file MinSteinerTreeDirectedCut.h.

◆ m_saturationStrategy

template<typename T >
int ogdf::MinSteinerTreeDirectedCut< T >::m_saturationStrategy
protected

Definition at line 89 of file MinSteinerTreeDirectedCut.h.

◆ m_separationStrategy

template<typename T >
int ogdf::MinSteinerTreeDirectedCut< T >::m_separationStrategy
protected

Definition at line 88 of file MinSteinerTreeDirectedCut.h.

◆ m_shuffleTerminals

template<typename T >
bool ogdf::MinSteinerTreeDirectedCut< T >::m_shuffleTerminals
protected

Definition at line 85 of file MinSteinerTreeDirectedCut.h.


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