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.

void	setEpsilon (double eps)
	Set the epsilon for the LP.

void	setMaxFlowModule (MaxFlowModule< double > *module)
	Set the maximum flow module to be used for separation.

void	setMaxNumberAddedCuttingPlanes (int b)
	Set maximum number of added cutting planes per iteration.

void	setPoolSizeInitFactor (int b)
	Set factor for the initial size of the cutting pool.

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

void	setPrimalHeuristicCallStrategy (int b)
	Set primal heuristic call strategy.

void	setSaturationStrategy (int b)
	Set saturation strategy for nested cuts.

void	setSeparationStrategy (int b)
	Set separation strategy for nested cuts.

void	useBackCuts (bool b)
	Switch computation of back-cuts on or off.

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

void	useFlowBalanceConstraints (bool b)
	Switch usage of flow balance constraints on or off.

void	useGSEC2Constraints (bool b)
	Switch usage of constraints x_uv + x_vu <= 1 on or off.

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

void	useMinCardinalityCuts (bool b)
	Switch usage of the cardinality heuristic (minimum-cardinality cuts) on or off.

void	useNestedCuts (bool b)
	Switch computation of nested cuts on or off.

void	useTerminalShuffle (bool b)
	Switch terminal shuffling before separation on or off.

Public Member Functions inherited from ogdf::MinSteinerTreeModule< T >
virtual	~MinSteinerTreeModule ()
	Do nothing on destruction.

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.

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.

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.

static void	getTerminals (List< node > &terminals, const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal)
	Generates a list (as List<node>) of all terminals.

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.

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.

static void	sortTerminals (List< node > &terminals)
	Sort terminals by index.

static T	pruneAllDanglingSteinerPaths (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal)
	Prunes nonterminal leaves and their paths to terminal or branching nodes.

static T	pruneDanglingSteinerPathFrom (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, node start)
	Prunes the dangling Steiner path beginning at a given nonterminal leaf only.

static T	pruneDanglingSteinerPathsFrom (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, const List< node > &start)
	Prunes dangling Steiner paths beginning at given nonterminal leaves only.

static T	removeCyclesFrom (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal)
	Remove remaining cycles from a Steiner "almost" tree.

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.

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)

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.

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.

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.

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.

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.

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.

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.

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.

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)

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.

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.

static void	drawSVG (const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, const char *filename)
	Writes an SVG file of the instance graph.

static void	drawSteinerTreeSVG (const EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, const char *filename)
	Writes a SVG that shows only the given Steiner tree.

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 82 of file MinSteinerTreeDirectedCut.h.

Constructor & Destructor Documentation

◆ MinSteinerTreeDirectedCut()

template<typename T >

ogdf::MinSteinerTreeDirectedCut< T >::MinSteinerTreeDirectedCut ( )

inline

Definition at line 176 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 2079 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 122 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 119 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 128 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 143 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 174 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 164 of file MinSteinerTreeDirectedCut.h.

◆ setPrimalHeuristicCallStrategy()

template<typename T >

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

inline

Set primal heuristic call strategy.

Definition at line 167 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 158 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 155 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 149 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 131 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 140 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 137 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 134 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 161 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 152 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 146 of file MinSteinerTreeDirectedCut.h.

Member Data Documentation

◆ m_addDegreeConstraints

template<typename T >

bool ogdf::MinSteinerTreeDirectedCut< T >::m_addDegreeConstraints

protected

Definition at line 91 of file MinSteinerTreeDirectedCut.h.

◆ m_addFlowBalanceConstraints

template<typename T >

bool ogdf::MinSteinerTreeDirectedCut< T >::m_addFlowBalanceConstraints

protected

Definition at line 94 of file MinSteinerTreeDirectedCut.h.

◆ m_addGSEC2Constraints

template<typename T >

bool ogdf::MinSteinerTreeDirectedCut< T >::m_addGSEC2Constraints

protected

Definition at line 93 of file MinSteinerTreeDirectedCut.h.

◆ m_addIndegreeEdgeConstraints

template<typename T >

bool ogdf::MinSteinerTreeDirectedCut< T >::m_addIndegreeEdgeConstraints

protected

Definition at line 92 of file MinSteinerTreeDirectedCut.h.

◆ m_backCutComputation

template<typename T >

bool ogdf::MinSteinerTreeDirectedCut< T >::m_backCutComputation

protected

Definition at line 97 of file MinSteinerTreeDirectedCut.h.

◆ m_callPrimalHeuristic

template<typename T >

int ogdf::MinSteinerTreeDirectedCut< T >::m_callPrimalHeuristic

protected

Definition at line 102 of file MinSteinerTreeDirectedCut.h.

◆ m_configFile

template<typename T >

const char* ogdf::MinSteinerTreeDirectedCut< T >::m_configFile

protected

Definition at line 85 of file MinSteinerTreeDirectedCut.h.

◆ m_eps

template<typename T >

double ogdf::MinSteinerTreeDirectedCut< T >::m_eps

protected

Definition at line 86 of file MinSteinerTreeDirectedCut.h.

◆ m_maxFlowModuleOption

template<typename T >

std::unique_ptr<MaxFlowModule<double> > ogdf::MinSteinerTreeDirectedCut< T >::m_maxFlowModuleOption

protected

Definition at line 90 of file MinSteinerTreeDirectedCut.h.

◆ m_maxNrAddedCuttingPlanes

template<typename T >

int ogdf::MinSteinerTreeDirectedCut< T >::m_maxNrAddedCuttingPlanes

protected

Definition at line 95 of file MinSteinerTreeDirectedCut.h.

◆ m_minCardinalityCuts

template<typename T >

bool ogdf::MinSteinerTreeDirectedCut< T >::m_minCardinalityCuts

protected

Definition at line 101 of file MinSteinerTreeDirectedCut.h.

◆ m_nestedCutComputation

template<typename T >

bool ogdf::MinSteinerTreeDirectedCut< T >::m_nestedCutComputation

protected

Definition at line 98 of file MinSteinerTreeDirectedCut.h.

◆ m_poolSizeInitFactor

template<typename T >

int ogdf::MinSteinerTreeDirectedCut< T >::m_poolSizeInitFactor

protected

Definition at line 104 of file MinSteinerTreeDirectedCut.h.

◆ m_primalHeuristic

template<typename T >

MinSteinerTreeModule<double>* ogdf::MinSteinerTreeDirectedCut< T >::m_primalHeuristic

protected

Definition at line 103 of file MinSteinerTreeDirectedCut.h.

◆ m_saturationStrategy

template<typename T >

int ogdf::MinSteinerTreeDirectedCut< T >::m_saturationStrategy

protected

Definition at line 100 of file MinSteinerTreeDirectedCut.h.

◆ m_separationStrategy

template<typename T >

int ogdf::MinSteinerTreeDirectedCut< T >::m_separationStrategy

protected

Definition at line 99 of file MinSteinerTreeDirectedCut.h.

◆ m_shuffleTerminals

template<typename T >

bool ogdf::MinSteinerTreeDirectedCut< T >::m_shuffleTerminals

protected

Definition at line 96 of file MinSteinerTreeDirectedCut.h.

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

include/ogdf/graphalg/MinSteinerTreeDirectedCut.h

OpenGraph DrawingFramework

Classes

Public Member Functions

Protected Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ MinSteinerTreeDirectedCut()

Member Function Documentation

◆ computeSteinerTree()

◆ setConfigFile()

◆ setEpsilon()

◆ setMaxFlowModule()

◆ setMaxNumberAddedCuttingPlanes()

◆ setPoolSizeInitFactor()

◆ setPrimalHeuristic()

◆ setPrimalHeuristicCallStrategy()

◆ setSaturationStrategy()

◆ setSeparationStrategy()

◆ useBackCuts()

◆ useDegreeConstraints()

◆ useFlowBalanceConstraints()

◆ useGSEC2Constraints()

◆ useIndegreeEdgeConstraints()

◆ useMinCardinalityCuts()

◆ useNestedCuts()

◆ useTerminalShuffle()

Member Data Documentation

◆ m_addDegreeConstraints

◆ m_addFlowBalanceConstraints

◆ m_addGSEC2Constraints

◆ m_addIndegreeEdgeConstraints

◆ m_backCutComputation

◆ m_callPrimalHeuristic

◆ m_configFile

◆ m_eps

◆ m_maxFlowModuleOption

◆ m_maxNrAddedCuttingPlanes

◆ m_minCardinalityCuts

◆ m_nestedCutComputation

◆ m_poolSizeInitFactor

◆ m_primalHeuristic

◆ m_saturationStrategy

◆ m_separationStrategy

◆ m_shuffleTerminals

Open
Graph Drawing
Framework